Class Time
Section A Monday Wednesday, 9:55 AM - 11:15 AM Room#106
Section B Monday Wednesday, 8:30 AM - 9:50 AM Room#103
Counseling Hours
Sunday, Tuesday, 11:15 AM - 2:10 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 [May 29]: Introduction [Motivation], Algorithm Analysis - I [Basics] [Ref. Lecture]
Lecture 02 [May 31]: Algorithm Analysis - II [Cost function analysis, Asymptotic notation] [Ref. Lecture]
Week 02:
Lecture 03 [Jun 05]: Algorithm Analysis - III [Growth of function, Asymptotic notation] [Ref. Lecture] [Practice: Runtime Analysis] [Slide: Algorithm Analysis - I]
Lecture 04 [Jun 07]: Class Test - I [Syllabus: Lecture 01-03], Divide and Conquer - I [Merge Sort] [Ref. Ch. 2.3]
Week 03:
Lecture 05 [Jun 14]: Divide and Conquer - II [Simple Divide and Conquer Problems] [Ref. Lecture]
Week 04:
Lecture 06 [Jun 19]: Heap [Ref. Ch. 6.1-6.4] [Slide: Heap, PQ]
Lecture 07 [Jun 21]: HeapSort, Priority Queue
Week 05:
Lecture 08 [Jul 03]: Recursion Tree Method for Solving Recurrences [Ref. Ch. 4.4]
Lecture 09 [Jul 05]: Dynamic Programming - I [Basic, Rod Cutting Problem, Ref. Chapter 15.1, 15.3]
Week 06:
Lecture 10 [Jul 08]: Class Test - II [Syllabus: Lecture 04-07], Dynamic Programming - II [Coin Change Problem]
Lecture 11 [Jul 10]: Dynamic Programming - III [0/1 Knapsack Problem]
Lecture 12 [Jul 12]: Greedy Algorithms [Activity selection]
Week 07:
Lecture 13 [Jul 24]: Graph Basics [Ref. Ch. 22.1]
Week 08:
Lecture 14 [Jul 31]: BFS, DFS [Ref. Ch. 22.2-22.3]
Week 09:
[On leave]
Week 10:
Lecture 15 [Aug 16]: BFS, DFS Applications [Ref. Lecture]
Week 11:
Lecture 16 [Aug 19]: Disjoint Set Forests [Ref. Ch. 21.1-21.3]
Lecture 17 [Aug 19]: Class Test - III [Syllabus: Lecture 13-15]
Lecture 18 [Aug 21]: Single Source Shortest Path Basics, Dijkstra's Algorithm [Ref. Ch 24 (introduction), 24.3]
Lecture 19 [Aug 23]: Bellman-Ford Algorithm [Ref. Ch. 24.2], Direct Address Tables [Ref. Ch. 11.1]
Lecture 20 [Aug 24]: Class Test - IV [Syllabus: Disjoint Set Forests, Single Source Shortest Paths], Hash Tables, Hash Functions [Ref. Ch. 11.2-11.3]
Week 12:
Lecture 21 [Aug 30]: Open Addressing [Ch. 11.4], Naive String Matching, Rabin-Karp Algorithm [Ref. Ch. 32.1, 32.2]
Lecture 22 [Aug 31]: Rabin-Karp Algorithm (contd.), Polynomial Time, Polynomial Time Verification, P, NP [Ref. Ch. 34]