CSE525 Graduate Algorithms Monsoon 2025

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

Undergraduate Algorithms course

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.

QUIZ: (60-90 mins duration) 10% (tentatively, on 2nd September)
LQ (LECTURE SHORT QUIZ): (5 mins duration, in class) 10% (few lowest scores will be dropped), each worth 1%
HOMEWORKA (before midsem): 10%

Done in a group of 2: 6 highest HQ worth 1.5% + 7th highest HQ is worth 1% (few lowest scores will be dropped)
Done individually: 5 highest HQ worth 2% (few lowest scores will be dropped)

HOMEWORKB (after midsem): 10%

Done in a group of 2: 6 highest HQ worth 1.5% + 7th highest HQ is worth 1% (few lowest scores will be dropped)
Done individually: 5 highest HQ worth 2% (few lowest scores will be dropped)

MIDSEM: worth 25%
ENDSEM: worth 35%
To pass the course, at least 25% overall and at least 20% in the largest of midsem & endsem is required.

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@

Lecture 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 (the ones in italics are tentative)

Recursive algorithms : Insertion Sort
Recursive algorithms : Stooge Sort
Divide and conquer algorithms
Divide and conquer algorithms: Select
Divide and conquer algorithms: FFT
Divide and conquer algorithms: Closest-Pair
backtracking algorithms
Dynamic Programming
Dynamic Programming: Edit Distance
Dynamic Programming: Space-saving DP for Edit Distance
Single-source Shortest-path DP
APSP
DFS-based Graph Algorithms
Reduction Algorithms
NP-hardness
NP-completeness
Gadgets for NP-completeness
Reductions from decision to finding solution
Approximation algorithms
Approximation algorithms
Disjoint-Set
Disjoint-Set
Disjoint-Set
Disjoint-Set

Proctored Exams

Homeworks

Collaboration Policy

You are free to discuss ideas with your peer in class or an AI agent. You are forbidden to ask a senior, or anyone outside your class, or even post it online. However, you must write the answers in your own in your own words. Which means that you should ensure that what you are writing to be submitted is original, even though the idea may not be fully yours. An easy way to ensure this is to write entirely from memory, without access to the discussions, notes, or even scribbles. If your ideas are borrowed from someone, you must acknowledge that person's name at the beginning of the answer. If your answers are borrowed from an AI agent, you must disclose the name of the agent and the prompts used. Marks will not be deducted for disclosing this information. If you do not disclose, and I find your answer to be unusually better or different, then I may deduct marks for falsely claiming authorship.