Dr. Lalatendu Behera
Vision and Mission of the Department and Institute
CS0501: Algorithm Design and Analysis
Instructor
Dr. Lalatendu Behera
TAs
Harshita Singh
Class Timings and Venue
Monday: 02:30 PM - 03:25 PM
Thursday: 03:30 PM - 04:25 PM
Friday: 04:30 PM - 05:25 PM
Venue: CS-201
Course Outcomes
| CO | |
| 1 | Recall and interpret fundamental data structures and complexity notations; analyze their performance in the context of algorithm design paradigms. |
| 2 | Construct and evaluate hierarchical and multimedia data structures to solve domain-specific problems efficiently. |
| 3 | Analyze and compare advanced data structures like heaps, disjoint sets, and graph-based algorithms for real-world applications. |
| 4 | Design and analyze advanced algorithms and classify problems into complexity classes using polynomial-time reductions to establish NP-completeness. |
CO - PO Mapping
| DSE | DSE | CSE (IS) | CSE (IS) | ||||
| CO | PO1 | PO2 | PO3 | PSO1 | PSO2 | PSO1 | PSO2 |
| CO1 | L | L | L | M | |||
| CO2 | M | M | L | H | |||
| CO3 | H | M | H | H | L | ||
| CO4 | H | H | H | M | |||
Recommended Books
Cormen, Thomas H., Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to algorithms. MIT press, 2022.
Kleinberg, Jon, and Eva Tardos. Algorithm design. Pearson Education India, 2006.
Goodrich, Michael T., and Roberto Tamassia. Algorithm design: foundations, analysis, and internet examples. John Wiley & Sons, 2001.
Evaluation
Class Performance: 5%
Assignments: 5%
Quiz: Three Quizzes (Best Two) (10%)
Mid-semester: 30%
End-semester: 50%
Syllabus
Recommended Materials
Classes
| Lecture No. | Date | Topic | Source |
| 1 | 25/08 | Introduction to the course |  |
| 2 | 26/08 | Introduction to Algorithms | |
| 3 | 01/09 | Upper Bound | |
| 4 | 03/09 | Lower and Tight Bound, Space Complexity | |
| 5 | 08/09 | Solving Recurrence Relation | |
| 6 | 09/09 | Merge Sort | |
| 7 | 10/09 | Quick Sort and Single Source Shortest Path Algorithm | |
| 8 | 15/09 | Correctness proof of Dijkstra Algorithm and Minimizing Maximum Lateness | |
| 9 | 16/09 | Correctness and Optimality proof of EDF Algorithm and Matrix Chain Multiplication | |
| 10 | 17/09 | Longest Common Subsequence | |
| 11 | 22/09 | Binary Search Tree | |
| 12 | 23/09 | AVL Tree | |
| 13 | 24/09 | 2-3 Tree | |
| 14 | 29/09 | 2-3-4 Trees | |
| 15 | 30/09 | Red-Black Trees | |
| 16 | 01/10 | No Class | |
| 17 | 13/10 | No Class | |
| 18 | 14/10 | Insertion in Red-Black Trees | |
| 19 | 15/10 | Revision | |
| 20 | 27/10 | Deletion in Red-Black Trees and Splay Tree | |
| 21 | 28/10 | Institute Lecture | |
| 22 | 29/10 | Binary Heap and Binomial Heap | |
| 23 | 03/11 | Fibonacci Heap | |
| 24 | 10/11 | Graphs, Connectivity, Articulation Points, Topological Sort | |
| 25 | 11/11 | Minimum Spanning Trees | |
| 26 | 12/11 | Network Flow | |
| 27 | 13/11 | Robin-Karp Algorithm | |
| 28 | 17/11 | Introduction to Parallel Algorithms, Parallel Merge Sort | |
| 29 | 18/11 | Introduction to Online Algorithms (Maintaining Search List, Online Caching) | |
| 30 | 19/11 | Linear Programming | |
| 31 | 24/11 | Classes P and NP and Co-NP, reduction, NP-completeness | |
| 32 | 25/11 | satisfiability problem (SAT) | |
| 33 | 26/11 | Subset sum problem, Vertex cover, Independent Set | |
Homeworks
Home work - 1 is due on 29/October/2025 at 5:30 PM.
Quizzes
1st Quiz on 24/September/2025 at 12:30 PM in CS-208 and CS-303. (Solutions: Click Here)
2nd Quiz on 07/November/2025 at 12:30 PM in CS-208 and CS-303.
Practice Questions
To be declared