IITM BS Advanced Algorithms (BSCS4021): Syllabus and Tips

Advanced Algorithms (BSCS4021) is a 4 credit level 4 elective in the IITM BS in Data Science. It picks up where PDSA stopped: stronger greedy and dynamic programming ideas, network flows, and then the main question of the course, what to do when a problem is NP-hard. The course page lists no prerequisite. It is a theory heavy course with proofs of correctness and performance.

Advanced Algorithms at a glance

The instructor is Prof. Neeldhara Misra of IIT Gandhinagar. The course page lists the type as "Elective". The handbook table lists it as "L4_DEGREE" with the tag "BP", 4 credits and no prerequisite. The two sources agree.

The handbook table (updated 18 March 2026) marks it as offered only in January 2027 out of the three terms it covers. It is not marked for May 2026 or September 2026.

What you learn in Advanced Algorithms

• Weeks 1 to 3: design techniques, one level up. Greedy algorithms on scheduling and stable matching problems. Matroids, a general setting where greedy methods are known to work. Dynamic programming on problems like edit distance, subset sum and optimal binary search trees.
• Weeks 4 and 5: network flows. Maximum flow, minimum cut, augmenting paths and bipartite matching. Then real uses, like exam scheduling, baseball elimination and project selection.
• Weeks 6 and 7: hardness and approximation. P, NP and NP-completeness through reductions from SAT and 3SAT to problems like independent set, graph colouring and subset sum. Then approximation algorithms for vertex cover, TSP and set cover, including LP rounding.
• Weeks 8 to 10: other ways to cope. Randomised algorithms (Monte Carlo and Las Vegas, min cut, MAX SAT, 2SAT, primality testing). Exact algorithms such as branch and bound and dynamic programming for TSP. Parameterised algorithms, which are fast when some part of the input is small.
• Weeks 11 and 12: kernels and solvers. Kernelization, which shrinks a hard instance before solving it. Then practical tools: turning problems into inputs for SAT solvers and LP solvers.

The suggested books are Introduction to Algorithms by Cormen, Leiserson, Rivest and Stein, and The Design of Approximation Algorithms by Williamson and Shmoys.

How it is assessed

The course page lists 12 weeks of coursework with weekly online assignments, 2 in-person invigilated quizzes and 1 in-person invigilated end term exam. It does not list an OPPE or a project.

Where it counts

It is a level 4 course tagged BP. BP appears to mean the programming stream, though the handbook does not spell it out. If so, it can be one of the two level 4 or higher programming courses the BS degree level asks for. Confirm with support. It is not part of any minor.

Who finds it hard and how to prepare

The difficulty is not coding. It is reasoning. You need to prove why a greedy choice is safe, why a reduction works, or why an approximation is within some factor of the best answer. The randomised weeks also need basic probability.

• Revise PDSA first. Greedy methods, divide and conquer, dynamic programming, network flows and linear programming all appear in PDSA (BSCS2002). Be comfortable with them before week 1.
• Write the recurrence before the code. For every DP problem, state what each table cell means in one sentence. Then write the recurrence.
• Build a reduction notebook. For each NP-hardness proof, record which problem reduces to which, and the key gadget. Reductions repeat in patterns.
• Brush up on probability. Expected value and the probability inequalities from Statistics 1 and 2 help in week 8.
• Try one solver. Encode a small puzzle as a SAT or LP problem and run a free solver. Week 12 makes more sense after that.

What to take before and after

Theory of Computation (BSCS3021) gives the formal side of NP-completeness. AI: Search Methods for Problem Solving (BSCS3003), a BSc core course, covers search and constraint methods that sit close to the coping strategies here. For large scale data problems, Algorithms for Data Science (BSDA5003) is a different course with a data focus.

Common questions

Is Advanced Algorithms the same as Algorithms for Data Science?

No. Algorithms for Data Science is BSDA5003, a level 5 course tagged BD/BP. It is part of the Minor in Algorithmic Decision Making. Advanced Algorithms (BSCS4021) is a level 4 BP course and is not part of a minor.

Do I need to write programs in this course?

The course page does not list an OPPE or a programming exam. The work is mostly designing algorithms and proving things about them. Coding a few of them still helps you understand them.

Can I use Advanced Algorithms for my BSc elective credits?

Yes. The BSc level has 8 elective credits, and the handbook's fee table shows level 4 credits as one way to fill them. You can also keep it for the BS level instead.

Is it harder than PDSA?

It goes much deeper. PDSA teaches the standard techniques. This course asks you to prove their limits and handle problems where no fast exact method is known.