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.
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 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.
Note:
There are some ambiguities and errors in some of the participation activities.
A list of the ones I am aware of (and suggestion rewordings) can be found
here.
Readings assignments:
- 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:
Last modified: December 4, 2023