# CS 6100: Topics in Design and Analysis of Algorithms

Term: Jan - May, 2012

Instructor
: John Augustine

Teaching Assistants:
• Sangeetha Jose
• Jim Chacko
• Venkatesh Kinthali
• Prateek Barapatre

Brief Description: This course will cover a range of topics that are actively studied by algorithms researchers. The topics we intend to cover (in order) are as follows.
• Computational Geometry (~35%). There is geometry all around us --- this is obvious for the most part, but not always so. Here's a non-obvious example. Consider a database of employees in a firm consisting of their age and salary. We can represent each employee as a point (x,y) where x is their age and y is their salary. Notice that queries of the form "get employees with age <= 30 and salary > Rs. 60,000" can be framed geometrically. Unsurprisingly, several algorithmic problems can be posed on geometric structures. To solve these problems, we will need to combine geometric insights with algorithmic techniques.
• Advanced Graph Algorithms, NP-Completeness and Approximation Algorithms (~30%). Graphs are simple structures that model elements of a set and connections between pairs of elements in that set. They are quite ubiquitous in application. We will pose and solve algorithmic problems on underlying graph structures. For some of these problems, we (humanity as a whole!) do not know if there are algorithms whose running times grow as polynomials on the size of the input instances. This will lead us to NP-completeness, which in turn will lead us to focus on approximate solutions.
• Parallel and Distributed Algorithms (~35%). We live in a world that is highly connected and our computers are no exception. On the one hand, we are individuals (with a smart phone computer in our hand). On the other hand, we are part of a global community (with our computers forming giant networks). A natural question is: how can our individual computers coordinate to perform some global task? Under this umbrella question, we will study several concrete problems.
In each topic, we will first study a few canonical problems that lay the foundation for that topic. Subsequently, we may touch upon some state-of-the-art works within the topic. This course is aimed at students who are considering research in algorithms and would like to sample plausible research topics within the well-defined framework of a course.

Prerequisites: Consent of Teacher (COT). Students enrolling in this course must have taken a core algorithms course. Furthermore, students must be reasonably familiar with basic probability theory.  Various randomization techniques will be introduced in this course. A quick recap of fundamentals will be provided as and when needed.

Grading: Problem solving assignments at regular intervals, final project/presentation, and exam(s). Detailed breakup will be given on the first day of class. Students may collaborate on assignment problems as long help is properly acknowledged. This freedom should be seen as an attempt to capture the social nature of research and not a means to trivialize your course experience. Exam problems must be solved individually. Given the freedom to collaborate in assignments, we expect students to maintain good conduct in exams.

References: Given the broad nature of this course, we do not have a single textbook. Instead, we will cherry pick from the following tentative list of references and other relevant sources (papers, reference books, etc). You do not need to own these books. Limited number of copies of these books will be made available in the department library.
• Computational Geometry: Algorithms and Applications, by de Berg, Cheong, van Krevald, and Overmars.
• Computationa Geometry: an Introduction Through Randomized Algorithms, by Mulmuley.
• Distributed Computing: A Locality-Sensitive Approach, by Peleg.
• Distributed Algorithms, by Lynch.
• Distributed Computing: Fundamentals, Simulations, and Advanced Topics, by Attiya and Welch.
• Introduction to Algorithms, by Cormen, Leiserson, Rivest, and Stein.
• Randomized Algorithms, by Motwani and Raghavan.
• Approximation Algorithms, by Vazirani.
• Introduction to Parallel Algorithms, by JaJa.

Typesetting in Latex: You are expected to typeset your assignments and project report in latex. Here are some tips to get you started. To use latex, you may have to download and install either Miktex (for Windows), Tex Live (for Linux), or Mactex (for Mac). I would recommend that you install the entire system so that you can avoid missing that one package that you suddenly need. Then you may need an editor. I use Texmaker, which is available for all common platforms. In fact, Texmaker is often included with your latex installation. Finally, you may also need a software tool to draw figures. I highly recommend ipe, which is cross platform and very easy to install in Windows, but its a bit difficult in MACs. A one stop place for most of your latex documentation needs is the latex wikibook.

Latex comes with several tools, one of which is pdflatex. When your source file is compiled with pdflatex, you will directly produce a pretty pdf document. Also, you can include figures in pdf format, which ipe can produce for you.

### Lecture Slides

If you find any errors, please drop an email to the instructor (augustine at cse). Thanks.

1. Introduction to CS6100, Even 2012.
2. Recollection of Basic Concepts.
3. Convex Hull.
4. Intersection of Line Segments.
5. The Art Gallery Problem.
6. Range Searching.
7. Point Location.
8. Voronoi Diagram.
9. Delaunay Triangulation.
10. All Pairs Shortest Paths.
11. Minimum Cut.
12. Introduction to Distributed Algorithms.
13. Leader Election in a Ring.
14. Maximal Independent Set (sent via email).
15. Minimum Spanning Tree (sent via email).
16. Vertex Colouring (Chapter 1 and parts of Chapter 10 in the notes by Roger Wattenhofer).
17. Fault Tolerant Consensus.
18. Dynamic Networks.

### Assignments

Assignment 0 (Due Jan 18). You can use my latex source file as a starting template.

Assignment 1 (Due Feb 12). You can use my latex source file as a starting template. Some auxiliary scanned material has been posted in the cs6100_2012 email group. If you haven't signed up yet, please do so.

Assignment 2 (Due March 4 March 7). You can use my latex source file as a starting template.

Assignment 3 (Due April 15). You can use my latex source file as a starting template.

### Exam Schedule:

Exam 1 will be on March 10th from 2 - 5PM. You will be tested on topics up to and including lecture slide number 9. This is mostly computational geometry, but keep in mind that I covered a few topics (randomized incremental sorting, skip lists, etc) that are not computational geometry, per se.

### Acknowledgements:

Much of my computational geometry notes and assignment questions are based on Computational Geometry: Algorithms and Applications, by de Berg, Cheong, van Krevald, and Overmars. I am thankful that they have made their figures and pseudocode public. I am using them liberally in my notes. For graph algorithms, with an intent to emphasize the power of randomization, I am following Randomized Algorithms, by Motwani and Raghavan. Many thanks to Prof. C. Pandu Rangan for his guest lectures on Parallel Algorithms. My notes in distributed algorithms are based on notes by Gopal Pandurangan and Roger Wattenhofer.