CPS616 |
Lecture Material |
|
CPS616 |
Lecture Material |
|
| Lecture | Topic | Textbook Chapters | Handouts | Other | Practice Exercises | Comments |
|---|---|---|---|---|---|---|
| 1 | Course Management | Course Outline | http://visualgo.net/ | |||
| 2 | Algorithm Fundamentals | 1.1, 1.2, 1.3 | Fundamentals | Bingo
KenKen | 1.1: 5, 6, 8, 12
1.2: 1, 2, 5, 9, 10 1.3: 1, 5, 9, 10 | Knowledge of ch 1.4 is assumed from cps305 |
| 3-8 | Mathematical Analysis of Algorithm Efficiency | 2.1, 2.2, 2.3, 2.4 | Analysis of Efficiency
Big O Notation | Wikipedia:
Summation Big O notation Table of time complexities | 2.1: 1, 8, 9
2.2: 1, 4a, 5, 7, 9, 10 2.3: 1, 2, 4, 5, 6, 10, 11 2.4: 1, 2, 3, 4, 8, 9, 10 | Knowledge of ch 2.5 is assumed from mth210 or cps420 |
| 9-11 | Brute Force and exhaustive search | 3.2,3.3,3.4 | Brute Force | String matching visualization | 3.2: 3, 4, 5, 6, 7, 8
3.3: 2, 3, 4, 5, 8 3.4: 2, 3, 6, 7, 10 3.5: 1, 3, 6, 7, 8, 10 | Knowledge of ch 3.1 is assumed from cps305 |
| 12 | DFS and BFS | 3.5 | From Wikipedia Commons: BFS, DFS on tree From David Galles: DFS, BFS on graph | |||
| 13-17 | Decrease and Conquer | 4.1, 4.2, 4.3, 4.4, 4.5 | Decrease and Conquer | Wikipedia: Gray codes | 4.1: 1, 2, 5, 9, 10, 11
4.2: 1, 4, 5, 6bc, 9 4.3: 1, 4ac, 5, 6, 7, 10, 11 4.4: 1, 4, 5, 8, 9, 11 4.5: 2, 5, 6, 7, 8, 9, 12, 13 | Knowledge of searching, sorting, and BSTs is assumed from cps305 |
| 18 | Divide and Conquer | 5.1,5.3, 5.4 (integer multiplication), 5.5 (closest pair) | Divide and Conquer | 5.1: 1, 2, 3, 4, 5, 7, 8, 9
5.3: 1, 2, 3, 5, 6, 7 (no proof), 8, 9, 10, 11 5.3: 1, 2, 3, 4, 5 5.5: 1, 5 | Knowledge of 5.2 Quicksort is assumed from cps305 | |
| 19-21 | Transform and Conquer | 6.1, 6.2, 6.3, 6.5, 6.6 | Transform and Conquer | River crossing | 6.1: 1, 2, 3, 4, 5, 7, 10 | |
| 22-24 | Dynamic programming | 8.1, 8.2, 8.4 | Dynamic Programming
Knapsack Example | 8.1: 1, 2, 3, 4, 5, 6
8.2: 1, 2, 4, 6 8.4: 1, 3, 4, 5, 6 | ||
| 25,26 | Greedy Techniques | 9.2, 9.4 | Greedy Techniques |
Minimum Spanning Trees:
Prim's algorithm, Kruskal's algorithm, visualisations Huffman Codes: Morse code and the Telegraph, Morse Army Training Film Morse Code table, Learning Morse Code | 9.1: 1, 2, 3
9.2: 1, 2, 3, 5 9.4: 1, 4, 5, 7, 8 | |
| 26,27 | Iterative Improvement | 10.1 | Iterative Improvement | Geometrical Overview of Simplex | Not covered in Winters 2017, 2018 | |
| 28-30 | Algorithm Limitations | 11.1, 11.2 | Algorithm Limitations |
Computational complexity of mathematical operations
Radix Sort: visualisation, complexity. | 11.1: 3, 5, 6, 7, 8, 11
11.2: 2, 3, 4, 5, 6, 8 | |
| 31-36 | NP-Completeness | 11.3 | NP Completeness | Turing Machines
TM Simulator AKS Primality Test | 11.3: 3, 5, 8, 9, 11, 12 |
