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