Prerona Chatterjee

Introduction to Theoretical Computer Science

• Introductory course for new graduate students.
• Class Timings: Mondays and Wednesdays from 14:30 to 16:00.
• Location: Room M2 at NISER Bhubaneswar

 

References

• Introduction to Algorithms (Cormen, Leiserson, Rivest, Stein)
• Introduction to Theoretical Computer Science (Barak)
• Probability and Computing (Mitzenmacher, Upfal)
• Applied Combinatorics (Roberts, Tesman)

 

Grading

• Weekly Revision Problems (take-home, due in ~2 days from release) - 10%
• Assignment 1 (take-home, due in ~10 days from release) - 10%
• Mid-sem (in-class) - 30%
• Assignment 2 (take-home, due in ~10 days from release) - 10%
• End-sem (in-class) - 40%

 

Problem Sets

• Revision: Week 1

 

Lecture Summary

Week 1: Mathematical Background

• Lecture 1 (Aug 04, 2025): Sets, functions and graphs.
• Lecture 2 (Aug 06, 2024): Basics of Logic, Logical Operations.

Week 2: Basics of Algorithms

• Lecture 3 (Aug 11, 2025): Searching and Sorting, Analysing Algorithms, Growth of Functions.
• Lecture 4 (Aug 13, 2024): Order Statistics and Elementary Data Structures.

Week 3: Divide-and-Conquer

Week 4: Dynamic Programming

Week 5: Greedy Algorithms and Amortised Analysis

Week 6: Basics of Optimisation

Week 7: Gradient Descent