๐ Welcome to the notes and resources page for CS 610: Algorithms. The class plan is right here, and you can also jump to:

Class Plan

Greedy Algorithms I

Week 01

We introduce the paradigm of greedy algorithms with some examples.

Activity Scheduling

Islands War

Greedy Algorithms II

Week 02

We introduced the theory of matroids through several examples and explored why the greedy algorithm works for finding the min/max weight basis in a matroid.

Matroids

Minimum Spanning Trees

Week 03

We introduced the Union Find data structure to appreciate how Kruskal's algorithm can be efficiently implemented.

DSU

Shortest Paths I

Week 04

In this week we wrap up our discussion on the DSU data structure and study Dijkstra's algorithm for finding shortest paths.

Shortest Paths II

Week 05

We studied how the SP structure changes if weights are changed in a systematic way (all inc/dec; scaled) and let the main ideas behind Dijkstra's algorithm evolve from generalizing BFS in a natural way.

Shortest Paths III

Week 06

We examine how to modify Dijkstra to work in the presence of negative edge weights and we introduce Bellman-Ford to detect the presence of negative cycles, and Floyd-Warshall to handle APSP.

Network Flows I

Week 07

We introduce the setting of network flows and illustrate how it can be used to model, for example, the maximum matching problem.

Network Flows II

Week 08

We continue to demonstrate applications of flows with two problems: timetable scheduling and sport elimination.

Ford-Fulkerson for MaxFlow

Week 09

We discuss algorithms for computing maximum flows.

Ford-Fulkerson for MaxFlow (contd)

Week 10

We wrap up the proof of the correctness of the maxflow algorithm presented previously.

Dynamic Programming I

Week 11

We introduce DP with some recursion puzzles and revisit interval scheduling in the weighted setting. Also: maxflow-mincut duality and midsem recap.

Dynamic Programming - II

Week 12

More DP examples and puzzles.

Dnyamic Programming - III

Week 13

More DP examples and puzzles.

Dnyamic Programming - IV

Week 14

DP over trees and what's beyond polynomial-time algorithms.

#### Logistics

The timings of the classes are: 2:05-3PM on Mondays, Wednesdays, and Thursdays. The first class will be on the 4th of August.

Link to the Zoom sessions (passcode: 424242)

These sessions will be streamed over YouTube and the recordings can be accessed from this YouTube playlist.

Office hours: Iโll be generally available on this Discord Server - please join in (Discord is like WhatsApp but better ๐คฉ - if you don't already use it you can just login from the web) to ask your questions here, and hopefully meet the other course participants as well.

Inquiries over email (neeldhara.m@iitgn.ac.in) and over one-on-meetings are also welcome, but it's probably just simpler to use Discord :)

#### Grading Policy

- We will have a short quiz during every class based on the lecture using the Itempool platform. Each quiz will have between two and six questions and will be worth 2-6 points. Your overall score from the quizzes will be scaled out of 75.

At least half of these questions will be just a simple test of attention and you should be able to get them right if you are around and awake ๐ If you do want to prepare for the quizzes in advance, the topics for upcoming classes will be provided typically a week in advance on this course homepage.

Please respect the spirit of the quizzes and comply with the institutional honor code. Discussion and clarifications are encouraged in general, BUT do not discuss the quiz questions while the quizzes are live!

- There will be a mid-semester exam with a weightage of 10 points.

- There will be an end-semester exam with a weightage of 15 points.

- These exams will consist of multiple-choice questions and questions with numeric answers.

- There are no assignments, and therefore, no deadlines! Just show up and enjoy. ๐

#### Prerequisites and References

**Prerequisites:**

Elementary Data Structures and Algorithms โ specifically, asymptotic notation, arrays, lists, stacks, queues, search trees, trees, graphs; sorting, searching, BFS/DFS.

**References:**

- J. Kleinberg and E. Tardos, Algorithm Design, Pearson

- Jeff Erickson, Algorithms

- R Motwani and P. Raghavan, Randomized Algorithms, Cambridge University Press

- D. P. Williamson and D. B. Shmoys, The Design of Approximation Algorithms

- Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Daฬniel Marx, Marcin Pilipczuk, Michaa Pilipczuk and Saket Saurabh, Parameterized Algorithms, Springer

ย