CPS616

Lecture Material

Ryerson University
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 Winter 2017
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

This page is maintained by Sophie Quigley (cps616@scs.ryerson.ca)
Last modified Monday, 10-Apr-2017 19:59:44 EDT