Modules / Lectures
Module NameDownload
noc21_cs90_assignment_Week_0noc21_cs90_assignment_Week_0
noc21_cs90_assignment_Week_1noc21_cs90_assignment_Week_1
noc21_cs90_assignment_Week_10noc21_cs90_assignment_Week_10
noc21_cs90_assignment_Week_11noc21_cs90_assignment_Week_11
noc21_cs90_assignment_Week_2noc21_cs90_assignment_Week_2
noc21_cs90_assignment_Week_3noc21_cs90_assignment_Week_3
noc21_cs90_assignment_Week_4noc21_cs90_assignment_Week_4
noc21_cs90_assignment_Week_5noc21_cs90_assignment_Week_5
noc21_cs90_assignment_Week_6noc21_cs90_assignment_Week_6
noc21_cs90_assignment_Week_7noc21_cs90_assignment_Week_7
noc21_cs90_assignment_Week_8noc21_cs90_assignment_Week_8
noc21_cs90_assignment_Week_9noc21_cs90_assignment_Week_9
noc21_cs90assignment_Week12noc21_cs90assignment_Week12


Sl.No Chapter Name MP4 Download
1mod01lec01 - Introduction to Computational ComplexityDownload
2mod01lec02 - The Class PDownload
3mod01lec03 - The Class NPDownload
4mod01lec04 - The Class NP - Alternate DefinitionDownload
5mod01lec05 - Polynomial Time ReductionsDownload
6mod01lec06 - NP - CompletenessDownload
7mod02lec07 - Cook Levin Theorem: Part 1Download
8mod02lec08 - Cook Levin Theorem: Part 2Download
9mod02lec09 - More NP Complete ProblemsDownload
10mod02lec10 - Polynomial Hierarchy: Part 1Download
11mod02lec11 - Polynomial Hierarchy: Part 2Download
12mod02lec12 - Polynomial Hierarchy: Part 3Download
13mod03lec13 - Time Hierarchy TheoremDownload
14mod03lec14 - Introduction to Space ComplexityDownload
15mod03lec15 - NL-CompletenessDownload
16mod03lec16 - Savitch's TheoremDownload
17mod03lec17 - NL = co-NL: Part 1Download
18mod03lec18 - NL = co-NL: Part 2Download
19mod04lec19 - PSPACE CompletenessDownload
20mod04lec20 - Games and PSPACE CompletenessDownload
21mod04lec21 - Space Hierarchy TheoremDownload
22mod04lec22 - Ladner's TheoremDownload
23mod04lec23 - Oracle Turing MachinesDownload
24mod04lec24 - Polynomial Hierarchy Using OraclesDownload
25mod05lec25 - Baker-Gill-Solovay Theorem: Part 1Download
26mod05lec26 - Baker-Gill-Solovay Theorem: Part 2Download
27mod05lec27 - Randomized Complexity Classes: Part 1Download
28mod05lec28 - Randomized Complexity Classes: Part 2Download
29mod05lec29 - Randomized Complexity Classes: Part 3Download
30mod06lec30 - Randomized Complexity Classes: Part 4Download
31mod06lec31 - Comparison Between Randomized Complexity ClassesDownload
32mod06lec32 - BPP is in Polynomial HierarchyDownload
33mod06lec33 - Circuit Complexity: Part 1Download
34mod06lec34 - Circuit Complexity: Part 2Download
35mod07lec35 - Formal Definition of CircuitsDownload
36mod07lec36 - Hierarchy Theorem for Circuit SizeDownload
37mod07lec37 - Complexity Class : P/PolyDownload
38mod07lec38 - Karp-Lipton TheoremDownload
39mod07lec39 - Turing Machines That Take AdviceDownload
40mod07lec40 - Classes NC and ACDownload
41mod08lec41 - Parity Not in AC0: Part 1Download
42mod08lec42 - Parity Not in AC0: Part 2Download
43mod08lec43 - Adleman's TheoremDownload
44mod08lec44 - Polynomial Identity Testing and Bipartite Perfect Matching in RNCDownload
45mod09lec45 - Search Bipartite Perfect Matching is in RNC: Part 1Download
46mod09lec46 - Search Bipartite Perfect Matching is in RNC: Part 2Download
47mod09lec47 - Promise Problems and Valiant-Vazirani TheoremDownload
48mod09lec48 - Valiant Vazirani Theorem ContinuedDownload
49mod09lec49 - #P and the Complexity of CountingDownload
50mod10lec50 - Permanent is #P-Complete: Part 1Download
51mod10lec51 - Permanent is #P-Complete: Part 2Download
52mod10lec52 - Toda's Theorem: Part 1Download
53mod10lec53 - Toda's Theorem: Part 2Download
54mod11lec54 - Introduction to Communication Complexity: Part 1Download
55mod11lec55 - Introduction to Communication Complexity: Part 2Download
56mod11lec56 - Lower Bound TechniquesDownload
57mod11lec57 - Communication Complexity of RelationsDownload
58mod11lec58 - Monotone Depth Lower Bound for MatchingDownload
59mod12lec59 - Interactive ProofsDownload
60mod12lec60 - #3SAT is in IPDownload
61mod12lec61 - Public Coin Interactive Proofs and AM/MADownload
62mod12lec62 - Simulating Private Coins using Public CoinsDownload
63mod12lec63 - Summary and Concluding RemarksDownload

