September 30, 2024
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 1, 2024
- 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 2, 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 7, 2024
- 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 8, 2024
- Poly-time reduction from BC-SAT to SAT.
- The 3CNF-SAT problem: definition and reduction from BC-SAT.
- The CLIQUE problem: definition.
October 9, 2024
- The CLIQUE problem: reduction from 3CNF-SAT.
- The VERTEX-COVER and INDEPENDENT-SET problems: definitions and reductions from CLIQUE.
- The SUBSET SUM problem: definition.
October 14, 2024
- The SUBSET SUM problem: reduction from 3CNF-SAT
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 15, 2024
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 16, 2024
Approximation Algorithms (CLRS, Cap. 35)
- Definition of approximation algoritm
- PTAS and FPTAS
- 2 approximation algorithm for MINIMUM VERTEX-COVER
October 21, 2024
- 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 22, 2024
- 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 23, 2024
- MST-based 2-approximation of TRIANGLE-TSP: algorithm
- Christofides' 3/2-approximation of TRIANGLE-TSP: algorithm and analysis
October 28, 2024
- 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
October 29, 2024
- SET-COVER: finer, charging-based analyisis
- An FPTAS for SUBSET-SUM: The exact exhaustive algorithm.
October 30, 2024
- An FPTAS for SUBSET-SUM: the list trimming algorithm and its analysis
- Definition of randomized algorithm and randomized approximation algorithm
November 4, 2024
- 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 5, 2024
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 6, 2024
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 11, 2024
- 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 12, 2024
- Chinese Reminder Theorem: statement, proof, corollaries and applications
- Definition of cryptosystem and public key cryptosystem
- Communication and authentication protocols
November 13, 2024
- 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 18, 2024
- 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 19, 2024
- 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 20, 2024
- 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 25, 2024
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
November 26, 2024
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.
November 27, 2024
- Introduction to Randomized Quicksort: intuition on its computational efficiency
- Chernoff Bounds, Application 1: Analysis in high probability of Quicksort
December 2, 2024
- 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 3, 2024
- Min-cut on multigraphs: definition
- Contraction w.r.t. an edge
- Karger Min-Cut algorithm: description and running time
December 4, 2024
- 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.
|
