Modules / Lectures

Module Name | Download |
---|---|

noc21_cs49_assignment_Week_1 | noc21_cs49_assignment_Week_1 |

noc21_cs49_assignment_Week_10 | noc21_cs49_assignment_Week_10 |

noc21_cs49_assignment_Week_11 | noc21_cs49_assignment_Week_11 |

noc21_cs49_assignment_Week_12 | noc21_cs49_assignment_Week_12 |

noc21_cs49_assignment_Week_2 | noc21_cs49_assignment_Week_2 |

noc21_cs49_assignment_Week_3 | noc21_cs49_assignment_Week_3 |

noc21_cs49_assignment_Week_4 | noc21_cs49_assignment_Week_4 |

noc21_cs49_assignment_Week_5 | noc21_cs49_assignment_Week_5 |

noc21_cs49_assignment_Week_6 | noc21_cs49_assignment_Week_6 |

noc21_cs49_assignment_Week_7 | noc21_cs49_assignment_Week_7 |

noc21_cs49_assignment_Week_8 | noc21_cs49_assignment_Week_8 |

noc21_cs49_assignment_Week_9 | noc21_cs49_assignment_Week_9 |

Sl.No | Chapter Name | MP4 Download |
---|---|---|

1 | Lecture 1: Introduction | Download |

2 | Lecture 2: NP Completeness | Download |

3 | Lecture 3: SAT is NP-complete | Download |

4 | Lecture 4: More on NP completeness | Download |

5 | Lecture 05: Hierarchy Theorems | Download |

6 | Lecture 06: Introduction to Space Complexity | Download |

7 | Lecture 07: Savitch’s Theorem | Download |

8 | Lecture 08: Immerman-Szelepscenyi Theorem | Download |

9 | Lecture 09: Polynomial Hierarchy | Download |

10 | Lecture 10: A PSPACE Complete Problem | Download |

11 | Lecture 11: More on Polynomial Hierarchy | Download |

12 | Lecture 12: Alternating Turing Machines | Download |

13 | Lecture 13: Equivalence of Quantifier and Oracle Based Definitions of Polynomial Hierarchy | Download |

14 | Lecture 14: Boolean Circuits | Download |

15 | Lecture 15: Shannon’s Theorem and Karp-Lipton-Sipser Theorem | Download |

16 | Lecture 16: Bounded Depth Circuit Classes | Download |

17 | Lecture 17: Kannan’s Theorem | Download |

18 | Lecture 18: Probabilistic Complexity | Download |

19 | Lecture 19: StrongBPP and WeakBPP | Download |

20 | Lecture 20: One-sided and Zero-sided Error Probabilistic Complexity Classes | Download |

21 | Lecture 21: Error Reduction for BPP | Download |

22 | Lecture 22: BPP in PH and Logspace Randomized Classes | Download |

23 | Lecture 23: Valiant-Vazirani Theorem - I | Download |

24 | Lecture 24: Valiant-Vazirani Theorem - I | Download |

25 | Lecture 25: Amplified version of Valiant-Vazirani Theorem | Download |

26 | Lecture 26: Toda’s Theorem - I | Download |

27 | Lecture 27: Toda’s Theorem - II | Download |

28 | Lecture 28: Permanent and Determinant Functions | Download |

29 | Lecture 29: Permanent is hard for #P | Download |

30 | Lecture 30: Interactive Proofs | Download |

31 | Lecture 31: Graph Non-Isomorphism is in IP[2] | Download |

32 | Lecture 32: Set Lower Bound Protocol | Download |

33 | Lecture 33: MA is in AM | Download |

34 | Lecture 34: Sumcheck Protocol - I | Download |

35 | Lecture 35: Sumcheck Protocol - II | Download |

36 | Lecture 36: Parity not in AC0 - I | Download |

37 | Lecture 37: Parity not in AC0 - II | Download |

38 | Lecture 38 : Circuits with Counters | Download |

