CS6234 : Advanced Algorithms

 

Basic Information:

 

Modular credits: 4

Prerequisite: CS5234

 

This module is aimed at graduate students who are doing or intend to do advanced research in algorithm design and analysis in all areas of computer science. The module covers advanced material on algorithms with emphasis on efficient algorithms, and explores their use in a variety of application areas. Topics covered include, but are not restricted to, linear programming, graph matching and network flows, approximation algorithms, randomised algorithms, online algorithms, local search algorithms, algorithms for large datasets. The module will be a seminar-based module that will expose students to current research in these areas.

Logistics:

 

Lectures: Every Friday 9-11 am at SR@LT19. First lecture on 13th January, 2012.

 

There will be no tutorials.

 

Office Hours: Every Friday 2-3 pm (or by appointment).

Lecturer:

 

Name : Rahul Jain

Office : S15-04-01

Email: first name at comp.nus.edu.sg

Phone: 65168826 (off).

Books:

 

We may use parts of the following texts and also material from outside these, e.g. research papers on algorithms and related areas.

 

1.      “Introduction to Algorithms” by Cormen, Leiserson, Rivest and Stein (Prentice Hall, Second Edition.)

2.      “Algorithm Design” by Jon Kleinberg and Eva Tardos. (Pearson International Edition.)

3.      “Approximation Algorithms”  by Vijay. V. Vazirani. (Springer.)

4.      “Randomized Algorithms” by Rajeev Motwani and Prabhakar Raghavan. (Cambridge University Press.)

5.      “Computational Geometry”, by de Berg, Mark, O. Cheong, M. van Kreveld, and M. Overmars. (Third edition. New York, NY: Springer-Verlag, 2008. ISBN: 9783540779735).

6.      “Data streams: Algorithms and applications”, by S. Muthukrishnan. Appears in Foundations and Trends in Theoretical Computer Science, Volume 1, issue 2, 2005.

Evaluations:

 

Somebody famously said “A problem well understood is half solved.” Therefore a primary ability any researcher must develop is the ability to read and understand and absorb known body of knowledge before adding further on to it. Since this module is intended at students who wish to do research in algorithms and related areas, the primary focus of the module will not be on ‘teaching new topics in algorithms’ (this has been done in several previous courses that you have taken in your journey so far), but on ‘teaching how to learn new topics in algorithms’. Therefore the focus will be to train students in being able to read and understand advanced material. You will be expected to read, understand and present advanced topics in algorithms/ research papers in algorithms. Your grade will be determined on how well you understand and present these topics/papers. There will be no exams.

 

Presentations:

 

‘Approximation Algorithms’ on 20-01-2012 (Week 2), presented by Simon Schoelly:

In this talk, Simon presented ‘approximation algorithms’ for NP complete problems. He started with greedy methods and presented a method to approximate the optimal solution of the ‘load balance problem’. Then he showed how to estimate how good the solution of this algorithm was, compared to the optimal solution. After that, he did a short improvement of this algorithm, by pre-sorting the input, which gave an even better bound. After that he showed the ‘pricing method’ to approximate an ‘optimal vertex cover’.

 

‘Online Algorithms’ on 27-01-2012 (Week 3), presented by Kartik Sankaran:

In this presentation, Kartik discussed evaluation of online algorithms using ‘competitive analysis’. The problem of ‘self organizing lists’ was described - why they are used, and where they are applied. Three deterministic online algorithms – ‘Move-To-Front, Transpose and Frequency Count’ were explained. The 2-competitive performance of Move-to-front was proved using the technique by Sleator and Tarjan. The use of randomization in the ‘Bit algorithm’ was shown to improve competitiveness. ‘Paging algorithms’ were discussed briefly. The presentation concluded by pointing out that competitive analysis is not enough to explain the better performance of ‘LRU’ (least recently used) over ‘FIFO’ (first in first out) paging algorithm. Due to time constraint, the ‘k-server problem’ was not discussed.

 

‘Randomized Algorithms’ on 03-02-2012 (Week 4), presented by Liu Xiao:

