Instructor

- Sangeetha Jose
- Jim Chacko

- Venkatesh Kinthali

- Prateek Barapatre

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

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

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.

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

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

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.

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.