CS 2800 : Design and Analysis of Algorithms

In Semester 2, 2021-2022, I will be teaching CS 2800: Design and Analysis of Algorithms.

Administrative Information.

When and Where.

Classes are held on Monday 10 am, Tuesday 9 am, Wednesday 8 am and Friday 1:00 pm. Location: Aryabhatta Hall and Zoom.

Pre-requisites.

The pre-reqs for the course are CS1100, CS1200, CS2700, CS2710.

Course Description.

The objective of the course is to teach techniques for effective problem solving incomputing. The use of different paradigms of problem solving will be used to illustrate clever and efficient ways to solve a given problem. In each case emphasis will be placed on rigorously proving correctness of the algorithm. In addition, the analysis of the algorithm will be used to show the efficiency of the algorithm over the naive techniques.

Textbooks and References.

• The textbook for the course is "Algorithms, by Dasgupta, Papadimitrou and Vazirani" (DPV).
• Algorithm Design, by Kleinberg and Tardos. Lecture slides for the book are available here.
• Review of Asymptotic notation: here and here.

List of topics:

• Introduction. Algorithmic problem solving, analysis of algorithms, emphasis on worst case running time. Algorithms for basic and modular arithmetic, primality testing, RSA and cryptography. Discussion on randomized algorithms. Reference: Ch 1 of DPV.
• Divide and Conquer. Integer multiplication revisited with an efficient algorithm that motivates and leads into recurrences. Solving recurrences using recurrence trees, repeated substitution, and statement of master theorem. Algorithms Merge Sort, finding medians, matrix multiplication and fast fourier transform. Reference: Ch 2 of DPV.
• Graph Algorithms: DFS and BFS. Representation of graphs, DFS and analysis of its correctness, topological sort, finding strongly connected components. BFS and its correctness, used to find single source shortest path in graphs. Reference: Ch 22 in CLRS.
• More Graph Algorithms: Dijkstra and Bellman-Ford. Reference: Ch 4 in DPV.
• Greedy Algorithms. Greedy choice, optimal substructure property, minimum spanning trees -- Prims and Kruskals, Huffman coding. Reference: Ch 5 in DPV.
• Dynamic Programming. Integral knapsack (contrasted with the fractional variant), longest increasing subsequence, edit distance, matrix chain multiplication, and independent sets in trees. Reference: Ch 6 in DPV.
• Linear Programming. Reference: Ch 7 in DPV.
• NP-completeness. Reduction amongst problems, classes NP, P, NP-complete, and polynomial time reductions. Reference: Ch 8 in DPV.
• Advanced Topics. Approximation algorithms, quantum computing etc as time permits.

Requirements.

• 2 Quizzes: 20% each.
• Final Exam: 30%.
• Tutorials: 30%. We will choose best n-2 out of total n tutorials.

Teaching Assistants.

Each student will be assigned to a TA. For any questions about grading, please email your TA along with the two lead TAs. Your TAs are:

• Lead: CS18D008 Anshu Yadav, cs18d008@cse.iitm.ac.in
• Lead: CS19D007 Keshav Ranjan, Keshav@cse.iitm.ac.in
• CS20D401 Vernekar Raghavendra Nagaraj, cs20d401@smail.iitm.ac.in
• CS19D401 Simran Kumari, cs19d401@smail.iitm.ac.in
• CS21D405 Anuja Modi, cs21d405@smail.iitm.ac.in
• CS21S021 Bhargavi Sriram, cs21s021@cse.iitm.ac.in
• CS18D015 Sugyani Mahapatra, msugyani@cse.iitm.ac.in
• CS20M066 Sukanya Sinha, cs20m066@smail.iitm.ac.in
• CS21M053 Ruheena Suhani Shaik, cs21m053@smail.iitm.ac.in
• CS21S011 Kondapalli Jayavardhan, cs21s011@cse.iitm.ac.in
• CS21S041 Nandini Mundra, cs21s041@smail.iitm.ac.in
• CS20M014 Apoorva Singh, cs20m014@smail.iitm.ac.in

Policies and Grades.

I expect all students to behave according to the highest ethical standards. Any cheating or dishonesty of any nature will result in failing the class plus being sent to the disciplinary committee. Read about plagiarism here.