- 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
|