Class Time
Section NA Monday Wednesday, 9:55 AM - 11:15 AM Room#1309
Section NB Monday Wednesday, 8:30 AM - 9:50 AM Room#1308
Counseling Hours
Sunday Tuesday, 4:50 PM - 7:00 PM
Monday Wednesday, 11:15 AM - 2:00 PM
Books
Introduction to Algorithms, Third edition
Charles E. Leiserson, Clifford Stein, Thomas H. Cormen, and Ronald Rivest
Grading
1. Class Attendance - 5%
2. Assignment - 5%
3. Class Tests (best 3 of 4) - 20%
4. Mid Exam - 30%
5. Final Exam - 40%
Course Schedule
Week 1:
Lecture 1 [Oct 05]: Introduction [Motivation]
Week 2:
Lecture 2 [Oct 17]: Algorithm Analysis - I [Complexity analysis (iterative), Growth of function; Ref: Chapter 1,2] [Slide: Algorithm Analysis - I]
Lecture 3 [Oct 19]: Algorithm Analysis - II [Insertion sort, Asymptotic notation; Ref: Chapter 2,3]
Week 3:
Lecture 4 [Oct 24]: Algorithm Analysis - III, Divide and Conquer - I [Complexity analysis (recursion tree), Merge sort; Ref: Chapter 2,4] [Slide: Algorithm Analysis - II]
Lecture 5 [Oct 26]: Heap, Heap Sort, Priority Queue [Ref: Chapter 6] [Slide: Heap, PQ]
Week 4:
Lecture 6 [Oct 31]: Class Test - I [Syllabus: Lecture 1-5], Divide and Conquer - II [Maximum Subarray Problem, Ref: Chapter 4] [Slide: Divide and Conquer]
Lecture 7 [Nov 02]: Algorithm Analysis - IV, Divide and Conquer - III [The Master Theorem, Ref: Chapter 4]
Lecture 8 [Nov 03]: Greedy Algorithms - I [Activity Selection, Coin Change, Knapsack Problem, Ref: Chapter 16] [Slide: Greedy]
Week 5:
Lecture 9 [Nov 07]: Greedy Algorithms - II [Kadane's Algorithm, Interval Partitioning] [Slide: Interval Partitioning]
Lecture 10 [Nov 09]: Assignment - I [PDF], Dynamic Programming - I [Fibonacci, Coin Change, Ref: Chapter 15] [Slide: Dynamic Programming]
Week 6:
Lecture 11 [Nov 14]: Dynamic Programming - II [0/1 Knapsack Problem], Divide and Conquer - IV [Inversion Counting] [Slide: Inversion Counting]
Lecture 12 [Nov 16]: Class Test - II [Syllabus: Lecture 6-10]
Week 7:
Lecture 13 [Nov 28]: Graphs - I [Preliminaries, BFS, Ref: Chapter 22] [Slide: Graphs, BFS]
Lecture 14 [Nov 30]: Graphs - II [DFS, Topological Sort, Ref: Chapter 22] [Slide: DFS, Topological Sort]
Week 8:
Lecture 15 [Dec 05]: Shortest Path Algorithms - I [Dijkstra's Algorithm, Ref: Chapter 24] [Slide: Dijkstra] [Example]
Lecture 16 [Dec 07]: Minimum Spanning Tree - I [Prim's Algorithm, Ref: Chapter 23] [Slide: Prim]
Week 9:
Lecture 17 [Dec 12]: Class Test - III [Syllabus: Lecture 13-16], Disjoint Sets [Ref: Chapter 21] [Slide: Disjoint Sets]
Lecture 18 [Dec 14]: Minimum Spanning Tree - II [Kruskal's Algorithm, Ref: Chapter 23] [Slide: Kruskal] [Pseudocode]
Week 10:
Lecture 19 [Dec 19]: Linear Time Sorting [Slide: Linear Time Sorting]
Lecture 20 [Dec 21]: Shortest Path Algorithms - II [Bellman Ford Algorithm, Ref: Chapter 24] [Slide: Bellman Ford]
Week 11:
Lecture 21 [Dec 26]: String Matching - I [Naive approach, Finite State Automaton] [Reading Material: String Matching]
Lecture 22 [Dec 28]: String Matching - II [Knuth-Morris-Pratt Algorithm]
Week 12:
Lecture 23 [Jan 02]: Class Test - IV [Syllabus: Lecture 17, 21-22], NP-Completeness [Slide: NP-Completeness]
Lecture 24 [Jan 04]: Review