Course Preview data structures as abstract containers of information complexity of operations on data structures pseudo-code and implementation independence experimental measures of algorithm performance Quick Review of C++ dynamic memory allocation and memory leaks reference parameters separate compilation copy constructors and overloaded assignment operators templates Review of Recursion the divide-and-conquer design pattern recursive backtracking Ackermann's function using a stack to remove recursion Asymptotic Analysis   (read Ch. 3) worst-case complexity primitive operations big-Oh notation analysis of hashing and loop-based sorting relatives of big-Oh expanding recurrences Binary Trees   (read Ch. 6 and 7.3.1) from graphs to trees to binary trees traversal algorithms linked implementation array-based implementation Huffman trees and text compression binary heaps

Sorting and Selecting   (read Ch. 10 and 7.3.4; also pp. 661-662) heap-sort merge-sort quick-sort basic concepts of discrete probability average-case analysis of quick-sort lower bounds on general sorting radix sorting in linear time randomized and deterministic quick-select Search Trees   (read Ch. 9, but skip 9.6) AVL trees 2-4 trees Red-Black trees B-trees Graphs   (read Ch. 12) basic concepts, terminology, and applications famous graph problems adjancency list and adjacency matrix implementations depth-first and breadth-first traversal Dijkstra's shortest-path algorithm Kruskal's minimum-spanning-tree algorithm Advanced Design and Analysis dynamic programming amortized analysis Introduction to Complexity Theory polynomial time as a measure of efficiency the P = NP problem NP-completeness