At the beginning of his presentation, Lui first had a short review of basic concepts in probability theory. Then he explained three algorithms. The first one is an algorithm that resolves ‘contention’. The second one is a randomized algorithm that finds min-cut of an undirected graph by repeatedly contracting edges. The third algorithm approximately solves the MAX 3-SAT problem. This example also illustrates the principle of ‘Probabilistic Method’. Lastly, he briefly introduced what ‘Chernoff bounds’ are (he had planned to do a more comprehensive introduction on Chernoff bounds but was only able to write down the theorem and the finished his talk due to the time constraint).

 

‘Extending the Limits of Tractability’ on 10-02-2012 (Week 5), presented by Guoqing Yu:

Guoqing first introduces the concept of dynamic programming and presents its difference with recursive algorithms (such as divide and conquer). Then, following a review of the largest vertex cover problem, a similar algorithm is presented for the ‘MAX 3-SAT’ problem. After that, Guoquing reviews the algorithm for the largest independent set on trees, and introduces the algorithm for the largest weighted independent set on trees by developing two formulae that adopt dynamic programming methods. Finally, he solves the ‘Circular Coloring’, using dynamic programming, problem by introducing a much simpler problem ‘Interval Coloring’. Due to time constraint, he discusses the definition of ‘tree width’ on IVLE. The concept of ‘Tree Width’ is very interesting and useful in practice, and helps to tackle hard problems on graphs with large number of nodes and/or edges but relatively small tree width.

 

‘Network Flow’ on 17-02-2012 (Week 6), presented by Md. Tanvirul Islam:

At the beginning of his presentation, Tanvirul tried to explain, with examples, what a ‘Maximum Flow’ Problem is. Then he picked a version of the problem and proved that solving that version is equivalent to solving almost all the possible variations encountered in realistic scenarios. He emphasized on building the physical intuition behind the ‘Ford-Fulkerson Method’ to the audience. He showed how one can come up with the idea of an ‘augmenting path algorithm’ using ‘residual graphs’. Even though the algorithm is simple, the proof of why it works is nontrivial. He explained in details (using both examples and mathematical proofs), all the necessary steps before going to the final ‘Max-Flow-Min-Cut theorem’. Then he analyzed the time complexity for different implementations of this method. Finally, to give an idea of how this algorithm can be used to solve various problems which seem to have little to do with ‘flow networks’ at a first glance, he solved the problem of ‘maximum bipartite matching’ and the problem of finding ‘edge disjoint paths’ between two nodes in a graph. He mentioned about the more advanced ‘Push-Relabel’ algorithms which have better time complexity than Ford-Fulkerson Methods.

 

‘Linear Programming’ on 09-03-2012 (Week 8), presented by Kuldeep Garg:
The motive behind the presentation on ‘Linear Programming’ was to familiarize the audience with the way of formulating a real life application into a linear programming problem and then to find a solution to that linear program. The presentation was instigated with the detailed discussion of how to convert a given problem into linear programming problem. Then, the various terminologies used to provide easy flow to the lecture were discussed. The solution method covered was ‘simplex algorithm’, which is the oldest but fairly efficient and widely used method to solve linear programs. Various examples were discussed during the lecture to provide good understanding of the algorithmic steps. The concepts of ‘dually’ and ‘initial basic solution feasibility’ were discussed using both examples and mathematical proofs to provide the correctness and clear insight into the simplex algorithm. The presentation was concluded by showing that the simplex acts appropriately by returning either of infeasible/unbounded/optimal solutions.

 

Some slides for this presentation

 

‘Computational Geometry’ on 16-03-2012 (Week 9), presented by Ankush Sharma:

Computational geometry algorithms for the two topics – ‘convex hull and Voronoi diagrams’ were covered in the presentation. Both ‘Graham's scan’ and ‘Javir's march’ algorithms were covered for the convex hull problem on 2-D. Both algorithms proceed by deciding which vertices to keep as vertices of the convex hull and which vertices to throw out. Both Graham's scan and Jarvir's march use a technique called ‘rotational sweep’, processing vertices in the order of the polar angles they form with a reference vertex. Minor terminologies like ‘polar angle, right or left turn’ were also covered in the beginning.

 

Algorithm for Voronoi Diagram was not covered completely due to time constraints. The topics covered were the definition of Voronoi diagram, elements involved in the Voronoi diagram, a brief overview of the ‘sweep line algorithm’ and the two major events in the sweep line algorithms – ‘site event and circle event’. 

 

