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 ~3 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
• Revision: Week 2
• Revision: Week 3

 

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): Linear Search, Insertion Sort, Bubble Sort, Analysing Algorithms.
• Lecture 4 (Aug 13, 2024): Binary Search, Order Statistics.

Week 3: Divide-and-Conquer

• Lecture 5 (Aug 18, 2025): Merge Sort, Lower Bound on Comparison Sorts.
• Lecture 6 (Aug 20, 2025): Maximum Subarray Problem, Matrix Multiplication.

Week 4: Greedy Algorithms

• Lecture 7 (Aug 27, 2025): Activity Selection Problem, Heaps, Priority Queues.
• Lecture 8 (Aug 29, 2025): Huffman Coding, Matroids and Greedy Algorithms.

Week 5: Dynamic Programming

Week 6: Basics of Optimisation

Week 7: Gradient Descent