CS6234 : Advanced Algorithms
Modular credits: 4
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 18th January, 2013.
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. Marks distribution is as follows.
First presentation 40 marks.
Second presentation 40 marks.
Forum discussions 20 marks.
Schedule: Please click this link.
1. Topic: Machine learning.
Date: 25 January.
Group: Tian Shangxuan, He Xiangnan, Ji Kun, Guan Peiyong and Wang Hancheng.
In the presentation, the group mainly talked about off-line learning and on-line learning algorithms in machine learning. Off-line learning algorithms aim to find a target function based on some training set. The group focused on Probably Approximately Correct (PAC) learning which can generate concepts having low error with high probability, and provides theoretical foundation for the relation between lower bound of accuracy and the size of the training set. Weak PAC learnability and a boosting approach to reduce error probability as well as Adaboost algorithm were also covered.
On-line learning targets at predicting labels for instances by assuming that instances come one by one. By adjusting the parameters (or models) on the arrival of each instance, they make the real-time machine learning tasks possible. In this part, the group mainly introduced two online learning algorithms, namely Weighted Majority algorithm and Winnow algorithm, which are two distinct representatives of online learning from experts and examples respectively.
2. Topic : Combinatorial Algorithm
Date : 1st February 2013
Group : Wangsheng, Ye Hong, Jin Yong, Wangwei and Gordon
The topic of the talk was combinatorial algorithms, specifically algorithms for bipartite graphs. The first part of the talk was on finding maximum matching in a bipartite graph. Two algorithms were presented: a simple algorithm using augmented paths and then the more efficient Hopcroft-Karp algorithm, which worked with several vertex disjoint augmented paths at the same time.
The next part of the talk was on the Stable Marriage Problem. The algorithm presented was the Gales-Shapley algorithm, to find a stable matching in a bipartite graph given some preference rules. Finally, the last part of the talk was on the optimal assignment problem. The algorithms presented were the Hungarian method and the Kuhn-Munkres algorithm.
3. Topic : Streaming Algorithms
Date : 8th February 2013
Group : : NARMADA SAMBATURU, SUBHASREE BASU, ALOK KUMAR KESHRI, RAJIV RATN SHAH, VENKATA KIRAN YEDUGUNDLA, VU VINH AN.
In this presentation, basic concepts of Streaming algorithms were introduced along with two techniques known as Sampling and Sketching. In Sampling, a classic Reservoir Sampling algorithm was presented where in all the elements of the data stream have equal probability of being chosen as well as retained in the final sample. To include the notion of timeliness of data that is missing in the reservoir sampling, the group introduced the concept of 'sliding window' and discussed the Priority Sampling Algorithm for sliding windows. In Sketching, two sketching methods namely Bloom Filter and Count-Min Search were presented. They are used to solve different important problems such as most frequent item in stream, finding the size of self-join on a data stream in limited space. The group presented a classical problem of counting distinct numbers in a stream along with two algorithms to solve the problem. One is the Flajolet-Martin Algorithm and the other one is an algorithm to solve the problem with optimal space complexity.
Topic : Linear
programming and Ellipsoid algorithm
Date : 15th February 2013
Group : Seungmin Kang, Aissan Dalvandi, Le Tuan Anh, Anup Kumar Das
In this talk, the group presented the `ellipsoid algorithm’ to solve linear optimization problems in polynomial time. First an optimization problem is converted into a feasibility problem. The algorithm then starts with a big enough ellipsoid which is guaranteed to cover the feasible region if it exists. Then the centre of the current ellipsoid is checked to see whether it lies within the feasible region or not (that is by checking if the centre satisfies all the constraints). If it doesn’t, then a cutting hyper-plane is found which divides this ellipsoid into two halves (by shifting any violated constraint to the centre of the ellipsoid) so that one of the halves contains the feasible region. Then a new ellipsoid is formed containing the half-ellipsoid which in turn contains the feasible region. These steps are repeated until the centre of the current ellipsoid lies within the feasible region (at which point the algorithm declares `feasible’ and stops) or a predefined number of iterations is over (at which point the algorithm declares `infeasible’ and stops).
A proof of correctness and the running time analysis of the algorithm was presented. First the proof of correctness in a simple case (unit ball, separating hyper-plane crossing 0 etc.) was presented. Then the same method was used to prove the correctness in the general case. For running time analysis, it was shown that the ratio between the current ellipsoid and the next ellipsoid is upper bounded by exp(-1/(2(n+1))). Hence it was shown that the algorithm will terminate after 2n(n+1)ln(R/r) iterations (where n is the dimension of the problem space, R is the radius of the original ellipsoid and r is the radius of a small ellipsoid that lies inside the feasible region if it exists).
To understand the concepts, the group first introduced convex optimization basics with the duality theorem. Subsequently, the details of the exact algorithm and the analysis were presented. Finally, the talk was concluded by mentioning some other algorithms for linear programming.
Topic : Cryptographic
Date : 22nd February 2013
Group : Daryl, Etkin, Supartha, Rajendra and Aarthi
The first half of the talk focussed on the RSA algorithm,
which is an implementation of a public key cryptosystem, where public/private
key pairs are generated and messages are encrypted with the public key but can
only be decrypted with the private key. RSA can help to create a secure (i.e.
private) line of communication between two parties without the need to agree on
a shared secret key. The algorithm can also be easily adapted for use in
digital signatures, where messages can be signed by their sender and verified
as authentic by any receiver. Various sub-algorithms are required to implement
RSA, including successive-squaring for modular exponentiation and the extended
Euclidean algorithm for computing the decryption exponent. However, since RSA
is based on the difficulty of factorizing integers with at least one large
prime factor, one of the most important sub-algorithms is that for generating
very large primes efficiently. The Miller-Rabin test is one such method to do
this and can be implemented as either a randomized or deterministic algorithm.
The randomized algorithm turns out to be more suitable in practice.
The second half of the presentation covered Reed-Solomon codes, which are a form of error correcting codes, initially at an intuitive level before delving into the mathematics and algorithms for performing encoding and decoding. Error correcting codes enable us to have reliable communication over unreliable channels. The basic idea is to introduce redundancy in a controlled way so that we can recover the original information even in the presence of errors or even erasures. Reed-Solomon codes use polynomials over finite fields to encode the data along with parity symbols. The decoding process is a multi-step one whose ultimate goal is to completely estimate the 'error polynomial' starting from the number of errors (shown with the Peterson decoder), the positions in the received message that have an error (found with Chien search) and determining the values of those errors (with Forney's Algorithm). Operating on the error polynomial and the received polynomial regenerates the intended message. This code has the advantage of being able to correct for burst-errors, erasures, efficiently implementable on dedicated chips for its use and achieves the Singleton Bound. It is still extensively used in Barcodes, satellite communication, to burn DVD's/CD's, and in some RAID storage models as well.
6. Topic: Random Walks and Markov Chains
Date: 8th March 2013
Group: Nimantha Thushan Baranasuriya, Girisha Durrel De Silva, Rahul Singhal, Karthik Yadati, Ziling Zhou
In this talk, the group covered how Random Walks and Markov Chains can be used to model problems and to analyse randomized solutions that solve those problems. In the first half of the presentation, the group introduced the concepts of Random Walks and Markov Chains and discussed examples to better explain the two concepts.
Next, the group focused on explaining in detail three problems that used Random Walks and Markov Chains for modelling and analysis: 2SAT, 3SAT and Card Shuffling. For each of these problems, the group discussed randomized solutions, and the algorithms were analysed using Random Walks and Markov Chains concepts that were introduced in the first half of the presentation.
7. Topic: PageRank
Date: 22nd March 2013
Group: Tian Shangxuan, He Xiangnan, Ji Kun, Guan Peiyong and Wang Hancheng.
PageRank is one of the most important algorithms used by Google search engine, developed by its current CEO Larry Page and co-founder Sergey Brin. In this talk, the group presented PageRank, Topic-Sensitive PageRank and their applications in depth and breadth.
The first half of the presentation focuses on PageRank. Elements of a general search engine are clearly explained to give the audience an overall picture, so that the purpose of PageRank is in the whole search engine is well understood. Generally, there are two essential components for ranking a page in most search engines, which are: query dependent score and query independent score which measure the relevance of the webpage to a given query and the importance of the webpage itself, respectively. PageRank focuses on the latter, i.e., ranking the importance of all web pages. The basic idea of PageRank is that the importance of a webpage is based on the importance of those web pages that pointing to it, not the number of pages. Followed from that, a simplified PageRank algorithm is given and random surfer model is used to explain how the algorithm works. However, the simplified PageRank has issues in handing dangling nodes, rank sinks and cycles. Using the theory from Markov chain, the group further proved the convergence of the algorithm, when the stochasticity and primitivity adjustments are applied.
The second half of the presentation focuses on Topic-Sensitive PageRank (TSPR) and applications of PageRank. TSPR utilizes a personalized vector, which allows different weighting of user-specified topics. With the understanding of TSPR, the group further compared the differences and relationships among the popular ranking algorithms, including HITS, PageRank, SALSA and TSPR. Lastly, the group presented two applications of PageRank: TrustRank to tackle the link farm issue and ImageRank to rank images based on their visual appearance.
In summary, searching on the large and heterogeneous Internet is not an easy task. Different techniques including PageRank, Topic-Sensitive PageRank, key word matching, natural language processing can be combined to further enhance the accuracy meaningfulness of the searching results with the objective of satisfying the needs of the diversified Internet users.
8. Topic: Approximate Counting
Date: 28th March 2013
Group : SUBHASREE BASU, RAJIV RATN SHAH, VENKATA KIRAN YEDUGUNDLA, VU VINH AN.
In this presentation, the group explained how randomization and approximation techniques could help in approximating the solution for some hard counting problems in time which is polynomial in the input size. At first, they introduced the counting problem, its application, difficulty and terminology. They also gave the definitions for A Polynomial Approximation Scheme (PAS), A Fully Polynomial Approximation (FPAS), A Polynomial Randomized Approximation Scheme (PRAS) and A Fully Polynomial Randomized Approximation Scheme (FPRAS). After that they discussed two problems: the Disjunctive Normal Form (DNF) counting problem and the Approximating the permanent problem.
In the DNF counting problem, one tries to approximate number of satisfying assignments for the given DNF. The group first described some unsuccessful attempts to solve the problem, followed by the ‘coverage algorithm’. The coverage algorithm tries to reduce the sample space while ensuring that the set of satisfying assignments is correctly represented.
In the approximating the permanent problem, the permanent of 0-1 matrix is shown to be equivalent to the number of perfect matchings in a bipartite graph. A near-uniform generation for set union is then generated using random walk on Markov Chain to estimate the number of perfect matchings of the bipartite graph. Canonical path argument is used for proving the polynomial time complexity of the algorithm in details.
9. Topic : Karmarkar’s interior point algorithm
Date: 11th April 2013
Group : Aissan, Anup, Seung Min, Le, David, Narmada Sambaturu.
This talk extends the concepts introduced in the talk on ellipsoid algorithm by presenting Karmarkar's algorithm, which can solve the Linear Programming problem in a faster polynomial time. Karmarkar's algorithm is an interior point algorithm, and starts with an initial feasible point and moves this point toward the optimal vertex in each iteration.
The algorithm introduces new constraints into the LP by expecting the input to be in a specific form (Karmarkar's canonical form). These constraints are then exploited to get a faster running time. The following two tricks help Karmarkar's algorithm achieve a fast polynomial running time:
1. Optimization over a ball: The biggest possible ball is drawn inside the feasible region, and all moves made are of length slightly less than the radius of this ball. This way we are guaranteed to stay within the feasible region even though we never check for feasibility. The direction chosen for each move is the direction in which the cost function is reducing the fastest (assuming the objective is to minimize the cost).
2. Projective transformation: The feasible region is transformed at each step in such a way that the current point is in the center of the transformed region. This way the largest ball in the feasible region will have center at the current point, and the largest possible move toward optimal can be made.
The presentation introduced the problem to be solved and the intuition behind the techniques used to achieve fast running time. The details of these techniques were then developed, including derivations of some of the transformations. This was followed by an analysis of the running time to prove that the algorithm converges in O(nL) iterations where L is the number of bits needed to represent the LP, and n is the number of dimensions. Analysis was also done to show that work per iteration can be done in O(n^2.5) time, making the overall running time O(n^3.5L). A procedure for converting any linear programming problem to Karmarkar's canonical form was then outlined, thus completing a start-to-finish solution to solve any given LP problem in O(n^3.5L) time.
10. Topic : Approximation algorithms: Sparsest cut.
Date: 12th April 2013
Group : Supartha, Aarthi, Etkin, Darly Seah, Rajendra.
This talk covered the Sparsest Cut problem along with an O(log k) factor randomized poly-time approximation algorithm for the problem, where k is the number of commodities. The introduction discussed the relationship between maximum-flow and minimum-cut problems, highlighting that the Max-Flow Min-Cut Theorem does not apply to Sparsest Cut and the corresponding Demands Multi-Commodity Flow problem since they are defined with respect to multiple commodities.
Since Sparsest Cut is NP-Hard, an alternate formulation for it as an integer program is also NP-Hard. To overcome this, the relaxation of the problem to a Linear program was shown where the objective function (for LP & IP) used cut metrics as variables of the program. The connection between the solutions to these programs and metric spaces was pointed out, especially as the conical combination of all cut metrics (i.e. the set CUTn) is an l1-metric space. Thus, solving the LP gives an arbitrary metric space and metric embeddings are used to find an approximation to the l1-metric space which gives rise to the O(log k) approximation factor.
Some intuition regarding the embedding itself can be explained as follows: The optimal Sparsest Cut can be a conical combination of an exponential number of cut metrics which would take exponential time to solve; but solving the LP relaxation gives some combination of cut metrics now no longer in l1 but in an arbitrary metric space whose dimension is also unknown and could be unbounded. The embedding in a randomized fashion, with high probability, creates an l1 metric defined in an O(log^2 k) dimension space. This dimension restriction makes it poly-time computable. The l1 metric obtained essentially forms a conical combination of some polynomial number of cut metrics on the vertices of the original graph s.t. the sparsity of the cut they define is at most an O(log k) factor of the optimal.
11. Topic: Stream codes
Date 18th April 2013
Group: Wangsheng, Ye Hong, Jin Yong, Wangwei, Gordon.
The team presented the topic on stream codes and in particular focused on lossless data compression techniques. To start, the team first gave an overall review of Huffman code and then the focus was on Arithmetic and Lempel-Ziv coding techniques.
Huffman coding technique assigns fewer bits to symbol that occurs more frequently and more bits to symbols that occur less frequently. A tree is build by adding up two symbols with the smallest probability at each stage and the process is continued until there is exactly 1 node left on the tree where the probability is then 1.
Arithmetic coding works on the idea based on a probabilistic model of source symbols. The interval [0,1) is partitioned iteratively until we hit the end of the string; the final interval is then sent over to the decoder which decodes with the same technique used in the encoding process. We can also shift from a static probabilistic model into an adaptive model by adjusting the probabilities when a new symbol comes. A simple Bayesian model was introduced by the group to facilitate this discussion. Finally, the group introduced the loss analysis for both cases where an end of file symbol is present and not. The coding rate was shown to reach the optimal Shannon bound.
Lempel-Ziv algorithm is a lossless data compression technique that works on the principle of building up a dictionary rather than having a probabilistic model. Words are partitioned into substrings and added as an entry into the dictionary and sent over in the form of binary. The decoding process is similar. Finally, to end the talk, a brief summary was given to recap the content that was covered.
12. Topic: Online Algorithms
Date 19th April 2013
Group: Rahul Singhal, Nimantha Thushan Baranasuriya, Girisha Durrel De Silva, Karthik Yadati, Ziling Zhou
The group first introduced the basic concept of online algorithms. Thereafter the group introduced the concept of the competitive ratio which is required to analyse online algorithms.
Once the introduction was done, the group introduced a simple online algorithm called the ski rental problem. After introducing the ski rental problem the group introduced another online algorithm called the secretary hiring problem.
The next phase of the presentation was related to the k-server problem. The group first introduced the k-server problem and then established several lemmas and definitions that are needed to examine algorithms related to k-sever problems.
In the final part of the presentation the group introduced a simple deterministic online algorithm for k-server problems called the BAL (balanced) algorithm. The group ended the presentation by discussing a lower bound for the competitive ratio related to the k-sever problem while introducing a state of the art k-server algorithm called WFA (Work Function Algorithm).