September 28, 2021
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.
September 30, 2021
 Encodings. Abstract and concrete problems. Reasonable encodings
 Formal Languages. Concrete problems and associated languages.
 Polytime decision of languages. Definition of P.
 Verifiability. Example: HAMILTON
 Polytime verifiability of languages. Definitiom of NP.
October 1, 2021
 Theorem: P is a subset of NP
 Reducibility. Example: verifier for HAMILTON
 Polytime 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.
 BCSAT: definition
October 5, 2021
 The BCSAT problem: definition.
 Cook's Theorem 1) Polytime verifier for BCSAT
2) Reduction from any language in NP to BCSAT (highlevel idea).
 The FORMULASAT (SAT) problem: definition.
 Non polytime reduction from BCSAT to SAT.
October 7, 2021
 Polytime reduction from BCSAT to SAT.
 The 3CNFSAT problem: definition and reduction from BCSAT.
 The CLIQUE problem: definition and reduction from 3CNFSAT.
October 8, 2021
 The VERTEXCOVER and INDEPENDENTSET problems: definitions and reductions from CLIQUE.
 The SUBSET SUM problem: definition and reduction from 3CNFSAT.
October 12, 2021
 The SUBSET SUM problem: definition and reduction from 3CNFSAT (cont'd)
Exercise session: NPcompleteness
 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.
 BCTESTING is in NPH
 KNAPSACK is in NPH
October 14, 2021
Exercise session: NPcompleteness
 Complementary languages and the class CoNp
 DOMINATING SET is in NPH
 LONGPATH is in NPH
 Construction of a solution starting from an oracle for the decision problem. Application to SUBSET_SUM.
October 15, 2021
Approximation Algorithms (CLRS, Cap. 35)
 Definition of approximation algoritm
 PTAS and FPTAS
 2 approximation algorithm for MINIMUM VERTEXCOVER
October 21, 2021
 MIN VC approximation cannot be used for MAXCLIQUE
 Greedy approaches to MIN VC without approximation guarantees
 MINIMUM WEIGHTED VERTEX COVER: fair pricing approach
 MINIMUM WEIGHTED VERTEX COVER: ILP rounding approach
October 22, 2021
 Primalduale relationship between the two MWVC approaches
 Decision TSP: NPcompleteness
 Inapprossimability of general TSP
 Decision TRIANGLE TSP (TSP with metric function): NPcompleteness
 MSTbased 2approximation of TRIANGLETSP: algorithm
October 26, 2021
 MSTbased 2approximation of TRIANGLETSP: algorithm
 Christofides' 3/2approximation of TRIANGLETSP: algorithm
October 28, 2021
 Christofides' 3/2approximation of TRIANGLETSP: analysis
 Stateoftheart results on TRIANGLETSP and EUCLIDEANTSP
 SETCOVER: NPcompleteness of decision problem and greedy algorithm.
 (ln n)approximation bound
October 29, 2021
 SETCOVER: finer, chargingbased analyisis
 An FPTAS for SUBSETSUM: The exact exhaustive algorithm.
November 2, 2021
 An FPTAS for SUBSETSUM: the list trimming algorithm and its analysis
 Definition of randomized algorithm and randomized approximation algorithm
November 4, 2021
 MAXSAT. Definition, NPcompleteness and 8/7 randomized approximation algorithm
Exercise session: Approximation Algorithms
 RESOURCE SELECTION: 2approximation based on linear relaxation
 MAXCUT: deterministic 2approximation
 MAXCUT: randomized 2approximation
November 5, 2021
Exercise session: Approximation Algorithms
 Impossibility of an FPTAS for TRIANGLE TSP
 SUBSETSUM: greedy 2approximation
 INDEPENDENT SET: greedy maxdegree approximation
 LOADBALANCING, 2approximation and hints to 3/2approximation
November 9, 2021
NumberTheoretic Algorithms (CLRS, Cap. 31)
 Divisibility: definitions and properties
 Greatest Common Divisor (gcd) and Bezout's identity.
 Euclid's algorithm: correctness and complexity.
 Extended Euclid's Algorithm
November 11, 2021
 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 EXTENDEDEUCLID
 Euler's function, Euler's theorem and Fermat's little theorem
November 12, 2021
 Chinese Reminder Theorem: statement, proof, corollaries and applications
 Definition of cryptosystem and public key cryptosystem
 Communication and authentication protocols
November 16, 2022
 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, 2021
 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 oneway hash functions.
 Introduction to primality.
November 19, 2021
 Basea pseudoprimes and simple deterministic test for random inputs: probabilistic analysis based on Pomerance Theorem in the distribution of base2 pseudoprimes.
 Compositeness certificates based on non basea pseudoprimality or nontrivial square roots of unity.
November 23, 2021
 MillerRabin test: randomized search for a compositeness certificate.
 MillerRabin test: running time
 MillerRabin test: correctness analysis for nonCarmichael numbers.
Exercise session: NumberTheoretic Algorithms
 Integer division algorithm: computing quotient and reminder in quadratic time.
November 25, 2021
Exercise session: NumberTheoretic 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
Randomized Algorithms
 Introduction to randomized algorithms: Monte Carlo and Las Vegas algorithms.
November 26, 2021
 Analysis in expectation and in high probability
 Markov inequalities and their implications.
 Chernoff bounds on the tails of sums of bernoulli variables.
