**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.

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

There will
be no tutorials.

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

Name :
Rahul Jain

Office :
S15-04-01

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

Phone:
65168826 (off).

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.

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.

‘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-ﬁfth 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