Topics in Algorithms and Complexity (M. Tech CS, 2 Year, 2020)
Topics in Algorithms and Complexity (M. Tech CS, 2 Year, 2020)
Instructor Arijit Ghosh
Description In this course we will cover various topics in Algorithms and Complexity.
Prerequisites Mathematical maturity of a finishing undergraduate student in mathematical sciences.
Class timings Tuesday, Thursday, and Saturday 15:30 - 16:30 hrs.
Syllabus
Randomized Algorithm
The Probabilistic Method
NP, NP-completeness, Reduction
Approximation Algorithms
References
[AB09] Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 2009.
[AS16] Noga Alon and Joel Spencer, The Probabilistic Method, 4th Edition, Wiley, 2016.
[BV04] Stephen Boyd and Lieven Vandenberghe, Convex Optimization, Cambridge University Press, 2004.
[B15] Sébastien Bubeck, Convex Optimization: Algorithms and Complexity, Foundations and Trends in Machine Learning, 2015.
[F99] Ehud Friedgut, Sharp thresholds of graph properties and the k-SAT problem, Journal of the American Mathematical Society, 12 (4): 1017–1054, 1999.
[FS11] Jacob Fox and Benny Sudakov, Dependent Random Choice, Random Structures & Algorithms, 38(1-2): 68–99, 2011.
[K06] Vladlen Koltun, Advanced Geometric Algorithms, Lecture Notes, Stanford University, 2006.
[MG07] Jiří Matoušek and Bernd Gärtner, Understanding and Using Linear Programming, Springer, 2007.
[KT06] Jon Kleinberg and Éva Tardos, Algorithm Design, Pearson, 2006.
[MR95] Rajeev Motwani and Prabhakar Raghavan, Randomized Algorithms, Cambridge University Press, 1995.
[MU17] Michael Mitzenmacher and Eli Upfal, Probability and Computing, Second Edition, Cambridge University Press, 2017.
[R19] Thomas Rothvoss, Probabilistic Combinatorics, Graduate Topics Course in Mathematics, UW Seattle, Winter 2019.
[V03] Vijay Vazirani, Approximation Algorithms, Springer, 2003.
[WS11] David P. Williamson and David B. Shmoys, The Design of Approximation Algorithms, Cambridge University Press, 2011.
[HP11] Sariel Har-Peled, Geometric Approximation Algorithms, AMS, 2011. (Preliminary version)
[HP18] Sariel Har-Peled, Randomized Algorithms, Lecture notes, UIUC, 2018.
[SB14] Shai Shalev-Shwartz and Shai Ben-David, Understanding Machine Learning: From Theory to Algorithms, Cambridge University Press, 2014. (Free copy)
Lecture details
Topics covered in Lecture 1
Discussed the outline of the course.
Topics covered in Lectures 2 and 3
Recalled basic results from probability theory
Random variables
Indicator random variables
Proving Markov's inequality using indicator random variables
Estimating size of maximum cuts in a graph (using linearity of expectation and indicator random variables)
Max-SAT problem (using linearity of expectation and indicator random variables)
A randomized algorithm for computing a minimum cut in graphs (using the chain rule of conditional probability)
References:
Topics covered in Lectures 4 and 5
Karger's minimum cut algorithm through the lens of Kruskal's algorithm
Faster implementation of Karger's randomized minimum cut algorithm
References:
Topics covered in Lectures 6 and 7
Galton-Watson process and minimum cut
Verifying matrix multiplications
Simple properties of Bernoulli, Binomial and Geometric distributions
Introduction to occupancy and coupon collector problems
References:
Topics covered in Lectures 8 and 9
Balls and bins
Birthday paradox via balls and bins
Bounding maximum load of a bin using combinatorial techniques
Coupon collector problem
Analysis of coupon collector problem using geometric random variable and Chebyshev's inequality
Better bound on the upper tail for the coupon collector problem
Expected number of comparisons in Quicksort algorithm (both random pivot case and random permutation case)
References:
Topics covered in Lectures 10, 11 and 12
A randomized algorithm for computing the median
Binary space partition and random permutation
Lower tail of the coupon collector problem via moment generating function
References:
Topics covered in Lectures 13 and 14
Moment generating function and it's basic properties
Chernoff bounds
Better concentration bound for +1/-1 case
Balancing vectors problems
Hoeffding’s inequality
References:
Topics covered in Lecture 15
First moment method
Max 3-SAT and maximum cut in graphs via the first moment method
Alteration method
Large independent sets in graphs using alteration
Improving independent set lower bound via random permutation and first moment method
References:
Additional references (non-examinable):
Topics covered in Lecture 16
Random Erdős–Rényi random graphs
Graphs with large girth via random graphs and alteration method
Second moment method
Threshold behavior in random graphs
References:
Additional references (non-examinable):
Friedgut's sharp thresholds of graph properties [F99]
Topics covered in Lecture 17
Lovász local lemma (LLL)
Applications of LLL
References:
Additional references:
Topics covered in Lectures 18 and 19
Introduction to Turán numbers of graphs
Turán numbers of bipartite graphs
Dependent random choice
References:
Additional references:
Fox-Sudakov's paper [FS11] on dependent random choice
Topics covered in Lectures 20 and 21
Optimization and decision versions of vertex cover and independent set problems.
Set cover and packing problems
Polynomial-time reductions
Difference between finding and verifying solutions
Efficient certification
NP, NP-completeness, and NP-hardness
NP-completeness proof of Independent set problem in graphs via 3-SAT
NP-completeness proof of Vertex cover problem via Independent set problem
P vs. NP problem
References:
Sections 8.1, 8.2, 8.3, and 8.4 from Chapter 8 in [KT06]
Topics covered in Lecture 22
Circuit satisfiability problem
Cook-Levin Theorem
Revisiting 7/8-approximation to Max-3-SAT problem
Max-SAT and maximum cut
2-approximation of Vertex cover problem via maximal matching
References:
Topics covered in Lecture 23
Approximation algorithm paradigm: Greedy algorithms and local search
Metric k-center problem and Travelling salesman problem
2-factor approximation for Metric k-center problem via Farthest point insertion heuristic
Hardness of approximation for Metric k-center problem via a reduction from dominating set
References:
Topics covered in Lectures 24 and 25
NP-completeness proof of Dominating Set problem via Vertex Cover problem
Traveling salesman problem (TSP)
Hardness of approximation for the general TSP
2-factor approximation for Metric TSP by modifying Prim's Minimum Spanning Tree algorithm
2-factor approximation for Metric TSP using Eulerian graph and double-tree algorithm
Christofides' 3/2-factor approximation algorithm for Metric TSP problem
References:
Topics covered in Lectures 26, 27, 28 and 29
Introduction to Integer Linear Programming (ILP) and Linear Programming (LP)
NP-hardness of ILP
Deterministic rounding algorithm for Vertex Cover and Set Cover problems
Randomized rounding algorithm for Set Cover problem
3/4-factor approximation algorithm for Max-SAT problem via randomized rounding
3/4-factor approximation algorithm for Max-SAT problem via non-linear randomized rounding
Derandomization
References: