Course Schedule
Students are strongly encouraged to read the related text book chapters/sections before the class.
Session Title Notes Resources*
Session 1 Introduction agenda
Session 2 Induction scribes handwritten [1]: Chap 1 & 2 [2]: Chap 1
Session 3 Analysis of Algorithms and the O notation scribes handwritten [1]: Chap 3 [2]: Chap 2
Session 4 Induction and Algorithms scribes handwritten [1]: Chap 2 & 5
Session 5 Induction and Algorithms, cont'd scribes handwritten [1]: Chap 5
Session 6 Recurrence relations scribes handwritten [1]: Sec 3.5
Session 7 Akra-Bazzi (Master) Theorem scribes handwritten [1]: Sec 3.5.2
Session 8 Introduction to Data Structures: Array, Linked List scribes handwritten [1]: Sec 4.2 [2]: Sec 2.5
Session 9 Binary Search and Applications scribes handwritten [1]: Sec 6.2
Session 10 Sorting: Insertion Sort, Selection Sorts, Merge Sort scribes handwritten [1]: Sec 6.4
Session 11 Sorting: Bucket Sort and Radix Sort scribes handwritten [1]: Sec 6.4
Session 12 Probability slides
Session 13 Sorting: Quicksort scribes handwritten [1]: Sec 6.4.4
Session 14 Hashing scribes handwritten [1]: Sec 4.4
Session 15 Introduction to Graph Theory scribes handwritten [1]: Sec 7.1 [2]: Sec 3.1 & 3.2
Session 16 Trees and Binary Search Trees scribes handwritten [1]: Sec 4.3 & 6.2
Session 17 Heap and Heapsort scribes handwritten [1]: Sec 4.3.2 & 6.4.5
Session 18 Greedy Algorithms scribes handwritten [1]: Sec 5.10 [2]: Chap 4
Session 19 Dynamic Programming scribes handwritten [1]: Sec 5.10 [2]: Chap 6
Session 20 DFS, BFS scribes handwritten [1]: Sec 7.3.1 & 7.3.2 [2]: Sec 3.3 & 3.4
Session 21 DAGS and Topological Sorting scribes handwritten [1]: Sec 7.4 [2]: Sec 3.5 & 3.6
Session 22 Single-Source Shortest Path scribes handwritten [1]: Sec 7.5 [2]: Sec 4.4
Session 23 All-pair Shortest Path scribes handwritten [1]: Sec 7.7 [2]: Sec 6.8
Session 24 Min. Spanning Tree and the Concept of NP scribes handwritten [1]: Sec 7.6 [2]: Sec 4.5
[1]: Chap 11 [2]: Sec 8.1
Session 25 Reduction and NP Completeness scribes handwritten [1]: Chap 11 [2]: Chap 8
Session 26 NP Completeness, cont'd scribes handwritten [1]: Chap 11 [2]: Chap 8
Session 27 Parallel Algorithms scribes handwritten [1]: Chap 12
Session 28 Parallel Algorithms and Map Reduce scribes handwritten
Final Exam
* Resources:
[1] Intoduction to Algorithms - A Creative Approach
[2] Algorithm Design