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) - 20%
• Mid-sem (in-class) - 30%
• Seminar (in-class) - 10%
• End-sem (in-class) - 40%

 

Problem Sets

• Revision: Week 1
• Revision: Week 2
• Revision: Week 3
• Revision: Week 4
• Revision: Week 5
• Revision: Week 6
• Revision: Week 7

 

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): Queues, Heaps, Priority Queues.
• Lecture 8 (Aug 29, 2025): Huffman Coding, Activity Selection Problem.

Week 5: Greedy Algorithms and Amortised Analysis

• Lecture 9 (Sep 1, 2025): Matroids and Greedy Algorithms.
• Lecture 10 (Sep 3, 2025): Stacks, Amortised Analysis.

Week 6: Graphs and Graph Algorithms

• Lecture 11 (Sep 8, 2025): Induced Subgraphs, Cliques, Independent Sets, Graph Isomorphism, Complement Graphs.
• Lecture 12 (Sep 10, 2025): Graph Representations, BFS, Shortest Paths.

Week 7: Graphs and Graph Algorithms

• Lecture 13 (Sep 15, 2025): Trees and Forests, Minimum Spanning Trees, Kruskal's Algorithm.
• Lecture 14 (Sep 17, 2025): Bipartite Graphs, Matchings, Hall's Theorem.

Week 8: Dynamic Programming

• Lecture 15 (Oct 06, 2025): .
• Lecture 16 (Oct 08, 2025): .

Weeks 9 and 10: Student Talks

• Lecture 17 (Oct 10, 2025): Single Source Shortest Path, the Bellman-Ford algorithm, Dijkstra's algorithm.
• Lecture 18 (Oct 13, 2025): Flow Networks, the Ford-Fulkerson Method.
• Lecture 19 (Oct 15, 2025): DFS, Finding Strongly Connected Components.
• Lecture 20 (Oct 17, 2025): Graph Coloring and its Applications.

Week 11: The classes P and NP

• Lecture 21 (Oct 27, 2025): .
• Lecture 22 (Oct 29, 2025): .