|
|
|---|
| Section | Pages | Points on Tests | Content |
|---|
| Test 1 - Chapter 1 | Introduction |
|---|
| | xiii-xvii (5) | | |
| 1.1 | 1-5 (5) | 3(2) | Insertion-Sort |
| 1.2 | 6-10 (5) | | Insertion-Sort with timing review |
| 1.3 | 11-15 (5) | 6 | Merge-Sort Divide-and-conquer algorithms. |
| 1.4 | 16 (1) (21) | | |
| Test 1 - Chapter 2 | Growth of Functions |
|---|
| 2.1 | 21-31 (11) | 40 | Definitions of Theta, O, Omega, o, and little omega; comparison of functions; evaluation of algorithms |
| 2.2 | 32-37 (6) (17) | 14 | Monotonicity, polynomially bounded, exponentials, logarithms, factorials, iterated logarithm, Fibonacci numbers |
| Test 1 - Chapter 4 | Recurrences |
|---|
| 4.1 | 53-57 (5) | 5 | substitution method |
| 4.2 | 58-60 (3) | 10 | iteration method - recursion trees |
| 4.3 | 61-64 (4) (12) | 5 | master method |
| Sorting and Order Statistics |
|---|
|
|---|
| Test 2 - Chapter 7 | Heapsort |
|---|
| 7.1 | 140-142 (3) | 10(1) | Parent, Left, Right |
| 7.2 | 143-144 (2) | 10(1) | Heapify |
| 7.3 | 145-146 (2) | 3 | Build-Heap |
| 7.4 | 147-148 (2) | | Heapsort |
| 7.5 | 149-150 (2) (11) | | Insert, Maximum, Extract-Max, Minimum, Extract-Min, Heap-Extract-Max, Heap-Insert |
| Test 2 - Chapter 8 | Quicksort |
|---|
| 8.1 | 153-155 (3) | 18 | Quicksort, Partition, not stable |
| 8.2 | 156-160 (5) | | Boundary conditions |
| 8.3 | 161-162 (2) | 5 | Random, Randomized-Partition, Randomized-Quicksort |
| 8.4 | 163-167 (5) (15) | | |
| Test 2 - Chapter 9 | Sorting in Linear Time |
|---|
| 9.1 | 172-174 (3) | 28 | decision tree |
| 9.2 | 175-177 (3) | 5 | Counting-Sort |
| 9.3 | 178-179 (2) (8) | 13 | Radix-Sort, review 9.3-4 |
| Test 4 - Chapter 10 | Medians and Order Statistics |
|---|
| 10.1 | 185-186 (2) | | Minimum |
| 10.2 | 187-189 (3) | 10 | Randomized-Select |
| 10.3 | 190-191 (2) (7) | 5 | Select |
|
|
|---|
| Test 4 - Chapter 12 | Hash Tables |
|---|
| 12.1 | 219-220 (2) | | Direct-Address-Search, Direct-Address-Insert, Direct-Address-Delete |
| 12.2 | 221-225 (5) | 15 | Chained-Hash-Insert, Chained-Hash-Search, Chained-Hash-Delete, plausibility? |
| 12.3 | 226-231 (6) | | |
| 12.4 | 232-239 (8) (21) | | Hash-Insert, Hash-Search |
| Advanced Design and Analysis Techniques |
|---|
|
|---|
| Test 2 - Chapter 16 | Dynamic Programming |
|---|
| 16.1 | 301-308 (8) | 25 | Matrix-Multiply, Matrix-Chain-Order, Matrix-Chain-Multiply, optimal parenthesization |
| 16.2 | 309-314 (6) (14) | 5 | Recursive-Matrix-Chain, Memoized-Matrix-Chain, Lookup-Chain, optimal substructure and overlapping subproblems |
| Review for Test 3 - Chapter 18 | Amortized Analysis |
|---|
| 18 | 356-378 (23) | | Amortized Analysis
Aggregate Method
- n ops take time T(n)
- avg cost of an op is T(n)/n
Accounting Method
Potential Method |
|
|
|---|
| Test 3 - Chapter 22 | Data Structures for Disjoint Sets |
|---|
| 22.1 | 440-442 (3) | 15 | Connected Components |
| 22.2 | 443-445 (3) (6) | 15 | Make-Set, Find-Set, amortized cost of Union? |
|
|
|---|
| Test 3 - Chapter 23 | Elementary Graph Algorithms |
|---|
| 23.1 | 463-468 (6) | 15 | Adjacency List, Adjacency Matrix, out-degree |
| 23.2 | 469-476 (9) | 15 | Breadth First Search didn't use color or predecessor |
| 23.3 | 477-484 (8) (23) | 15 | Depth First Search didn't use predecessor, Types of Edges |
| Test 3 - Chapter 24 | Minimum Spanning Trees |
|---|
| 24.1 | 498-503 (6) | 15 | 1-5 (445-446), Spanning Tree, Proof (501) |
| 24.2 | 504-513 (10) (16) | 15+5(4) | Kruskal's, Prim's, 24.2-1 understand |
| Test 4 - Chapter 25 | Single-Source Shortest Paths |
|---|
| 25.Intro | 514-518 (5) | 5 | |
| 25.1 | 519-526 (8) | | Initialize-Single-Source, Relax |
| 25.2 | 527-531 (5) | 15 | Dijkstra |
| 25.3 | 532-535 (4) (22) | 10 | Bellman-Ford |
|
|
|---|
| Test 2 - Chapter 31 | Matrix Operations |
|---|
| 31.1 | 730-737 (8) | | reference Matrix-Multiply (section 16.1) |
| 31.2 | 739-744 (6) (14) | 5 | Strassen's algorithm |