Asymptotic notation (Sections 2.3 and 2.4, Handout A)
Recurrence relations and how to solve them (Section 2.5, Handout A)
Algorithm analysis using recurrences and asymptotic notation (Section 2.6,
Handout A)
Styles of algorithm analysis: worst-case, average-case, amortized (Section 2.2,
Handout A)
Limitations of algorithm analysis; basic notions of experimental analysis
(Section 2.1, 2.2, 2.7)
Elementary building blocks: arrays and pointers; lists and memory allocation;
trees (Sections 3.1, 3.2, 3.3, 3.4, 3.5, 5.4, 5.5, 5.6, 5.7)
Top-down data structuring: abstract data types (Chapter 4)
Specific ADTs: stacks, queues, priority queues, dictionaries (Chapter 4,
Handout B), graphs
Implementations of stacks and queues
Implementations of priority queues: nonmeldable and meldable heaps (Chapter 9)
Implementations of dictionaries: binary search trees (Chapter 12)
Implementations of dictionaries: balanced search trees (Chapter 13)
Implementations of dictionaries: hashing (Chapter 14)
Implementations of graphs: adjacency matrices and lists, depth-first,
breadth-first, and priority search of a graph (Handout C)
Sorting: in quadratic time and in n log n time (Chapters 6, 7, and 8,
lightly, handout)
Advanced sorting: bucket sorting methods (Chapter 10), topological sorting of
a directed graph (Handout D)
If time permits: elementary graph algorithms (closure, shortest paths, minimum
spanning tree)