October 4, 2023
NP Completeness (CLRS, Ch. 34)
- Course Introduction.
- Syllabus.
- Problem classes: undecidable, intrinsically exponential,
intractable, polynomial.
- Abstract problems and decision problems. Reduction from optimization to decision problems. Example: SHORTEST UNWEIGHTED PATH.
October 5, 2023
- Encodings. Abstract and concrete problems. Reasonable encodings
- Formal Languages. Concrete problems and associated languages.
- Poly-time decision of languages. Definition of P.
- Verifiability. Example: HAMILTON
- Poly-time verifiability of languages. Definitiom of NP.
October 6, 2023
- Theorem: P is a subset of NP
- Reducibility. Example: verifier for HAMILTON
- Poly-time reducibility: characteristics of reduction functions.
- Theorem: if L1 < L2 and L2 is in P, then also L1 is in P
- Classes NPH and NPC.
- Corollary: if L is both in NPC and in P, then P=NP.
October 11, 2023
- The BC-SAT problem: definition.
- Poly-time verifier for BC-SAT
- Reduction from any language in NP to BC-SAT (Cook's Theorem, high level idea)
- The FORMULA-SAT (SAT) problem: definition.
- Non poly-time reduction from BC-SAT to SAT.
October 12, 2023
- Poly-time reduction from BC-SAT to SAT.
- The 3CNF-SAT problem: definition and reduction from BC-SAT.
- The CLIQUE problem: definition and reduction from 3CNF-SAT.
October 13, 2023
- The VERTEX-COVER and INDEPENDENT-SET problems: definitions and reductions from CLIQUE.
- The SUBSET SUM problem: definition and reduction from 3CNF-SAT.
October 18, 2023
- The SUBSET SUM problem: definition and reduction from 3CNF-SAT (contd)
Exercise session: NP-completeness
- Any NP language is decidable (in exponential time)
- The HALTING problem is in NPH
- If L1 < L2 and L2 is in NP, the L1 is in P.
- BC-TESTING is in NPH
- KNAPSACK is in NPH
October 19, 2023
Exercise session: NP-completeness
- Complementary languages and the class Co-Np
- DOMINATING SET is in NPH
- LONG-PATH is in NPH
- Construction of a solution starting from an oracle for the decision problem. Application to SUBSET_SUM.
October 20, 2023
Approximation Algorithms (CLRS, Cap. 35)
- Definition of approximation algoritm
- PTAS and FPTAS
- 2 approximation algorithm for MINIMUM VERTEX-COVER
October 25, 2023
- MIN VC approximation cannot be used for MAX-CLIQUE
- Greedy approaches to MIN VC without approximation guarantees
- MINIMUM WEIGHTED VERTEX COVER: fair pricing approach
- MINIMUM WEIGHTED VERTEX COVER: ILP rounding approach
October 26, 2023
- Primal-dual relationship between the two MWVC approaches
- Decision TSP: NP-completeness
- Inapprossimability of general TSP
- Decision TRIANGLE TSP (TSP with metric function): NP-completeness
- MST-based 2-approximation of TRIANGLE-TSP: algorithm
October 27, 2023
- MST-based 2-approximation of TRIANGLE-TSP: algorithm
- Christofides' 3/2-approximation of TRIANGLE-TSP: algorithm
November 2, 2023
- Christofides' 3/2-approximation of TRIANGLE-TSP: analysis
- State-of-the-art results on TRIANGLE-TSP and EUCLIDEAN-TSP
- SET-COVER: NP-completeness of decision problem and greedy algorithm.
- (ln n)-approximation bound
November 3, 2023
- SET-COVER: finer, charging-based analyisis
- An FPTAS for SUBSET-SUM: The exact exhaustive algorithm.
November 8, 2023
- An FPTAS for SUBSET-SUM: the list trimming algorithm and its analysis
- Definition of randomized algorithm and randomized approximation algorithm
November 9, 2023
- MAX-SAT. Definition, NP-completeness and 8/7 randomized approximation algorithm
Exercise session: Approximation Algorithms
- RESOURCE SELECTION: 2-approximation based on linear relaxation
- MAX-CUT: deterministic 2-approximation
- MAX-CUT: randomized 2-approximation
November 10, 2023
Exercise session: Approximation Algorithms
- Impossibility of an FPTAS for TRIANGLE TSP
- SUBSET-SUM: greedy 2-approximation
- INDEPENDENT SET: greedy max-degree approximation
- LOAD-BALANCING, 2-approximation and hints to 3/2-approximation
November 15, 2023
Number-Theoretic Algorithms (CLRS, Cap. 31)
- Divisibility: definitions and properties
- Greatest Common Divisor (gcd) and Bezout identity.
- Euclid algorithm: correctness and complexity.
- Extended Euclid Algorithm
November 16, 2023
- Modular arithmetic: the quotient structure Zn: group properties wrt sum
- The subset Z*n and group properties wrt multiplication
- Computation of the multiplicative inverse via EXTENDED-EUCLID
- Euler function, Euler theorem and Fermat little theorem
November 17, 2023
- Chinese Reminder Theorem: statement, proof, corollaries and applications
- Definition of cryptosystem and public key cryptosystem
- Communication and authentication protocols
November 22, 2023
- RSA details: computing public and private key. Recursive and iterative algorithms for modular exponentiation.
- RSA correctness: public and secret encoding are one the inverse of the other.
- RSA: complexity considerations
November 23, 2023
- RSA attacks.
- Decomposition of n=pq if p and q are very close.
tra loro.
- Attacks for choices of public keys sharing the same exponent.
- Attacks for choices of public keys sharing the same modulus.
- Attacks based on authentication. Digital digests and one-way hash functions.
- Introduction to primality.
November 24, 2023
- Base-a pseudoprimes and simple deterministic test for random inputs: probabilistic analysis based on Pomerance Theorem in the distribution of base-2 pseudoprimes.
- Compositeness certificates based on non base-a pseudoprimality or nontrivial square roots of unity.
November 29, 2023
- Miller-Rabin test: randomized search for a compositeness certificate.
- Miller-Rabin test: running time
- Miller-Rabin test: correctness analysis for non-Carmichael numbers.
Exercise session: Number-Theoretic Algorithms
- Integer division algorithm: computing quotient and reminder in quadratic time.
November 30, 2023
Exercise session: Number-Theoretic Algorithms
- Uniqueness of the multiplicative inverse
- Efficient computation of the least common multiple
- Integer linear combinations with two unknowns
- Bezout cofficients and solutions of integer linear combinations
December 1, 2023
Randomized Algorithms
- Introduction to randomized algorithms: Monte Carlo and Las Vegas algorithms.
- Analysis in expectation and in high probability
- Markov inequalities and their implications.
- Chernoff bounds on the tails of sums of bernoulli variables.
December 6, 2023
- Introduction to Randomized Quicksort: intuition on its computational efficiency
- Chernoff Bounds, Application 1: Analysis in high probability of Quicksort
December 7, 2023
- Average case complexity of Randomized Quicksort via Markov Inequality for bounded variables.
- Chernoff Bounds, Application 2: Correctness probability amplification
- Chernoff Bounds, Application 3: The Monte Carlo method
- Montecarlo counting for approximating pi = 3.1415...
December 13, 2023
- Min-cut on multigraphs: definition
- Contraction w.r.t. an edge
- Karger Min-Cut algorithm: description and running time
December 14, 2023
- Karger Min-Cut algorithm: probability of correctness and its amplification.
- Karger-Stein Min-Cut algorithm: description of the recursive strategy and running time , recurrence on correctness probability.
December 15, 2023
- Karger Min-Cut algorithm: probability of correctness and its amplification.
- Coupon Collecting: analysis in expectation and in high probability
- Occupancy problems (m balls into n boxes): maximum load of a box for the case m=n. Application to hashing under linear chaining.
December 20, 2023
- Occupancy problems: further results
Exercise session: Randomized Algorithms
- Coin unbiasing
- Partial coupon collection
December 21, 2023
Exercise session: Randomized Algorithms
- Randomized Selection (analysis in expectation)
- Randomized Selection (analysis w.h.p., sketch)
- Tail bound for sums of i.i.d. Geometric variables
December 22, 2023
Exercise session: Randomized Algorithms
- Montecarlo approximation to Maximum Independent Set
- Las Vegas approximation to Maximum Independent Set
- Las Vegas approximation to Max-3CNF SAT
- Las Vegas approximation to Vertex Cover
January 17, 2023
Flipped classroom presentations: Session 1
January 18, 2023
Flipped classroom presentations: Session 2
January 19, 2023
Flipped classroom presentations: Session 3
|
