# CS2800 Design and Analysis of Algorithms

Jan - May 2023

**Coordinates**

- Where: CS15
- When: B slot - Mon (9 am), Tue (8 am), Wed (1 pm), Fri (11 am)

**Instructor**

- Yadu Vasudev
- SSB 207
- yadu@cse.iitm.ac.in

**TAs**

Abhijit, Ankit, Anmol, Barenya, Bibhuti, Keshav, Ravi, Sampriti, Souradipta, Susmit

**About this course**

This course is an introductory course on the design and analysis of algorithms. It serves as a recommended, and sometimes necessary, prerequisite for almost all courses in the area of theoretical computer science offered in the CSE department. The emphasis is on understanding some basic design principles that can be applied in a variety of algorithmic questions. That said, these principles are neither exhaustive nor applicable in all situations. The hope is that the student gets sufficient background to think in a principled manner when confronted with a new computational question.

**Prerequisites**: The course on programming and data structures (CS2700/CS2705) is a necessary prerequisite for the course. In particular, I will assume that you know the following (which are typically covered in CS2700/CS2705): - The concept of an abstract data type and the difference between ADTs and data structures. - Basic ADTs like stacks, queues, priority queues. Basic data structures like arrays, linked lists, heaps, simple BSTs and operations on them. - The concept of pseudocode, and the difference between pseudocode and a computer program. - Algorithms for sorting, searching, and basic algorithms on graphs. - The concept of asymptotic analysis, and the definitions of \(O(\cdot), \Omega(\cdot)\), and \(\Theta(\cdot)\) as well as \(o(\cdot)\) and \(\omega(\cdot)\).

The course will require you to design algorithms, and then mathematically prove their correctness. There **will not be any programming component** for this course, though you may be required to implement a few of the algorithms if you take the lab course Object-Oriented Analysis, Implementation and Algorithms (OOAIA, CS2810).

**Course contents**

The course will look at some basic algorithm design techniques using examples. The contents of the course include the following topics:

- Recursion and divide-and-conquer algorithms
- Dynamic programming
- Greedy algorithms
- Graph algorithms like shortest path, minimum spanning trees
- Brief introduction to intractability
- Advanced topics (based on time): Randomization in algorithms, network flows, linear programming

The topics included above will be covered at different depths, and the order in which they are covered will also vary.

**Course resources**

There are many textbooks and resources (both offline and online) that cover most of the material presented in the list above. We will not be following one textbook. Our main sources of reference will be the following textbooks.

**Algorithms**by*Jeff Erickson*- This book is freely available online and contains a large number of exercises with varying degrees of difficulty. This is a fairly recent book.**Algorithm Design**by*Jon Klienberg and Eva Tardos*- A slightly older textbook than the one by Erickson, this contains most of the material given in the course contents. It also contains chapters on topics that one might see in a slightly more advanced course. Copies are available in the library and the Indian edition is not too pricey (in case you are planning to buy).**Introduction to Algorithms**by*Cormen ,Leiserson, Rivest and Stein*(referred to as CLRS) - An old textbook, currently in its 4th edition. Copies are available in the library, and Indian editions (for the 2nd and 3rd editions) are not pricey.**Algorithms**by*Dasgupta, Papadimitriou and Vazirani*- Another nice book on algorithm design. Contains some topics that are not dealt properly in the three earlier books. Copies of the book are available in the library, but I am unable to find a cheap Indian edition of this book.

Apart from this, there are a lot of resources available online. We may refer to them occasionally. All these books contain a number of exercise problems for practice.

**Weekly schedule**

- Lectures: Mon (9 am), Tue (8 am), Wed (1 pm)
- Tutorials: Fri (11 am)

The Friday slot will be used for tutorials. This includes both ungraded practice tutorials, as well as mini-quizzes. Please see the details below to know the dates for the mini-quizzes and ungraded tutorials. We will stick to this schedule unless there is some unforeseen change in the academic calendar.

**Grading policy** (tentative)

The course will be evaluated through a series of quizzes and finally the end-sem. I will be releasing problem sets on a weekly basis, and we will have tutorial sessions to discuss the these problems and possible approaches to solving them. The tentative grading scheme is as follows.

**Important dates** (tentative)

Please note the following dates for the ungraded tutorials and mini-quizzes. The dates for Quiz 1,2 and end-semester examination will be as per the institute calendar.

**Contact**

Please sign up on the course discussion forum here. This will be the first point of contact for any issues related to the course. Please do not email me or the TAs unless the issue is specific to you (like missing lectures, correction in grading). Even for such issues, we highly recommend you to message privately using the discussion forum.

For general questions related to the course (any comments/doubts), please create a topic in the correct stream and add you question/comment there. You are also welcome to reply and clear the doubts of your friends.

Date | Lecture |
---|---|

Lecture #1Mon 16/01 |
Introduction to the course; administrative details; algorithms for integer multiplication - what constitutes a good algorithm? [slides] PS0 released |

Lecture #2Tue 17/01 |
Stable marriage problem; Gale-Shapley algorithm and examples [slides] |

Lecture #3Wed 18/01 |
Gale-Shapley algorithm - proof of correctness; properties of the solution and proof of optimality [slides] |

Tutorial #1Fri 20/01 |
Based on Problem set 0 |

Lecture #4Mon 23/01 |
Recall of asymptotic analysis; Divide-and-conquer - Karatsuba's algorithm, recurrence relations, recurrence trees, master theorem [slides] PS1 released |

