Preliminaries
- a reminder: some linear data structures
- complexity of operations on data structures
- pseudo-code and implementation independence
- experimental measures of algorithm performance
- the world's oldest algorithm
Review of C++ (Ch. 1-2 and handouts)
- dynamic memory allocation and memory leaks
- parameter passing and separate compilation
- copy constructors and operator overloading
- templates and the Standard Template Library
- inheritance and polymorphism
- abstract classes and virtual methods
Review of Recursion (handouts)
- the divide-and-conquer design pattern
- recursive backtracking
- Towers of Hanoi and the Knight's Tour
- using a stack to remove recursion
Asymptotic Analysis (Ch. 3)
- worst-case complexity
- big-Oh notation
- analysis of hashing and loop-based sorting
- relatives of big-Oh
- expanding recurrences
Binary Trees
(Ch. 6 and 7.3.1 and 11.4)
- traversal algorithms
- Huffman trees and text compression
- linked vs. array-based implementation
- construction and manipulation of binary heaps
|
Sorting and Selecting
(Ch. 10 and 7.3.4; also pp. 661-662)
- heap-sort, merge-sort, and 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-sort
- oblivious sorting (supplemental material to be provided)
Search Trees
(Ch. 9, but skip 9.6)
- AVL trees
- 2-4 trees
- Red-Black trees
- External Searching
Graphs
(Ch. 12)
- basic concepts and famous graph problems
- adjacency list vs. 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
Links:
C++ Resources Network
|