CompSci 161 - Reading Assignments Fall, 2023 (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.

• "Reading a section" means reading the section and doing all the participation activities.
• Readings and associated activities are to be completed before 1:59PM 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 1:59PM PDT on Monday, October 2.
• 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.

• Week 0:
  • Friday, September 29: There is no required reading for this class. However, if you have some time between now and the start of class, you might find it useful to get started on the reading due on Monday, October 2.
• Week 1:
  • Monday, October 2:
    • 1.1: Introduction
    • 1.2: Analyzing algorithms
  • Wednesday, October 4:
    • 1.3: A quick mathematical review
  • Friday, October 6:
    • 1.4: A case study in algorithm analysis
• Week 2:
  • Monday, October 9:
    • 2.1: Introduction [Basic Data Structures]
    • 2.2: Stacks and queues
    • 2.3: Lists
  • Wednesday, October 11:
    • 2.4: Trees
    • 3.1: Introduction [Binary Search Trees]
    • 3.2: Searches and updates
  • Friday, October 13: The first two readings are recommended but not required. The reason for this is given with each reading. The third reading, on merge sort, is required.
    • [Recommended but not required] Section 5.3 (just the material on Insertion Sort that starts immediately after Participation Activity 5.3, together with Figure 5.3.3 and Figure 5.4.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.
    • 8.2: Merge sort
• Week 3:
  • Monday, October 16:
    • 5.1: Introduction [Priority Queues and Heaps]
    • 5.2: Priority queues
    • 5.3: PQ-sort, selection sort, insertion-sort
  • Wednesday, October 18: 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]
  • Friday, October 20:
    • 8.4: A lower bound on comparison-based sorting
    • 9.1: Introduction [Fast Sorting and selection]
• Week 4:
  • Monday, October 23:
    • 9.2: Bucket Sort and Radix Sort
  • Wednesday, October 25: No reading assignment
  • Friday, October 27: No reading assignment.
• Week 5:
  • Monday, October 30: No reading assignment
  • Wednesday, November 1:
    • 10.1: Introduction [The Greedy Method]
    • 10.2 The fractional knapsack problem
    • 10.3 Task scheduling
  • Friday, November 3:
    • 10.4 Text compression and Huffman coding
    • 11.1: Introduction [Divide and Conquer]
    • 11.2 Recurrences and the master theorem
• Week 6:
  • Monday, November 6:
    • 11.3 Integer multiplication
  • Wednesday, November 8: Note that Section 11.5 is marked as optional, which means your reading grade will not be affected by whether you read it.
    • 11.4 Matrix multiplication
    • 11.5 The maxima-set problem [optional]
    • 12.1 Introduction [Dyamic Programming]
  • Friday, November 10: No reading assigned (University Holiday) and no lecture.
• Week 7:
  • Monday, November 13:
    • 12.3 The General Technique [Dynamic Programming]
    • 12.4: Telescope Scheduling
    • 12.7: The 0-1 Knapsack problem
  • Wednesday, November 15:
    • 12.2 Matrix chain-products
  • Friday, November 17:
    • 12.6 The longest common subsequence problem
• Week 8:
  • Monday, November 20: No reading assigned
  • Wednesday, November 22:
    • 13.1 Introduction [Graphs and traversals]
    • 13.2 Introduction [Graph Terminology and representations]
  • Friday, November 24: No reading assigned (University Holiday) and no lecture.
• Week 9:
  • Monday, November 27: (Note: Section 13.5 is marked optional, but you need to know the material on Directed Acyclic graphs.)
    • 13.5 Directed graphs. Read the portion on Directed acyclic graphs at the end of this section. It begins immediately after Preliminary Exercise 13.5.3. Since there is much material in this section that I will not cover in class, I am treating this section as optional. But again, read the portion on Directed acyclic graphs. This topic will be covered in class and you need to know it for the second midterm and the final.
    • 14.1 Introduction [Shortest paths]
    • 14.2 Single-source shortest paths
  • Wednesday, November 29:
    • 14.3 Dijkstra's algorithm
  • Friday, December 1: No reading assignment.
• Week 10:
  • Monday, December 4: No Reading Assigned.
    • Note: I pushed what would have been the required reading for Monday back to Wednesday, because I wanted to give you the weekend off after the midterm. However, the assignment for Wednesday is longer than usual, so if you do have time you might want to start on it early. If you do so, please read the note about recommended order of reading.
  • Wednesday, December 6:
    • Note: I recommend you read Section 15.4 before Section 15.3, as we will cover the Prim-Jarnik algorithm before we cover Kruskal's algorithm
    • 15.1 Introduction [Minimum spanning trees]
    • 15.2 Properties of minimum spanning trees
    • 15.3 Kruskal's algorithm
    • 15.4 The Prim-Jarnik algorithm
  • Friday, December 8:
    • 9.3 Selection