References:

1.      “Introduction to Algorithms” by Cormen, Leiserson, Rivest and Stein.

2.      http://www.tcs.fudan.edu.cn/rudolf/Courses/Algorithms/Alg_ss_07w/Webprojects/Chen_hull/applications.htm
- www.montefiore.ulg.ac.be/~briquet/algo3-chull-20070206.pdf

3.      “Computational Geometry”, by de Berg, Mark, O. Cheong, M. van Kreveld, and M. Overmars.

4.      CS5237 Computational Geometry, Lecture 4 (Lecturer - Holun Cheng, NUS).

5.      “Computational Geometry”, by de Berg, Mark, O. Cheong, M. van Kreveld, and M. Overmars.

6.      CS5237 Computational Geometry, Lecture 5 (Lecturer - Holun Cheng, NUS).

7.      "Lecture 7: Voronoi Diagrams" - nms.csail.mit.edu/~aklmiu/6.838/L7.pdf

 

Some slides of the presentation

 

‘Parallel and Distributed algorithms’, on 23-03-2012 (Week 10), presented by Eric Cesar E. Vidal, Jr. :

The talk starts with a basic introduction to parallel computation and a simplified parallel-computing architecture known as the ‘Parallel Random Access Machine’.  A parallelized version of the algorithm to find the maximum of a set of numbers (and, by extension, any semigroup algorithm) is implemented using this machine model.  A technique called ‘Accelerated Cascading’ is then shown to optimize the ‘total work’ (number of processors x running time) done by this family of algorithms.  The second half of the talk explored other viable models of parallel computation (circuits, linear networks and mesh networks) using sorting as a case study -- the ‘Odd-Even Transposition Network’ is used as a basis for accomplishing sorting using these architectures, the correctness of which is proven in part by the ‘Zero-One Principle’ of sorting networks.  Finally, distributed computation is introduced, focusing on additional issues present in this model of computation (‘message broadcasting, bandwidth usage minimization and decentralization’) along with algorithms to solve these problems (‘broadcast, echo and leader selection’).  The leader selection problem was not anymore discussed due to time constraints.

 

Some slides for this presentation

 

‘Constructive Proof of the General Lovász Local Lemma’, on 30-03-2012 (Week 11), presented by Simon Schoelly, Guoqing Yu and Kartik Sankaran:

In this presentation, Simon, Guoqing and Kartik discussed a 'Constructive Proof of the General Lovász Local Lemma (LLL)' (by Moser and Tardos 2009). Simon gave an introduction of the lemma, by first describing the notion of 'bad events' and 'dependency graph' with respect to the 'Hypergraph Colouring' problem, using an illustrative example. After explaining the difference between a 'Constructive' and 'Non-constructive' proof, he then presented the LLL algorithm, and its working. Guoqing described two constructs - 'Execution Log' and 'Witness trees', which are useful during the analysis. He gave the steps to construct a Witness tree for any given position in the Execution Log, with a supportive example. He then proved a result regarding the probability of occurrence of a witness tree in the log (useful in later analysis). Kartik described the 'Galton-Watson branching process', used to generate random witness trees. He proved that under the constraints of the lemma, the branching process terminates, allowing us to calculate the probability of generation of a particular witness tree. Using the results proved earlier, he calculated the expected (finite) length of the execution log, and hence showed that the LLL algorithm not only terminates, but the expected running time is polynomial.

References:

1.      "www.babai60.org/slides/tardos.ppt" : Slides (by Gábor Tardos) for the example of constructing a witness tree .

2.      "http://dl.acm.org/citation.cfm?id=1667060" Link to paper by Moser and Tardos, 2009.

3.      ``A constructive proof of the general lovász local lemma’’. Robin A. Moser and Gábor Tardos. Journal of the ACM (JACM), Volume 57 Issue 2, January 2010.

 

 ‘A Polylogarithmic-Competitive Algorithm for the k-Server Problem’, on 05-04-2012 (Week 12), presented by Kuldeep Garg, Tanvirul Islam and Eric Vedal :

