CSE525 Graduate Algorithms Monsoon 2024

This course is an advanced form of an introductory algorithms course, and is meant to have a thorough grounding in core Algorithms required for pursuing PG degree in Computer Science. The course covers topics such as asymptotic notation, recurrence relation, graph algorithms, heaps, dynamic programming, greedy algorithms, divide and conquer, NP-completeness where the undergraduate contents of each topic is first reviewed in a fast-paced manner, and is followed by some advanced content.

Pre-requisites

Open only to M.Tech. and Ph.D. students (recommended for students with inadequate background in Algorithms).

Course Objectives

1. The student is able to design and analyse algorithms using techniques like divide and conquer, greedy and dynamic programming.
2. The student is able to use standard data structures like heaps, trees and graphs for designing algorithms.
3. The student is able to prove NP-completeness of problems using reductions.
4. The student is familiar with modern techniques to handle intractable problems like randomization, approximation, backtracking search.

Resource

We will be following the notes on Algorithms by Jeff Erickson

Evaluation Policy

Evaluation will be based on in-class short online quizzes (to be taken during lectures and tutorials), group homeworks, closed-book online proctored midsem and endsem exams. We will follow a flexible policy to let students focus more on exams or homeworks, as per their choice. 

The following algorithm will be used to calculate your cumulative score out of a total 100.

Homeworks can be done in groups of two or singly. Homework submissions happen on Google Classroom; to submit a homework, a student must (a) upload a typed sheet/scan of handwritten solution and (b) then turn-in (this is an explicit separate step on Classroom). Late submissions are not generally allowed. If a group of two students are submitting together, then the group member whose name is alphabetically before the other must submit the homework; the second group member should turn-in an empty submission stating that homework XYZ has been solved by group members ABC and DEF and submitted by PQR. Both students get the same score.

Course Personnel and Office Hours

All office hours will take place on the Meet Link given on Classroom.

Debajyoti Bera - dbera@
Suryendu Dalal - suryendud@

Quizzes

Quizzes during lectures will happen via Google Forms and are of short duration (5 minutes). They are used to test if students are following the concept. There could be multiple quizzes (or, none) in a lecture and the average score of an individual will be used as the final score for that quiz.

Lecture Topics

  1. Recursive algorithms : Insertion Sort
  2. Recursive algorithms : Stooge Sort
  3. Divide and conquer algorithms
  4. Divide and conquer algorithms: Select
  5. Divide and conquer algorithms: FFT
  6. Divide and conquer algorithms: Closest-Pair
  7. backtracking algorithms
  8. Dynamic Programming
  9. Dynamic Programming: Edit Distance
  10. Dynamic Programming: Space-saving DP for Edit Distance
  11. Single-source Shortest-path DP
  12. APSP
  13. DFS-based Graph Algorithms
  14. Reduction Algorithms
  15. NP-hardness
  16. NP-completeness
  17. Gadgets for NP-completeness
  18. Reductions from decision to finding solution
  19. Approximation algorithms
  20. Approximation algorithms
  21. Disjoint-Set
  22. Disjoint-Set
  23. Disjoint-Set
  24. Disjoint-Set

Proctored Exams

Homeworks