CompSci 161 Reading Assignments - Winter, 2025 (Dillencourt)

CompSci 161 - Reading Assignments Winter, 2025 (Dillencourt)

The textbook reading activities for the quarter are listed below. Generally, the readings for each week will be posted by Friday afternoon of the previous week.

Rules for receiving credit for a reading:

"Reading a section" means reading the section and doing all the participation activities.
Readings and associated activities are to be completed before 9:59AM on the due date (one minute before the start of class).
- For example, you would receive full credit for having read Section 1.1 and 1.2 if and only if the Zybook software logs you as having completed all participation activities in the section as of 9:59AM PDT on Wednesday, January 8.
There is no grace period.
It is recommended that you do not wait until the last possible moment to read the material and complete the activities.
Zybook allows me to obtain a retroactive report of who had finished which sections at any time in the past. Please keep this in mind before claiming that a section that you finished after the deadline was actually completed before the deadline.

Special rules for the first two weeks:

The readings for the first two weeks (up through and including Friday, January 17) will not count toward your reading score.
I will collect the data and send each student an individual report it during week 3. When this report is available, please read it. This helps identify errors. (For example, if you signed up for Zybooks using an email other than your UCI email, or if you signed up for Zyooks using the incorrect code.)
Beginnins week 3, readings will count toward your reading score.

Note: There are some ambiguities and errors in some of the participation activities. A list of the ones I am aware of (and suggested rewordings) can be found here.

Readings assignments:

Week 1:
- Monday, January 6: No reading assigned
- Wednesday, January 8:
  - 1.1: Introduction
  - 1.2: Analyzing algorithms
  - 1.3: A quick mathematical review
  - 1.4: A case study in algorithm analysis
- Friday, January 10:
  - 2.1: Introduction [Basic Data Structures]
  - 2.2: Stacks and queues
  - 2.3: Lists
  - 2.4: Trees
Week 2:
- Monday, January 13: No reading assigned
- Wednesday, January 15:
  - 3.1: Introduction [Binary Search Trees]
  - 3.2: Searches and updates
- Friday, January 17: The two readings for due this day are recommended but not required. The reason for this is given with each reading.
  - [Recommended but not required] Section 5.3 (just the material on Insertion Sort that starts immediately after Participation Activity 5.3, together with Algorithm 5.3.3 and Participation Activity 5.3.4).
    - [GT], somewhat idiosyncratically, presents insertion sort as a priority queue algorithm, and this is where it is covered. I will assign this section as required reading when we cover priority queues in class.
  - [Recommended but not required] Section 8.3: Quick Sort.
    - The details of the quicksort algorithm given in [GT] differ from the quicksort algorithm that I will present in class, and I will expect you to know the version presented in class. So I am not requiring this section. That having been said, you may find this section a useful complement to quicksort as presented in class.
Week 3:
- Monday, January 20: No reading assigned (University Holiday) and no lecture.
- Wednesday, January 22:
  - 8.2: Merge sort
  - 5.1: Introduction [Priority Queues and Heaps]
  - 5.2: Priority queues
  - 5.3: PQ-sort, selection sort, insertion-sort
- Friday, January 24: Note that Section 5.6 is marked as optional, which means your reading grade will not be affected by whether you read it.
  - 5.4: Heaps
  - 5.5: Heapsort
  - [Optional: 5.6 Extending priority queues]
  - 8.4: A lower bound on comparison-based sorting
Week 4:
- Monday, January 27:
  - 9.1: Introduction [Fast Sorting and selection]
  - 9.2: Bucket Sort and Radix Sort
- Wednesday, January 29. No reading assigned.
- Friday, January 31. Midterm 1. No reading assigned.
Nore: After we finish with sorting, we will cover Greedy Algorithms. The corresponding reading is Chapter 10, Sections 10.1 through 10.4. This will be the first assigned reading for week 5, if you want to get a head start on it.
Week 5:
- Monday, February 3: No requred reading, but please read the following note.
  - Note: I will cover Chapter 10 during week 5. The readings are not due until Wednesday, but it is fine to do them before that.
- Wednesday, February 5:
  - 10.1: Introduction [The Greedy Method]
  - 10.2 The fractional knapsack problem
  - 10.3 Task scheduling
  - 10.4 Text compression and Huffman coding
- Friday, February 7:
  - 11.1: Introduction [Divide and Conquer]
  - 11.2: Recurrences and the master theorem
Week 6: (Note: In the initial posting for the week, there was an error in the posted readings for Wednesday February 12 and Friday February 14. This error was fixed on February 7.)
- Monday, February 10:
  - 11.3: Integer multiplication
  - 11.4: Matrix multiplication
- Wednesday, February 12:
  - 12.1: Introduction [Dyamic Programming]
  - 12.4: The General Technique [Dynamic Programming]
  - 12.5: Telescope Scheduling
- Friday, February 14:
  - 12.3: Matrix chain-products
  - 12.7: The longest common subsequence problem [Recommended but not required]
    - Note: this section is not required. We will not cover this section in class and I will not ask about it on the exams. But it is useful knowledge, so I recommend you read it.
  - 12.8: The 0-1 Knapsack problem
Week 7:
- Monday, February 17: No reading assigned (University Holiday) and no lecture.
- Wednesday, February 19: No reading assigned
- Friday, February 21: No reading assigned
Week 8:
- Monday, February 24: No reading assigned.
- Wednesday, February 26. No reading assigned.
- Friday, February 28. Midterm 2. No reading assigned.
Note: After we finish with dynamic programming, we will cover graph algorithms. The corresponding reading is Chapter 13. All sections except for 13.5 will be required, and 13.5 is recommended. The first four section of Chapter 13 will be the first assigned reading for week 9, if you want to get a head start on it.
Week 9:
- Monday, March 3:
  - No reading assigned for Monday, but you might want to get started on the reading for the rest of the week.
- Wednesday, March 5:
  - 13.1 Introduction
  - 13.2 Graph Terminology and representations
  - 13.3 Depth-first search
- Friday, March 7:
  - 13.4 Breadth-first search
  - [Optional but see note 1 below] 13.5 Transitive closure
  - 13.6 Directed acyclic graphs
  - [optional but see note 2 below] 13.7 Biconnected components
  - Notes:
    1. This section is not required. We will not cover this section in class and I will not ask about it on the exams. But it is useful knowledge, so I recommend you read it.
    2. I do not know whether we will get to this material or not in class. If we do, it will be required reading for week 10. In any case, it is useful knowledge, so I recommend you read it.
Week 10:
- Monday, March 10:
  - 14.1 Introduction to shortest paths
  - 14.2 Single-source shortest paths
  - 14.3 Dijkstra's algorithm
- Wednesday, March 12:
  - 15.1 Introduction to minimum spanning trees
  - 15.2 Properties of minimum spanning trees
  - 15.3 Kruskal's algorithm (see note below)
  - 15.4 The Prim-Jarnik algorithm (see note below)
  - Note: We will cover the Prim-Jarnik algorithm before we cover Kruskal's algorithm, so you might want to read Section 15.4 before Section 15.3
- Friday, March 14: No Reading Assigned

Last modified: March 8, 2025