Status: December 15, 2004

Final exam due December 15
(deadline extended by 15 hours and 1 minute!)

Instructor:

Schedule:

Contents:

This graduate course in CS deals with advanced analysis of algorithms and data structures. It should be considered as a course extending the material presented in CIS 610 and partly in CIS 665.

Course Description: This course is dealing with two very important topics in modern algorithms and complexity theory: approximation algorithms and randomized algorithms.

Approximation algorithms have been developed in response to the impossibility of solving many problems exactly. In the case of NP-hard problems, we sacrifice optimality in favor of a "good" solution that can be computed efficiently. Trading-off optimality in favor of tractibility is the paradigm of approximation algorithms. Still, approximation algorithms are important also for problems that have polynomial-time exact algorithms - in that case our aim is to achieve much faster algorithms, or algorithms satisfying certain desired properties (for example, being able to be executed in distributed fashion).

Randomized algorithms has proven itself to be a useful resource for developing provably efficient algorithms and it has been certainly among the central discoveries in the foundations of computer science over the last three decades. Randomized algorithms are algorithms that make random choices as they proceed, and have had a fundamental impact on several areas of computer science (e.g., distributed algorithms, cryptography, resource allocation, approximation algorithms).

Nowadays both, approximation and randomized algorithms belong to the basic tools of modern algorithms theory and this course will explore a collection of basic results and techniques for analyzing approximation and randomized algorithms. Even though most of the algorithms discussed arose from practical applications, emphasis will be mostly on theoretical aspects of the algorithms.

More detailed presentation of the topics explored in the course will be available here soon.

Prerequisite: CIS 610 or the permission of the instructor

Grading and Policies:

Lectures:

1. September 3, 2004
   
   • Lecture notes 1 (in postscript format)
   • Discussion on the syllabus, requirements, topics to be covered, references, and the (lack of the) textbooks.
   • Why randomized algorithms and what are randomized algorithms?
   • Why approximation algorithms and what are approximation algorithms?
   • Simple examples of randomized algorithms and their analysis
     • randomized Quick-Sort
     • randomized selection
   • Basics in probability theory (see Handout 1)
     • Probability, probability distribution, random variables, expected values, etc
     • Markov inequality
     • Chebyshev inequality
   • Further examples of randomized algorithms:
     • Max-cut: polynomial-time and constant approximation ratio
     • Min-cut: efficient algorithm without using max-flow
2. September 10, 2004
   
   • Lecture notes 2 (in postscript format)
   • Improving the running-time of min-cut algorithm via random sampling (algorithm due to Karger and Stein).
   • Randomized selection - refinment of randomized Quick Sort for which the expected number of comparisons is 4 n + o(n).
   • A better randomized selection - random sampling leads to the expected number of comparisons 1.5 n + o(n).
     • Introducing Chernoff bound.