Lecture #5Tue 24/01 |
Order statistics - finding the \(k^{th}\) smallest element; median-of-medians - recursive solution, analyzing the recurrence using recursion trees [slides] |

Lecture #6Wed 25/01 |
Convolution of vectors; equivalence with polynomial multiplication; evaluating polynomials on mulitple points; FFT algorithm [slides] |

Lecture #7Mon 30/01 |
FFT algorithm (contd.); Closest pair of points in 2D [slides] PS2 released |

Lecture #8Tue 31/01 |
Basic graph algorithms; adjacency matrices and lists; graph traversals - DFS [slides] |

Tutorial #2Wed 01/02 |
Discussion of Problem Sets 1 and 2 |

Mini quiz #1Fri 03/02 |
Based on material covered in Problem sets 0, 1, 2 |

Lecture #9Mon 06/02 |
BFS; finding connected components in graphs; digraphs - classification of edges [slides] PS3 released |

Lecture #10Tue 07/02 |
DFS with clocks - classification of edges; Topological ordering of DAGs [slides] |

Lecture #11Wed 08/02 |
Digraphs and their strongly connected components; Finding and labelling the strongly connected components of a digraph [slides] |

Tutorial #3Fri 10/02 |
Discussion of Problem set 3 |

Lecture #12Mon 13/02 |
Finding and labelling strongly connected components - Kosaraju-Sharir algorithm; Shortest paths in graphs - BFS [slides] PS4 released |

Lecture #13Tue 14/02 |
Shortest path in unweighed graphs - BFS (contd); Shortest paths in DAGs [slides] |

Lecture #14Wed 15/02 |
Shortest path in graphs - Dijkstra's algorithm [slides] |

Tutorial #4Fri 17/02 |
Discussion of Problem set 4 |

Lecture #15Mon 20/02 |
Shortest path in graphs - Dijkstra's algorithm (contd), Bellman-Ford algorithm [slides] |

Quiz #1Tue 21/02 |
Based on material covered till Mon Feb 13 |

Lecture #16Wed 22/02 |
Bellman-Ford algorithm (contd) [notes] |

Lecture #17Fri 24/02 |
Greedy algorithms - interval scheduling [notes] |

Lecture #18Mon 27/02 |
Greedy algorithms - scheduling jobs to minimize delays; exchange arguments PS5 released |

Lecture #19Tue 28/02 |
Greedy algorithms - scheduling jobs to minimize delays; exchange arguments; greedy vertex cover [notes] |

Lecture #20Wed 01/03 |
Huffman coding - optimal prefix codes and binary trees [notes] |

Tutorial #5Fri 03/03 |
Discussion of Problem set 5 |

Lecture #21Mon 06/03 |
Huffman coding - algorithm and proof of correctness [notes] PS6 released |

Lecture #22Tue 07/03 |
Huffman coding - implementation details; Minimum spanning trees - cut property [notes] |

Mini quiz #2Fri 10/03 |
Based on Problem sets 5 and 6 |

Lecture #23Mon 13/03 |
Minimum spanning trees - proof of the cut property; Boruvka's algorithm [notes] PS7 released |

Lecture #24Tue 14/03 |
Prim's and Kruskal's algorithms - examples, implementation details, running time [notes] |

Lecture #25Wed 15/03 |
Kruskal's algorithm - amortized analysis; data structures for disjoint sets [notes] |

Tutorial #6Fri 17/03 |
Discussion of Problem set 7 |

Quiz #2Tue 21/03 |
Based on material covered through Problems sets 5,6,7 |

Lecture #26Fri 24/03 |
Union-by-rank with path compression; Amortized analysis - accounting method [notes] |

Lecture #27Mon 27/03 |
Union-by-rank with path compression - amortized analysis [notes] |

Lecture #28Tue 28/03 |
Dynamic programming - text segmentation [notes] |

Lecture #29Wed 29/03 |
Dynamic programming - text justification, edit distance [notes] PS8 released |

Tutorial #7Fri 31/03 |
Discussion of Problem set 8 |

Lecture #30Mon 03/04 |
Dynamic programming - edit distance; saving space using divide-and-conquer [notes] |

Lecture #31Wed 05/04 |
Dynamic programming - edit distane (contd.); 0-1 Knapsack - pseudopolynomial-time algorithm [notes] Online lecture - video link on Zulip |

Lecture #32Mon 10/04 |
0-1 Knapsack - pseudopolynomial-time algorithm (contd.); Dynamic programming on trees - independent sets [notes] |

Lecture #33Tue 11/04 |
All Pairs Shortest Paths (APSP) - Johnson's algorithm; Dynamic programming based algorithms [notes] |

Lecture #34Wed 12/04 |
Floyd-Warshall algorithm; APSP and matrix multiplication [notes] |

Lecture #35Mon 17/04 |
APSP and matrix multiplication - Seidel's algorithm; Introduction to computational intractability [notes] PS9 released |

Lecture #36Tue 18/04 |
Introduction to intractability - P and NP; poly-time solving versus poly-time verification [notes] |

Lecture #37Wed 19/04 |
Polynomial-time reductions - NP completeness, examples of reductions [notes] |

Mini quiz #3Fri 21/04 |
Based on Problem set 8 |

Lecture #38Mon 24/04 |
NP-completeness - examples of reductions [notes] PS10 released |

Lecture #39Tue 25/04 |
Beyond NP-completeness - brief overview; Wrap-up of the course |

Mini quiz #4Wed 26/04 |
Based on Problem set 9 |