---

This schedule is a work in progress and will be updated throughout the quarter; check in before each lecture for updates. In general, I'll try to keep the schedule at least a week or so ahead, so that you can anticipate where we're headed.

All assigned readings are from the Goodrich text. It is a good idea to skim the assigned reading before the lecture for the main ideas, attend lecture, and then to go through the assigned reading again to fill in the details that you missed, both in your initial skim of the reading and in the lecture.

Several lectures have little or no reading corresponding to them. In some cases, this is because a block of reading corresponds to more than one lecture. In other cases, the material covered in that lecture is not discussed in the textbook.

A few of the early lectures include material that is a review of ICS 22 / CSE 22. Some of the readings corresponding to these lectures were also assigned in ICS 22 / CSE 22. This course expands on those topics.

Date	Lecture Topics	Readings	Project Due
Week 1
Tu 6/26	Course introduction and policies Arrays vs. ArrayLists, revisited Multidimensional arrays O-, Ω-, and Θ-notation	Ch. 1.5 Ch. 4
Th 6/28	O-, Ω-, and Θ-notation (continued) Analyzing linked list variations using these notations Stacks, queues, and deques "Alternative" forms of algorithm analysis Amortized analysis (briefly)	Ch. 5 Ch. 6.1 (especially the analysis in 6.1.5)
Week 2
Tu 7/3	Analyzing the performance of recursion Recurrences General trees General tree implementation (briefly)	Ch. 11.1.5 Ch. 7.1
W 7/4	University Holiday: Independence Day
Th 7/5	Breadth-first tree traversals Preorder and postorder tree traversals N-ary and binary trees Binary search trees Inorder tree traversals	Ch. 7.2 - 7.3 Ch. 10.1
F 7/6			Project #1 due 11:59pm
Week 3
Tu 7/10	Binary search trees (continued) The importance of keeping binary search trees balanced AVL trees	Ch. 10.2
Th 7/12	AVL trees (continued) Priority queues (briefly) Implementing a priority queue using a min heap or max heap	Ch. 8.1 - 8.3
Week 4
Tu 7/17	Skip lists Probabilistic analysis (briefly) Hashing and hash tables Separate chaining "Good" hash functions	Ch. 9.4 Ch. 9.2
Th 7/19	Open addressing Linear probing Hashing objects other than numbers
F 7/20			Project #2 due 11:59pm
Week 5
Tu 7/24	Data compression (brief overview) Huffman codes and Huffman code trees
Th 7/26	MIDTERM: regular lecture time and location
Week 6
Tu 7/31	Graphs: definition and terminology Directed graphs Directed acyclic graphs (DAGs) Graph implementation trade-offs	Ch. 13.1 - 13.2, Ch. 13.4
Th 8/2	Undirected graphs Depth-first graph traversal	Ch. 13.3
F 8/3			Project #3 due 11:59pm
Week 7
Tu 8/7	Connectedness of a graph Strong connectedness vs. weak connectedness Dijkstra's shortest path algorithm	Ch. 13.5
Th 8/9	Breadth-first graph traversal Topological ordering of a DAG Minimum spanning trees	Ch. 13.6
Week 8
Tu 8/14	The sorting problem Sorting in O(n2) time (insertion and selection sort) Sorting in O(n log n) time (mergesort, quicksort, treesort, heapsort)	Ch. 11.1 - 11.2
Th 8/16	Sorting in O(n log n) time (continued) A lower bound for comparison-based sorting Linear time sorting (counting sort)	Ch. 11.3
F 8/17			Project #4 due 11:59pm
Week 9
Tu 8/21	Linear time sorting (bucket sort and radix sort) The memory hierarchy (briefly) Performance differences between memory and external storage
Th 8/23	Searching on external media B-trees Sorting on external media (briefly)	Ch. 14.3 - 14.4
Week 10
Tu 8/28	Equivalence classes The Union-Find algorithm	Ch. 11.4.3	Project #5 due 11:59pm
Th 8/30	FINAL EXAM: regular lecture time and location