---

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 0
Th 9/27	Course introduction and policies Arrays vs. ArrayLists, revisited Multidimensional arrays	Ch. 3.1
Week 1
Tu 10/2	Multidimensional arrays O-, Ω-, and Θ-notation	Ch. 3.2 - 3.4 Ch. 4.1 - 4.2
Th 10/4	Analyzing linked list variations using these notations Stacks, queues Generalized lists	Ch. 5
Week 2
Tu 10/9	"Alternative" forms of algorithm analysis Deques Amortized analysis (briefly)	Ch. 3.5
Th 10/11	Recursion Recurrences General trees General tree implementation (briefly)	Ch. 7.1
Week 3
Tu 10/16	N-ary and binary trees Tree traversals Binary search trees	Ch. 7.2 - 7.3 Ch. 10.1	Project #1 due 9:00pm
Th 10/18	Binary search trees (continued) The problem with binary search trees AVL trees	Ch. 10.2
Week 4
Tu 10/23	AVL trees (continued) Min heaps and max heaps Implementing a priority queue using a heap	Ch. 8.1 - 8.3.3
Th 10/25	Skip lists Probabilistic analysis (briefly) Hashing and hash tables Separate chaining "Good" hash functions	Ch. 9.1, 9.2, 9.4
Week 5
Tu 10/30	Open addressing Linear probing Double hashing Hashing objects other than numbers		Project #2 due 9:00pm
Th 11/1	Graphs: definition and terminology Directed vs. undirected graphs Graph implementation trade-offs	Ch. 13.1 - 13.5
Week 6
Tu 11/6	MIDTERM: regular lecture time and location
Th 11/8	Depth-first graph traversal Connectedness of a graph
Week 7
Tu 11/13	Breadth-first graph traversal Directed acyclic graphs (DAGs) Topological ordering of a DAG
Th 11/15	Dijkstra's shortest path algorithm Minimum spanning trees Introduction to sorting	Ch. 13.6 - 13.7 Ch. 3.1.2
F 11/16			Project #3 due 9:00pm
Week 8
Tu 11/20	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 11/22	University Holiday: Thanksgiving — NO LECTURE TODAY
Week 9
Tu 11/27	Sorting in O(n log n) time (continued) A lower bound for comparison-based sorting Linear time sorting (counting sort)	Ch. 11.3 - 11.5
Th 11/29	Linear time sorting (bucket sort and radix sort) The memory hierarchy (briefly) Performance differences between memory and external storage	Ch. 10.4 Ch. 14.2.1
F 11/30			Project #4 due 9:00pm
Week 10
Tu 12/4	Searching on external media 2-3 trees and B-trees Sorting on external media (briefly)	Ch. 14.3 - 14.4
Th 12/6	Equivalence classes The Union-Find algorithm
F 12/7			Project #5 due 9:00pm
Finals Week
Th 12/13	FINAL EXAM — 1:30-3:30pm, ICS 180