⏱️ Algorithms & Complexity Notes
Contents
- 01 Abstract Problem
- 02 High-Level Algorithms and Polynomial Time
- 03 Degrees of uncertainty
- 04 Polynomial Time
- 05 Closure of P under Boolean combinations
- 06 Nondeterminism by certificates
- 07 Closure of NP under positive Boolean combination
- 08 Polynomial-time reductions
- 09 NP-hardness
- 10 History of Computing
- 11 How much harder is solving as compared to just verifying ?
- 12 P versus NP
- 13 Hardness for the class NP
- 14 The first NP-hard problem
- 15 A Simple reduction - Almost SAT
- 16 Algorithmic Paradigm to cope with NP-hardness
- 17 The Stable Matching Problem
- 18 Stable Matching for allocations within one group
- 19 What about Stable Matching for allocations between two groups ?
- 20 How fast can we solve the Stable Matching Problem ?
- 21 Gale-Shapley Algorithm for STABLE MATCHING
- 22 What are greedy algorithms ?
- 23 Dijkstra’s Algorithm
- 24 Minimum Spanning Trees
- 25 Minimum Spanning Trees via Prim’s Algorithm
- 26 Minimum Spanning Trees via Kruskal’s algorithm
- 27 The Reverse-Delete algorithm for finding MST
- 28 The Interval Scheduling problem
- 29 A harder variant of scheduling
- 30 Greedy algorithm for Partitioning problem
- 31 What is dynamic programming ?
- 32 Interval Scheduling problem (without weights)
- 33 The Weighted Interval Scheduling problem
- 34 Bellman-Ford Algorithm
- 35 The Subset Sum Problem
- 36 Max Independent Set problem on Trees
- 37 What is divide and conquer ?
- 38 The MergeSort algorithm
- 39 Two methods to solve recurrences
- 40 Counting Number of Inversions
- 41 How fast can we multiply two n-digit numbers ?
- 42 Uniform vs No-Uniform models
- 43 CNF’s
- 44 A first non-uniform class
- 45 Undecidability
- 46 Boolean Circuits
- 47 The EXACT functions
- 48 A non-symmetric example - Inequality
- 49 Composing constructions
- 50 Depth of a circuit
- 51 Formulas