In this talk, the k-server problem and its 25 plus year history of online solution approaches were briefly discussed. Then Bansal et al.'s paper on a polylogarithmic-competitive (O(log^2 k log^3 n)) algorithm for the k-server problem on arbitrary metric spaces was introduced. This algorithm builds upon Cote et al.'s previous solution employing the use of binary Hierarchically well-Separated Trees (HSTs) as an approximate metric, along with a reduction of the problem to a "fractional" (as opposed to truly randomized) Allocation Problem on a uniform metric. The new algorithm's contribution is a solution to an expanded version of the Allocation Problem on a weighted-star metric, thereby allowing the use of non-binary weighted HSTs, which, in turn, allows the new algorithm to depend only on the number of servers k and the number of points n in the metric space as well as giving a polylogarithmic competitiveness. A rough overview and competitive analysis of the overall solution was presented, then the fractional allocation algorithm was shown and discussed. (The competitive analysis of the fractional allocation algorithm was not presented due to time constraints.)

 

References :

1.      http://www.cs.princeton.edu/~zdvir/barriers2/naor.pptx

2.      J. Fakcharoenphol, S. Rao, and K. Talwar, "A tight bound on approximating arbitrary metrics by tree metrics," in STOC ’03: Proceedings of the thirty-fifth annual ACM symposium on Theory of Computing, 2003, pp. 448–455.

3.      Nikhil Bansal's tutorial presentation at Mysore Park Workshop 2011, link: http://www.tcs.tifr.res.in/~prahladh/mysore2011/abstracts.html

4.      “A Polylogarithmic-Competitive Algorithm for the k-Server Problem”. Nikhil Bansal, Niv Buchbinder, Aleksander Mądry and Seffi Naor. FOCS 2011.

 

Some slides for this presentation : slides-1, slides-2

 

‘A Polynomial Time Approximation Scheme for Euclidean TSP’, on 06-04-2012 (Week 12), presented by Ankush Sharma, Xiao Liu and Tareek Ben Yousef
A Polynomial Time Approximation Scheme (PTAS) for the Eiclidian TSP in a 2D plane, proposed by Sanjeev Arora was covered in the presentation. In the beginning, a brief overview of Euclidean TSP, variants of TSP and PTAS was covered. Given n nodes in the plane and e > 0, the scheme finds a (1 + e) approximation to the optimum travelling salesman tour in n^(O(1/e)) time. The scheme for a TSP instance in R^2 has a (1+ e) approximate tour having a simple structure that “there is way to recursively partition the plane (rectangle enclosing the nodes) so that very few
edges of the tour cross each line of partition”. A Dynamic Programming approach is used to estimate the approximate tour. Major definitions and propositions were covered in the beginning,
followed by "Structure Theorem" and its complexity analysis. Structure Theorem forms the base of the approximation scheme. In the end, correctness proof for the Structure theorem was covered.

References
1. “Polynomial Time Approximation Schemes for Euclidean TSP and other Geometric Problems ” by Sanjeev Arora. In Proceedings of the 37th Annual Symposium on Foundations of Computer Science, 1996.
2. http://www.corelab.ntua.gr/courses/approx-alg/material/Euclidean%20TSP.pdf
3. http://faculty.math.tsinghua.edu.cn/~jxie/courses/algorithm/TSP-PTAS.ppt
4. http://www.cse.yorku.ca/~aaw/Zambito/TSP_Euclidean_PTAS.pdf

 

Some slides of the presentation: slides-1, slides-2

 

‘Local search’ on 06-04-2012 (Week 12), presented by Tareek Ben Yousef:
The presentation began with a formal definition of the local search algorithms, including a set of solutions, a neighbouring relation and a function to optimize. Tareek presented then two simple local search algorithms for finding a global optimum: a trivial solution called the gradient descent algorithm, and a more efficient algorithm called `Metropolis’ which try to escape some local optimums. A variant of Metropolis algorithm called `Simulated annealing’ was presented as well. Then, he gave a concrete problem called `Hopfield neural networks’, in which local search algorithms are used to find local optimum (that are enough to solve the problem). Then, an equivalent but more specific concrete example was presented. It is called `Maximum-cut approximation’ and local search allows to find a ½-approximation of the optimal solution. The last part deals with a game theory problem applied to ‘multicast routing problem’, in which many objectives are solved instead of only one objective. Local search approaches are presented to introduce ‘best response dynamics’ and ‘nash equilibrium’.

 

Some slides of the presentation