CSE525 Graduate Algorithms Monsoon 2022

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.

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.

QUIZSCORE = sum of 10 highest quiz percentages (normalized by 100) x 1.00
HWACOUNT = number of homework submissions before midsem (HQ 1-15)
HWBCOUNT = number of homework submissions after midsem (HQ 16-28)
Both HWACOUNT and HWBCOUNT are capped to 10 if more than 10 are submitted, and set to 5 if less than 5.
HWASCORE = sum of best HWACOUNT homework percentages from homeworks submitted before midsem (normalized by 100) x 1.50
HWBSCORE = sum of best HWBCOUNT homework percentages from homeworks submitted after midsem (normalized by 100) x 1.50
REDUCE = [(HWACOUNT - 5) + (HWBCOUNT - 5)] x 1.50
MIDSCORE = (35/75)x(75 - REDUCE) x midsem percentage (normalized by 100)
ENDSCORE = (40/75)x(75-REDUCE) x endsem percentage (normalized by 100)
CUMULATIVE (%) = QUIZSCORE + HWASCORE + HWBSCORE + MIDSCORE + ENDSCORE

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). If someone does not want to submit a homework, then he/she should not turn-in. The number of submitted homeworks shall be used for computing HWACOUNT and HWBCOUNT. Homeworks once turned-in cannot be considered later as unsubmitted; late submissions are also 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.

Quizzes

Quizzes during lectures will happen via Google Forms and are of short duration (2-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.

Course Personnel and Office Hours

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

Debajyoti Bera - dbera@ - TBA (email me if you want meet at some other time)
Ritesh Seth - riteshs@ - TBA
Sanchita Saha - sanchita21075@ - TBA
Shaguftha Zuveria Kottur - shaguftha21079@ - TBA