Class Time
Section NA Monday Wednesday, 9:55 AM - 11:15 AM, Room#1308
Section NC Sunday Tuesday, 9:55 AM - 11:15 AM, Room#1306
Counseling Hours
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 01:
Lecture 01 [NC Jan 29, NA Jan 30]: Introduction (Motivation)
Lecture 02 [NC Jan 31, NA Feb 06]: Algorithm Analysis - I [Insertion Sort, Ref: Ch. 2.1, 2.2]
Week 02:
Lecture 03 [NC Feb 05, NA Mar 02]: Algorithm Analysis - II [Growth of Functions, Asymptotic Notations, Ref. Ch. 3.1] [Slide: Algorithm Analysis - I]
Lecture 04 [NC Feb 07, NA Feb 08]: Algorithm Analysis - III [Cost Function Analysis], Divide and Conquer - I [Merge Sort, Ref. Ch. 2.3] [Slide: Algorithm Analysis - II]
Week 03:
Lecture 05 [NC Feb 12, NA Feb 13]: Class Test - I [Syllabus: 2.1, 2.2, 2.3 (covered so far in class)]
Lecture 06 [NC Feb 14, NA Feb 15]: Divide and Conquer - II [Maximum Subarray Problem, Ref. Ch. 4.1] [Slide: Divide and Conquer]
Week 04:
Lecture 07 [NC Feb 19, NA Feb 20]: Heap, Heap Sort [Ref: Chapter 6.1-6.4] [Slide: Heap, PQ]
Week 05:
Lecture 08 [NC Feb 26, NA Feb 27]: Priority Queue [Ref. Chapter 6.5], Recursion Tree Method [Ref. Chapter 4.4]
Lecture 09 [NC Feb 28, NA Mar 01]: Sorting in Linear Time [Counting Sort, Radix Sort, Ref. Chapter 8.1, 8.2, 8.3]
Week 06:
Lecture 10 [NC Mar 04, NA Mar 04]: Dynamic Programming - I [Basic, Rod Cutting Problem, Ref. Chapter 15.1, 15.3]
Lecture 11 [NC Mar 05, NA Mar 06]: Class Test - II [Syllabus: Divide and Conquer, Heap, Heapsort, Priority Queue], Dynamic Programming - II [Coin Change Problem]
Lecture 12 [NC Mar 07, NA Mar 08]: Dynamic Programming - III [Longest Common Subsequence]
Week 07:
Lecture 13 [NC Mar 19, NA Mar 20]: Graphs - I [Graph Basics, Breadth First Search, Ref: Ch. 22.1, 22.2] [Slide: Graphs, BFS]
Lecture 14 [NC Mar 21, NA Mar 22]: Graphs - II [Depth First Search, Ref: Ch. 22.3] [Slide: DFS, Topological Sort]
Week 08:
Lecture 15 [NC Mar 28, NA Mar 27]: Graphs - III [Topological Sort, Ref. Ch. 22.4]
Lecture 16 [NC Apr 02, NA Mar 29]: Disjoint Sets, Disjoint Forests [Ref. Ch. 21.1-21.3] [Slide: Disjoint Sets]
Week 09:
Lecture 17 [NC Apr 04, NA Apr 03]: Class Test - III [Syllabus: Lecture 13-15], Minimum Spanning Tree - I [Growing a MST, Ref. Ch. 23.1]
Lecture 18 [NC Apr 06, NA Apr 05]: Minimum Spanning Tree - II [Prim's, Kruskal's Algorithm, Ref. Ch. 23.2, 23.3] [Slide: Prim]
Week 10:
Lecture 19 [NC Apr 11, NA Apr 10]: Single Source Shortest Path - I [Basics, Dijkstra's Algorithm, Ref. Ch. 24 (upto 24.1), 24.3] [Slide: Dijkstra] [Example]
Lecture 20 [NC Apr 13, NA Apr 12]: Single Source Shortest Path - II [Bellman-Ford Algorithm, Ref. Ch. 24.2] [Slide: Bellman Ford]
Week 11:
Lecture 21 [NC Apr 16, NA Apr 17]: Hash Tables - I [Direct Address Tables, Hash Tables, Ref. Ch. 11.1, 11.2]
Lecture 22 [NC Apr 18, NA Apr 19]: Class Test - IV [Syllabus: Single Source Shortest Path], Hash Tables - II [Hash Functions, Open Addressing, Ref. Ch. 11.3, 11.4]
Week 12:
Lecture 23 [NC Apr 23, NA Apr 24]: String Matching [Naive, Rabin-Karp Algorithm, Ref. Ch. 32.1, 32.2]
Lecture 24 [NC Apr 25, NA Apr 26]: NP-Completeness [Ref. Ch. 34]