Sl.No Chapter Name English
1mod01lec01 - Introduction to Computational ComplexityDownload
Verified
2mod01lec02 - The Class PDownload
Verified
3mod01lec03 - The Class NPDownload
Verified
4mod01lec04 - The Class NP - Alternate DefinitionPDF unavailable
5mod01lec05 - Polynomial Time ReductionsPDF unavailable
6mod01lec06 - NP - CompletenessPDF unavailable
7mod02lec07 - Cook Levin Theorem: Part 1PDF unavailable
8mod02lec08 - Cook Levin Theorem: Part 2PDF unavailable
9mod02lec09 - More NP Complete ProblemsPDF unavailable
10mod02lec10 - Polynomial Hierarchy: Part 1PDF unavailable
11mod02lec11 - Polynomial Hierarchy: Part 2PDF unavailable
12mod02lec12 - Polynomial Hierarchy: Part 3PDF unavailable
13mod03lec13 - Time Hierarchy TheoremDownload
Verified
14mod03lec14 - Introduction to Space ComplexityPDF unavailable
15mod03lec15 - NL-CompletenessPDF unavailable
16mod03lec16 - Savitch's TheoremDownload
Verified
17mod03lec17 - NL = co-NL: Part 1PDF unavailable
18mod03lec18 - NL = co-NL: Part 2PDF unavailable
19mod04lec19 - PSPACE CompletenessPDF unavailable
20mod04lec20 - Games and PSPACE CompletenessPDF unavailable
21mod04lec21 - Space Hierarchy TheoremPDF unavailable
22mod04lec22 - Ladner's TheoremPDF unavailable
23mod04lec23 - Oracle Turing MachinesPDF unavailable
24mod04lec24 - Polynomial Hierarchy Using OraclesPDF unavailable
25mod05lec25 - Baker-Gill-Solovay Theorem: Part 1PDF unavailable
26mod05lec26 - Baker-Gill-Solovay Theorem: Part 2PDF unavailable
27mod05lec27 - Randomized Complexity Classes: Part 1PDF unavailable
28mod05lec28 - Randomized Complexity Classes: Part 2PDF unavailable
29mod05lec29 - Randomized Complexity Classes: Part 3PDF unavailable
30mod06lec30 - Randomized Complexity Classes: Part 4PDF unavailable
31mod06lec31 - Comparison Between Randomized Complexity ClassesPDF unavailable
32mod06lec32 - BPP is in Polynomial HierarchyPDF unavailable
33mod06lec33 - Circuit Complexity: Part 1PDF unavailable
34mod06lec34 - Circuit Complexity: Part 2PDF unavailable
35mod07lec35 - Formal Definition of CircuitsPDF unavailable
36mod07lec36 - Hierarchy Theorem for Circuit SizePDF unavailable
37mod07lec37 - Complexity Class : P/PolyPDF unavailable
38mod07lec38 - Karp-Lipton TheoremPDF unavailable
39mod07lec39 - Turing Machines That Take AdvicePDF unavailable
40mod07lec40 - Classes NC and ACPDF unavailable
41mod08lec41 - Parity Not in AC0: Part 1PDF unavailable
42mod08lec42 - Parity Not in AC0: Part 2PDF unavailable
43mod08lec43 - Adleman's TheoremPDF unavailable
44mod08lec44 - Polynomial Identity Testing and Bipartite Perfect Matching in RNCPDF unavailable
45mod09lec45 - Search Bipartite Perfect Matching is in RNC: Part 1PDF unavailable
46mod09lec46 - Search Bipartite Perfect Matching is in RNC: Part 2PDF unavailable
47mod09lec47 - Promise Problems and Valiant-Vazirani TheoremPDF unavailable
48mod09lec48 - Valiant Vazirani Theorem ContinuedPDF unavailable
49mod09lec49 - #P and the Complexity of CountingPDF unavailable
50mod10lec50 - Permanent is #P-Complete: Part 1PDF unavailable
51mod10lec51 - Permanent is #P-Complete: Part 2PDF unavailable
52mod10lec52 - Toda's Theorem: Part 1PDF unavailable
53mod10lec53 - Toda's Theorem: Part 2PDF unavailable
54mod11lec54 - Introduction to Communication Complexity: Part 1PDF unavailable
55mod11lec55 - Introduction to Communication Complexity: Part 2PDF unavailable
56mod11lec56 - Lower Bound TechniquesPDF unavailable
57mod11lec57 - Communication Complexity of RelationsPDF unavailable
58mod11lec58 - Monotone Depth Lower Bound for MatchingPDF unavailable
59mod12lec59 - Interactive ProofsPDF unavailable
60mod12lec60 - #3SAT is in IPPDF unavailable
61mod12lec61 - Public Coin Interactive Proofs and AM/MAPDF unavailable
62mod12lec62 - Simulating Private Coins using Public CoinsPDF unavailable
63mod12lec63 - Summary and Concluding RemarksPDF unavailable


Sl.No Language Book link
1EnglishNot Available
2BengaliNot Available
3GujaratiNot Available
4HindiNot Available
5KannadaNot Available
6MalayalamNot Available
7MarathiNot Available
8TamilNot Available
9TeluguNot Available