39 | Lecture 39 : Communication Complexity - I | Download |

40 | Lecture 40 : PCP Theorem | Download |

41 | Lecture 41 : Communication Complexity - II | Download |

Sl.No | Chapter Name | English |
---|---|---|

1 | Lecture 1: Introduction | Download To be verified |

2 | Lecture 2: NP Completeness | Download To be verified |

3 | Lecture 3: SAT is NP-complete | Download To be verified |

4 | Lecture 4: More on NP completeness | Download To be verified |

5 | Lecture 05: Hierarchy Theorems | Download To be verified |

6 | Lecture 06: Introduction to Space Complexity | Download To be verified |

7 | Lecture 07: Savitch’s Theorem | Download To be verified |

8 | Lecture 08: Immerman-Szelepscenyi Theorem | Download To be verified |

9 | Lecture 09: Polynomial Hierarchy | Download To be verified |

10 | Lecture 10: A PSPACE Complete Problem | Download To be verified |

11 | Lecture 11: More on Polynomial Hierarchy | Download To be verified |

12 | Lecture 12: Alternating Turing Machines | Download To be verified |

13 | Lecture 13: Equivalence of Quantifier and Oracle Based Definitions of Polynomial Hierarchy | Download To be verified |

14 | Lecture 14: Boolean Circuits | Download To be verified |

15 | Lecture 15: Shannon’s Theorem and Karp-Lipton-Sipser Theorem | Download To be verified |

16 | Lecture 16: Bounded Depth Circuit Classes | Download To be verified |

17 | Lecture 17: Kannan’s Theorem | Download To be verified |

18 | Lecture 18: Probabilistic Complexity | Download To be verified |

19 | Lecture 19: StrongBPP and WeakBPP | Download To be verified |

20 | Lecture 20: One-sided and Zero-sided Error Probabilistic Complexity Classes | Download To be verified |

21 | Lecture 21: Error Reduction for BPP | Download To be verified |

22 | Lecture 22: BPP in PH and Logspace Randomized Classes | Download To be verified |

23 | Lecture 23: Valiant-Vazirani Theorem - I | Download To be verified |

24 | Lecture 24: Valiant-Vazirani Theorem - I | Download To be verified |

25 | Lecture 25: Amplified version of Valiant-Vazirani Theorem | Download To be verified |

26 | Lecture 26: Toda’s Theorem - I | Download To be verified |

27 | Lecture 27: Toda’s Theorem - II | Download To be verified |

28 | Lecture 28: Permanent and Determinant Functions | PDF unavailable |

29 | Lecture 29: Permanent is hard for #P | PDF unavailable |

30 | Lecture 30: Interactive Proofs | PDF unavailable |

31 | Lecture 31: Graph Non-Isomorphism is in IP[2] | PDF unavailable |

32 | Lecture 32: Set Lower Bound Protocol | PDF unavailable |

33 | Lecture 33: MA is in AM | PDF unavailable |

34 | Lecture 34: Sumcheck Protocol - I | PDF unavailable |

35 | Lecture 35: Sumcheck Protocol - II | PDF unavailable |

36 | Lecture 36: Parity not in AC0 - I | PDF unavailable |

37 | Lecture 37: Parity not in AC0 - II | PDF unavailable |

38 | Lecture 38 : Circuits with Counters | PDF unavailable |

39 | Lecture 39 : Communication Complexity - I | PDF unavailable |

40 | Lecture 40 : PCP Theorem | PDF unavailable |

41 | Lecture 41 : Communication Complexity - II | PDF unavailable |

Sl.No | Language | Book link |
---|---|---|

1 | English | Not Available |

2 | Bengali | Not Available |

3 | Gujarati | Not Available |

4 | Hindi | Not Available |

5 | Kannada | Not Available |

6 | Malayalam | Not Available |

7 | Marathi | Not Available |

8 | Tamil | Not Available |

9 | Telugu | Not Available |