Advanced Algorithms

COT5405 Fall 2005

Course Information Handout: [pdf]

Instructor

Piyush Kumar

Lecture Time and Place

Monday , Wednesday. 5:15 - 6:30pm. Love 0103.
TA: Stanislav Ustymenko (ustymenk @ cs)
TA Office Hours: Mon 11am-12am and Thursday 3pm-4pm in 104C Love. 104C is inside 104A (Grad lab), you'll have to knock for entry.
Instructor Office Hours: Monday, After Class.

Lecture Notes/Slides

You will be able to find the lecture notes/slides here. Class readings/homework assignments can be found here. Programming assignments will be posted here.

Course Description

This is an advanced course in algorithms. You will be expected to know the material taught in 4531 well. Here is a short summary of the topics that we will tentatively cover in the course (not necessarily in this order).

Data Structures: Integer searching (Programming Assignment). Hashing. NN-Searching, Sufix trees.
String matching, Tries, Introduction to search engine design.
Compression: Huffman Coding, Arithmetic coding.
Optimization:
- Linear Programming.
- Eigenvalue/SVD/Clustering problems.
Network Flows.
Approximation Algorithms.
- Vertex cover
- TSP
Online algorithms.
Parallel algorithms.
Computational Geometry:
- Finding a large triangle inside a polygon (Programming Assignment).
- Range searching, Convex hulls, RIC: (MEB).
External memory Algorithms: Sorting.
Cache oblivious Algorithms: Van Emde boas Layout, FFTW.
Machine Learning: PAC Model and applications, VC-Dimension, Perceptrons, SVMs.

Learning Objectives

The objective of this course is to encourage you to learn how to :

design and implement `new' algorithms in the real world.
map problems to algorithmic problems.
read and understand algorithms published in journals.
develop writing skills to present your own algorithms
collaborate and work together with other people to design new algorithms.

Prerequisites

A Grade of B or better in COP 4531 or CGS 5427 or an equivalent course. Come and talk to me if you do not have the prerequisite and you still want to take the course. I will try to keep the prerequisites to a minimum and will review material as needed. You will find basic concepts of combinatorics (counting, graphs, recursion) to be very useful. Finally, it is useful to have experience with C, C++, or Python. (You should be able to code in C++.) Some of the homeworks will ask you to write code. There will also be a programming project in the course.

Textbooks

I will assume that each of you own a copy of Algorithm Design (Hardcover) by Jon Kleinberg, Éva Tardos ISBN: 0321295358. You should also have access to [CLRS] book that I use in 4531. Most of the material in the course will be from the following books.

[CLRS]	T. Cormen, C. Leiserson, R. Rivest, and C. Stein. Introduction to Algorithms (2nd edition). MIT Press / McGraw-Hill, 2001.
[MR]	R. Motwani and P. Raghavan. Randomized Algorithms. Cambridge University Press, 1995.
[V]	V. V. Vazirani. Approximation Algorithms.
[AMO]	. Ravindra K. Ahuja, Thomas L. Magnanti, and James B. Orlin. Network Flows: Theory, Algorithms, and Applications. Prentice Hall, 1993.

Useful Links

Succeeding in Algorithms Class

Interesting Algorithms Classes [1] [2] [3] [4]

Cheat Sheet

Advanced Computational Geometry

Some more material

The LEDA Book

How to Present a Paper in Theoretical Computer Science, by Ian Parberry.

Remember, choosing when to take Algos based on the professor teaching it is like trying to choose which barrel of boiling oil to swim in based on the color of the barrel. Besides, you'll probably have to take it more than once anyway. --Anonymous