CS 2800 : Design and Analysis of Algorithms

In Semester 2, 2017-2018, 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: CSB 36.

Office Hours and Teaching Assistants.

The teaching assistants for the course are listed below. Office hours to be decided.

• Arkadeep Sen (Lead). Email arkadeep.sen87@gmail.com
• Ditty Mathew (Lead). Email dittyvkm@gmail.com
• Girija Limaye (Lead). Email cs17d006@cse.iitm.ac.in
• Hitesh Gupta. Email CS16M023@smail.iitm.ac.in
• Pavan Ravishankar. Email CS17S026@smail.iitm.ac.in
• Anubha Pandey. Email CS16S023@smail.iitm.ac.in
• Sugandha Tiwari. Email CS17S001@smail.iitm.ac.in
• Lalitha Mahesh Voleti. Email CS16M046@smail.iitm.ac.in

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: 15% each.
• Final Exam: 40%.
• Tutorials: 30%. We will choose best n-2 out of total n tutorials.

Policies and Grades.

Collaboration is encouraged but you must write up solutions on your own. You must also write the names of all the people you discussed the problem with. In case you find material that will help you in solving some problems, you should mention the source in your writeup. Class participation will also be taken into account when assigning 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.