3. September 17, 2004
   
   • Lecture notes 3 (in postscript format)
   • Continuing the analysis of randomized selection algorithm that uses random sampling approach and has the expected number of comparisons 1.5 n + o(n) (this number of comparisons is actually/also with very high probability).
   • Using Chernoff bounds:
     • Two variants of Chernoff bound:
       • Let 0 < p < 1. Let X₁, X₂, ... X_n be independent 0-1 random variables with Pr[X_i = 1] = p for every i. Let X = X₁ + X₂ + ... + X_n. Then, for every t > 0, we have
         Pr[X > E[X] + t] < e^{-2 t2/n}
         Pr[X < E[X] - t] < e^{-2 t2/n}
         
       • Let X₁, X₂, ... X_n be independent 0-1 random variables. For every i, let Pr[X_i = 1] = p_i. Let X = X₁ + X₂ + ... + X_n. Then, for every e > 0, we have
         
         Pr[X > (1+e) E[X]] ≤ (e^e/(1+e)^1+e)^E[X]
         Moreover, if 0 < e < 1, then we have
         Pr[X > (1+e) E[X]] ≤ e^{-e2 E[X] / 3}
         Pr[X < (1-e) E[X]] ≤ e^{-e2 E[X] / 2}
         
     • Proof of a Chernoff bound.
     • Simple applications of Chernoff bound and why they're better than Markov (if we can use them!).
   • The secretary problem: a simple online problem and its analysis (we'll find the best secretary with probability about 1/e ... and this is the best we can hope for!).
   • Finding a long path in an undirected graph:
     • Finding the longest path is NP-hard.
     • A randomized algorithm that for a given graph G with n vertices finds in a polynomial-time a path of length W(log n / loglog n) - if no such path exists, then the algorithm will find the longest path.
     • A randomized algorithm that for a given graph G with n vertices finds in a polynomial-time a path of length W(log n) - if no such path exists, then the algorithm will find the longest path (the algorithm is from N. Alon, R. Yuster, and U. Zwick, Color-coding, Journal of the ACM, 42(4): 844-856, July 1995).
     • Historical note: For quite a long time the result above was the strongest bound known for the problem, and only recently we have seen two major improvements: Bjorklund and Husfeldt (SIAM J. Comput., 32(6):1395-1402, 2003) designed a polynomial-time algorithm that finds a path of length W(log² n / loglog n) and very recently, Gabow (STOC, pp. 407-416, 2004). made a major improvement and obtained a polynomial-time algorithm that finds a path of length e^{W√(log n / loglog n)}.

4. September 24, 2004
   
   • Finishing the analysis of the randomized algorithm that for a given graph G with n vertices in polynomial-time either finds a path of length W(log n) or finds the longest path (the algorithm is from N. Alon, R. Yuster, and U. Zwick, Color-coding, Journal of the ACM, 42(4): 844-856, July 1995).
   • Balls and bins, Coupons, Birthdays, and their applications.
     • Describing a generic model of balls-and-bins games (called also sometime the occupancy problems): throwing m balls into n bins independently and uniformly at random.
     • Discussing basic applications: hashing, distributed load balancing, etc.
   • Coupon collector: how many balls must be thrown to have all bins with at least 1 ball.
     • After throwing m balls into n bins, the expected number of empty bins is n (1-1/n)^m ~ n e^-m/n.
     • Probability that there exists an empty bin is at most n (1-1/n)^m ≤ n e^-m/n.
       • If m > 2 n ln(n) then we don't expect to have any empty bin (even with high probability, probability at least 1 - 1/n).
     • Expected number of balls is n H_n = n ln n + O(n).
     • During this analysis we use random variables having geometric probability distribution.
   • Birthday paradox: how many balls must be thrown to have at least one bin with at least 2 balls.
     • If we throw m << n balls, then the expected number of bins with load ≥ 2 is m²/n.
     • If m ≥ √ n then we expect to have at least one bin with at least 2 balls.
   • Analysis of the maximum-load in the system.
     • Applications in hashing, load balancing, etc.
     • Maximum-load for m=n is equal to the running-time for the search in the hashing with chaining scheme (assuming random hash function is used).
     If n=m then the maximum-load is O(ln n / lnln n) with high probability. ("Easy" proof for the upper bound uses Chernoff bound (2nd variant from the previous lecture).)
     • If we are interested in the expected maximum load, then Gonnet proved that the expected chain length is exactly G^(-1)(n) + 1.5 + o(1), where G is the Euler Gamma (factorial) function (for example, G(n) = (n-1)! for all integers n). It is known that G^(-1)(n) = (1+o(1)) ln n / lnln n.
     • The analysis of the case n=m can be easily extended to the case when m < n log n. In that case, the maximum load is O(ln n / ln(n ln n / m)) with high probability.
     • If m > n ln n then the maximum load is O(m/n) with high probability ("easy" proof for the upper bound follows from Chernoff inequality).
   • Two choices are always better than one (but three are not really better than two).
     • Analysis of the two-random choices processes - for each ball two random locations are available (and the ball can "choose" which of the two location she will go to).
     • Online variant (due to Y. Azar, A. Broder, A. Karlin, and E. Upfal, Balanced allocations, SIAM J. Comput., 29(1):180-200, 1999):
       • We allocate the balls into bins sequentially, one ball after another. For each ball, choose 2 locations independently and uniformly at random, and place the ball into the lighter of the two chosen bins; if tie, then choose either arbitrarily or at random.
       • If n balls are allocated into n bins, then the maximum load is log₂log₂n + Q(1) with high probability.
       • Application to hashing: we have a static dictionary that uses two random hash function and performs the search in O(loglog n) time with high probability.
       • If we do more than 2 random choices then the improvement is very little: for d random choices, d > 1, the maximum load is log₂log₂n / log₂d + Q(1) with high probability.
       • If the number of balls is not neccessarily n, then the maximum load is m/n + log₂log₂n + Q(1) with high probability (P. Berenbrink, A. Czumaj, A. Steger, and B. Vöcking, Balanced allocations: the heavily loaded case, STOC, pp. 745-754, 2000.)
     • A surprising improvement is possible if we run the process in a asymmetric way (B. Vöcking, How asymmetry helps load balancing, Journal of the ACM, 50(4):568-589, 2003):
       • for every ball we select 2 bins, one at random out of the first n/2 bins, and another at random out of the other n/2 bins.
       • then, we place the ball into the lighter of the 2 selected bins.
       • however, if there is a tie, then we always place the ball into the bin from the first n/2 bins.
       • The maximum load is 0.69 log₂log₂n + Q(1) with high probability.
     • Offline variant: we first choose 2 random possible locations for every ball and then decide where the balls are to be allocated.
       • Maximum-flow approach can be used to find the best allocation (P. Sanders, S. Egner, and J. H. M. Korst, Fast concurrent access to parallel disks, Algorithmica, 35(1): 21-55, 2003).
       • If m > c n log n for certain constant c, then with high probability it is possible to allocate the balls so that the maximum load is (the ceiling of) m/n - which is a "perfect allocation" (Czumaj, Riley, and Scheideler, Perfectly balanced allocation, RANDOM, pp. 240-251, 2003.)
       • For every m and n, with high probability one can find an allocation of the balls so that the maximum load is (the ceiling of) m/n + 1 - which is at most 1 off the "perfect allocation."
       • Application to hashing: we have a static dictionary that uses two random hash function and performs the search in O(1) time (actually, at most 4 lookups with high probability).
5. October 1, 2004
   • Lecture notes 5 (in postscript format)
   • Finishing the analysis of the on-line scheme of Azar et al.
     • Sketch of the analysis: using (inductive) conditioning we can eliminate dependency and reduce everything to concentration (Chernoff) bounds.
   • Brief discussion on the off-line schemes:
     • Structure theorem: for a given choices for all the balls, the max-load is equal to the maximum over all subsest of the balls B of S(B)/|B|, where S(B) denotes the number of balls whose both selected locations are in set B.
     • With the Structure theorem, everything can be reduced to the estimation of some basic properties of binomial distribution (that can be analyzed using Chernoff bound).
   • Universal hash families and 2-universal classes of hash functions (see Chapters 8.4.1, 8.4.2, 8.4.3 in the book »Randomized Algorithms« by R. Motwani and P. Raghavan, Cambridge University Press, Cambridge, UK, 1995).
     • Dynamic dictionaries using 2-universal classes of hash functions.
     • Construction of 2-universal classes of hash functions of size O(m²), where m is the size of the universum.
       • H = {h_a,b : {0,1,...,m} --> {0,1,,,,,n}},
         where h_a,b(x) = ((ax + b) mod p) mod n, for a prime number p, p ≥ m (by Bertrand's postulate, there always exists a prime p, m ≤ p ≤ 2m)
     • Proof that this class of functions is 2-universal.
   • Static dictionary with O(1)-wost-case time access using 2-universal classes of hash functions (M.L. Fredman, J. Komlós, and E. Szemerédi, Storing a sparse table with O(1) worst case access time, Journal of ACM, 31:538-544, July 1984; for a more reader-friendly description, see either Chapter 8.5 in »Randomized Algorithms« by R. Motwani and P. Raghavan, 1995, or Chapter 11.5 in »Introduction to Algorithms« by T.H. Cormen, C.E. Leiserson, R.L. Rivest, and C. Stein, The MIT Press 2001).
     • Two-level hashing.
   • Bloom filters
     • What they are, what is their use, and some basic properties.
   • (Very briefly) introducing to Linear Programming and its complexity.
     • Linear programming is in P (has polynomial-time solution)
       • this breakthrough result (that uses the ellipsoid method) is due to L. Khachiyan, A polynomial algorithm in linear programming, Soviet Mathematics Doklady, 20:191-194, 1979; for an excellent presentation of Khachiyan's technique, see the book by M. Grötschel, L. Lovász, and A. Schrijver, »Geometric Algorithms and Combinatorial Optimization«, Springer, Berlin, 1988.
       • a few years after, N. Karmarkar (A new polynomial-time algorithm for linear programming, Combinatorica, 4:373-395, 1984) presented an efficient algorithm (using the interior point method) for linear programming (the algorithm due to Khachiyan hasn't been very practical).
       • Simplex method (due to Dantzig), though has the exponential worst-case running time, is still the method of choice for practical applications.
       • It has been known for a long time that simplex algorithm has "typically" polynomial-time. This notion has been recently formalized and extended by D.A Spielman and S.-H. Teng, Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time, Journal of the ACM, 51(3): 385-463, May 2004.
       • Next class will begin with a randomized algorithm for linear programming that uses geometric properties of the problem: to solve the problem with n variables and m constraints we will need expected time O(m n!), which is linear(!) for constant n.
6. October 8, 2004
   • Lecture notes 6 (in postscript format)
   • Randomized algorithm for linear programming that uses geometric properties of the problem: to solve the problem with n variables and m constraints we will need expected time O(m n!), which is linear(!) for constant n.
   • Randomized rounding technique on an example of Max-SAT problem.
   • Randomized algorithm for Max-SAT
     • Simple algorithm that randomly (i.u.r.) selects the value of every variable (worst-case expected cost ≥ 1/2 of the optimal).
     • Randomized rounding algorithm:
       • Write an integer program and solve (in polynomial-time) its LP relaxation.
       • For every i independently: if x^*_i is the solution to the LP for variable x_i then set x_i=1 with probability x^*_i and set x_i=0 otherwise.
       • Expected cost of this algorithm is at least 1-1/e times the optimal.
     • Combine the two algorithms above.
       • Run Algorithm 1 and Algorithm 2 - independently - and either return a better solution or return a random one (ouf of the two).
       • Expected cost of the algorithm is at least 3/4 times the optimal.
   • Randomized rounding approach for set cover (with weights).
     • Integer programming formulation of set cover.
     • Solving (in polynomial-time) LP relaxation.
     • Let x^*_i be the solution to the LP for variable x_i.
       • Repeat while there is at least one uncovered set:
         • If x_i=0 then set x_i to 1 with probability x^*_i.
     • The algorithm will need at most O(log n) rounds to cover all the sets.
     • Its expected cost is at most O(log n) times the optimal.
7. October 15, 2004
   • Metric embeddings (for more details, see Lecture Notes 7).
8. October 22, 2004
   • TSP, metric TSP, and Euclidean (geometric) TSP
     • TSP is NP-hard - and it's even NP-hard to achieve any approximation guarantee
     • Metric TSP is NP-hard, it has no PTAS unless P=NP, but it has a 1.5-approximation algorithm (due to Christofides)
       • 2-approximation algorithm
       • Christofides algorithm
     • Euclidean TSP in R^d for a constant d has a PTAS (algorithm will be described in the next lecture)
     • For d = log n / ε, the Euclidean TSP in R^d has no PTAS (unless P=NP)
   • Rounding algorithm (but this time deterministic rounding) for vertex cover - 2-approximation bound
     • This algorithm works also for the weighted version of the vertex cover problem, in which each vertex has a nonnegative weight and the objective is to minimize the total weight of the vertex cover
     • Vertex cover is not approximable within 1.1666 unless P=NP
   • Lattice-Approximation Problem: for a given n × n matrix A with entries in [0,1], and for a given column n-vector p with entires in [0,1], find a column n-vector q with entries in {0,1} (binary) that minimizes || A · (p-q) ||₂
     • Randomized rounding leads to a polynomial-time algorithm that finds q such that || A · (p-q) ||₂ < √(n ln n) with probability at least 1-O(1/n)
   • Spanners and their basic applications
   • Euclidean spanners that are light, sparse, have low maximum-degree, and can be constructed efficiently:
     • For every constant d, for every positive constant ε, for any set P of n points in R^d, one can find
       • in time O(n log n)
       • a (1+ε)-spanner
       • that has maximum-degree O(1) and
       • whose weight is upper bound by a constant (depending on d and ε) times the weight of the MST for P
   • Application of spanners to design an O(n log n)-time algorithm that for a set of n points P in Euclidean space R^d (for a constant d) finds a (1+ε)-approximation of the MST for P
9. October 29, 2004
   • Lecture notes 9 (in postscript format)
   • Spanners and geometric spanners.
   • Simple geometric construction of spanners based on sector (cone) decomposition that for any set of n points on a plane and for every positive constant e constructs a (1+e)-spanner that has O(n) edges.
   • Using spanners to approximate TSP - every (1+e)-spanner has an (1+e)-approximation of TSP.
   • PTAS for Euclidean TSP - algorithm due to Arora (Journal of the ACM, 45(5), 753-782, 1998) (use also this link), and Rao and Smith (STOC 1998).
   • Introduction to clustering problems in metric spaces: min-sum clustering and its connection to the balanced k-median problem.
10. November 5, 2004
    • Lecture notes 10 (in postscript format)
    • Clustering problems in metric spaces
      • (V,μ) - metric space with set of n points V and the distance function μ
      • k-center problem: find a set of k centers c₁, c₂, ..., c_k in V and a partition V into k sets V₁, ..., V_k such that the following sum is minimized:
                    max_{i=1, ..., k}   max_{u in Vi}   μ(u,c_i)
      • k-median problem: find a set of k centers c₁, c₂, ..., c_k in V and a partition V into k sets V₁, ..., V_k such that the following sum is minimized:
                    ∑_i=1^k   ∑_{u in Vi}   μ(u,c_i)
      • k-means problem: find a set of k centers c₁, c₂, ..., c_k in V and a partition V into k sets V₁, ..., V_k such that the following sum is minimized:
                    ∑_i=1^k   ∑_{u in Vi}   (μ(u,c_i))²
      • Min-sum clustering problem: find a partition V into k sets V₁, ..., V_k such that the following sum is minimized:
                    ∑_i=1^k   ∑_{u, v in Vi}   μ(u,v)
      • Balanced k-median problem: find a set of k centers c₁, c₂, ..., c_k in V and a partition V into k sets V₁, ..., V_k such that the following sum is minimized:
                    ∑_i=1^k   |V_i|   ∑_{u in Vi}   μ(u,c_i)
      • All these clustering problems are known to be NP-hard, even in metric case.
      • The first three problems have constant-factor approximation polynomial-time algorithms.
      • The last two problems, min-sum clustering and balanced k-median, seem to be significantly harder and no constant factor polynomial-time algorithms are known for them.
      • There is PTAS for min-sum clustering for the most basic case when k=2 ( due to Indyk, 1999). This algorithm explores the well-known duality of the min-sum clustering problem and the Max-Cut problem.
      • There is an algorithm that in time n^O(k) finds an optimal solution for the balanced k-median problem (due to Guttman-Beck and Hassin, 1998).
      • Since a solution to balanced k-median approximates to within a constant factor of 2 a solution to min-sum clustering, the result above implies also the existence of a 2-approximation algorithm for min-sum clustering with the running time of n^O(k).
      • Bartal, Charikar, and Raz (2001) gave the best so-far approximation algorithm for both these problems: for every e>0, the algorithm runs in time n^{O(1 + 1/e)} and returns a O((1/e) (log n)^{1 + e})-approximation of the optimal solution.
      • Fernandez de la Vega, Karpinski, Kenyon, and Rabani (2003) gave a (1+e)-approximation for the min-sum clustering problem that runs in time O(n^3k   2^O((1/e)k2)).
    • Detailed discussion of the approximation algoithm due to Bartal, Charikar, and Raz (STOC, 2001) for the balanced k-median problem.
      • Main idea:
        • Balanced k-median can be reduced to σ-HSTs -> an c-approximation for balanced k-median in σ-HST yields an O(c σ log_σ n)-approximation algorithm in metric space (this result is a combination of the result by Bartal FOCS 1996 and STOC 1998, and by Fakcharoenphol, Rao, and Talwar, STOC 2003)
        • Dynamic programming algorithm for balanced k-median in σ-HST that retursn a O(1)-approximation and requires time n^{O(log n)}.
        • By doing some approximation in the dynamic programming approach, we can obtain a O(1)-approxiamtion algorithm with the running time n^{O(log log n / log σ)}.
        • By setting σ = O(log^e n), we will obtain a polynomial-time (n^{O(1 + 1/e)}-time) algorithm for balanced k-median that achieves the approximation guarantee of O((1/e) (log n)^{1 + e}).

    DON'T miss the 1st Annual Symposium: Pioneers of Computing that will be held in NJIT on Monday, November 8, 2004.
    Don't miss the oportunity to see very distinguished speakers who will be talking in NJIT about their research:

    • Amir Pnueli (NYU and Weizman, ACM Turing Award winner (1996))
    • David S. Johnson (AT&T ... don't you want to see the famous author of Computers and Intractability : A Guide to the Theory of NP-Completeness )
    • George Miller (Princeton, National Medal of Science (1991))
11. November 12, 2004
    • Part II of Lecture notes 11 (in postscript format) - Part I will be added here (hopefully) soon.
    • Random graphs
      • for additional information on random graphs, see »Random Graphs« by Béla Bollobas, Cambridge University Press; 2nd edition, 2001 ... actually, this book contains almost all what is known on this topic
      • ... if you want to know more than all, then you can also check another book »Random Graphs« by Svante Janson, Tomasz Luczak, Andrzej Rucinski, Wiley-Interscience, 2000.
    • Basic properties - triangle free random graphs (are when p < c/n for certain constant c) and the clique number in random graphs (which is Q(log n) for p=1/2).
    • Further basic properties: threshold for connectivity, Hamiltonicity, and matching - all are p = c ln n / n for certain constant c.
    • Threshold for the first cycle, (p=c/n for certain constant c), and the evolution of random graphs.
    • Markov chains - basic (and very incomplete) introduction
    • Markov chains in computer science: Random walks in undirected graphs.
    • Cover time and hitting times of random walks.
    • Cover times of complete graphs (Q(n log n)), of the line (Q(n²)), of the lollipop graph (Q(n³)).
    • Proof of the classical result: Cover time of any graph is at most 2 m (n-1).
    • Using random walks in undirected graphs: randomized algorithm for s-t undirected connectivity with O(log n) - space.
    • ... very recently, Omer Reingold solved a long standing open question and gave a deterministic algorithm for s-t undirected connectivity with O(log n) - space. (No, we didn't discuss the algorithm from that paper.)
    • For much more detailed exposition of the concept of random walks see the classical book on this topic by "Random Walks and Electric Networks" by P. G. Doyle and J. L. Snell.
12. November 19, 2004   -   The IBM Research / NYU / Columbia Theory Day
    • No class - instead all students are encouraged to attend The IBM Research | NYU | Columbia Theory Day that will be held at Courant Institute of Mathematical Sciences, New York University, 251 Mercer Street, Auditorium 109, New York.
    • Program
        9:30 - 10:00     Coffee and bagels
      10:00 - 10:55     Prof. Sampath Kannan (University of Pennsylvania):
                                Algorithms for Streamed Graphs and Streaming Lower Bounds
      10:55 - 11:05     Short break
      11:05 - 12:00     Prof. Sanjeev Arora (Princeton):
                                Geometric Embeddings, Graph Partitioning, and Expander Flows: A survey of recent results
      12:00 -   2:00     Lunch break (on your own)
        2:00 -   2:55     Prof. Silvio Micali (MIT):
                                Collusion Free Protocols
        2:55 -   3:15     Coffee break
        3:15 -   4:10     Prof. Joan Feigenbaum (Yale):
                                Progress on the PORTIA Project
    • For directions, please see: http://www.cims.nyu.edu/direct.html and http://cs.nyu.edu/csweb/Location/directions.html (building 46)
13. November 24, 2004 (Friday → Wednesday this week!)
    • Lecture notes 12 (in postscript format)
    • Detailed discussion of homework problems.
    • Last few words about random walks (for a much more detailed exposition of the concept of random walks see the classical book on this topic by "Random Walks and Electric Networks" by P. G. Doyle and J. L. Snell):
      • Cover time of any undirected graph is ≤ 2 · m · (n-1).
      • The proof: build a spanning tree and ran the walk "via" Eulerean cycle which takes every edge of the spanning tree twice - once in each direction; then the result follows from the fact that for every edge (u,v) in E it holds that h_u,v + h_v,u ≤ 2 · m (and we proved! that result).
      • Note: cover time of a directed, strongly connected graph might be even O(2ⁿ).
    • Expanders - soft introduction (see Sections 1.1.3 and 1.2.3):
      • Probability amplification: how to reduce success probability for any randomized RP algorithm.
      • Magical graphs (=expanders) - their existence via the proof that a random graph is magical.
      • Probability amplification using magical graphs (we haven't finished it yet).
14. December 3, 2004 (last day of classes)
    • Another (long) discussion about homework problems.
    • Magical graphs, probability amplification, and expanders (see Sections 1.1.3 and 1.2.3 at http://www.math.ias.edu/~avi/TALKS/expander_course.pdf).
    • Expanders, their properties, and a few words about their applications.
    • Derandomization.
      • Method of conditional probabilities.
      • Small probability spaces - reduction to the analysis of d-wide independent random variables.

December 15, 2004

• Problems for the final exam in pdf format and in postscript.
  These files have been updated on December 11 due to a typo in Problem 2. (Originally p was greater than 1 ... now it has been corrected.)
• The due date for the final exam is 11:59pm on December 15, 2004 (the exam is take home).
• Deadline extension: it's now due 3:00pm on December 16 - please don't prolong it any longer ...

Handouts:

1. Handout 1: Basics in probability theory (file in postscript format)

Lecture Notes:

• Lecture 1 in pdf and in postscript
• Lecture 2 in pdf and in postscript
• Lecture 3 in pdf and in postscript
• Lecture 4 in pdf and in postscript
• Lecture 5 in pdf and in postscript
• Lecture 6 in pdf and in postscript
• Lecture 7 in pdf and in postscript
• Lecture 9 in pdf and in postscript
• Lecture 10 in pdf and in postscript
• Part II of Lecture notes 11 (in postscript format) - Part I will be added here (hopefully) soon.
• Lecture 12 in pdf and in postscript

Homework Assignments:

Homework is due November 24, 2004 (1:00pm - sharp) and is available in pdf format and in postscript format (files updated on November 5)

References:

Textbooks:

There are no single textbooks used by the instructor. However, there are a few books which could be very useful in the course.

• »Approximation Algorithms« by Vijay V. Vazirani, Springer, 2001.
  An excellent and very up-to-date textbook on approximation algorithms. A large part of the course material on approximation algorithms will be based on the presentation from this textbook.



• »Randomized Algorithms« by R. Motwani and P. Raghavan, Cambridge University Press, Cambridge, UK, 1995.
  An excellent (standard) textbook on randomized algorithms.



• »Approximation Algorithms for NP-hard Problems« edited by D.S. Hochbaum, PWS Publishing, Boston, MA, 1997.
  A (very good) collection of survey articles dealing with various approximation algorithms.



• »Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties« by G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, M. Protasi, Springer, 1999.
  A standard textbook on optimization problems/algorithms and approximation algorithms.



• »The Probabilistic Method« by N. Alon and J.H. Spencer, John Wiley & Sons; 2nd edition, 2000.
  An excellent (standard) textbook on probabilistic methods with some surprising applications to randomized algorithms.



• »Random Graphs« by B. Bollobas, Cambridge University Press; 2nd edition, 2001.
  The Bible on Random Graphs - all what you have to know about random graphs, their structure, their properties, ... and actually much more than you want to know. Besides that - an excellent book on the use of probabilistic techniques.

Links relevant to course:

• »A compendium of NP optimization problems«, maintained by Pierluigi Crescenzi and Viggo Kann (sometimes it is not very up-to-date, some problems are missing, but otherwise, it's a great compendium). This compendium will be very helpful in the course ...
  
  
• »Lecture Notes on Approximation Algorithms« by David P. Williamson, 1998.
  
  
• A preliminary draft of Vazirani's book (some parts are missing, some are perhaps not as good as in the book, but it's free)
  
  
• Postscript file (gzipped) of »Lecture Notes on Approximation Algorithms - Volume I« by Rajeev Motwani, Stanford (10 years old ... but still quite OK)
  
  
• »Lecture Notes on Approximation Algorithms for Network Problems« by J.Cheriyan and R.Ravi
  
  
• Approximation algorithms - a collection of Bin Ma.
  
  
• Postscript file of »Lecture Notes Approximationsalgorithmen« by Rolf Wanka (... if you can read German). Web page for this class is available too.
  Christian Scheideler used that lecture notes in his class and he has some lecture notes too.
  
  
• Very short text (in postscript) »Lecture Notes: Complexity of Approximation« by Berthold Vöcking
  
  
• Link to a much more advanced course »Advanced Topics in Theory of Algorithms : Approximation Algorithms« by Moses Charikar, Fall 2001, Princeton
  
  
• Link to a paper on approximation algorithms for Max-SAT: New 3/4-approximation algorithms for the maximum satisfiability problem by Michael Goemans and David P. Williamson
  
  
• Sample chapters from a draft of a monograph written by D. Dubhashi and A. Panconesi "Concentration of Measure for the Analysis of Randomised Algorithms."
  
  
• Linear programming - various links
  • Linear Programming Frequently Asked Questions
  • Mysteries in Linear Programming by Komei Fukuda
  • Geometric Linear Programming
  • Open problem: Linear Programming: Strongly Polynomial?
  • A Short Course in Linear Programming by Harvey J. Greenberg
  
  
  

Other links:

• A very interesting text about "How to read a research paper" by a Harvard Prof. Mike Mitzenmacher
• Link to an amazing course in CMU: Great Theoretical Ideas In Computer Science
• Some other interesting notes Introducing Theory to students in York Univ., Canada
• And some other cool text about theory: Abstract Thinking, Intro to the Theory of Computation by Jeff Edmonds