Fall 2014 CS7800: Advanced Algorithms

Fall 2014 CS7800: Advanced Algorithms

OVERVIEW

This course will present advanced techniques for the design and analysis of algorithms. The course is divided into two parts. Part I, weeks 1 through 6, will cover fundamental design techniques, optimization methods, and graph algorithms. Part II, weeks 7 through 14, will cover selected advanced topics including linear programming, algebraic techniques, and approximation algorithms. Here is a tentative list of topics that will be covered:

•Graph algorithms: minimum spanning trees, shortest paths, and network flows

•Design techniques: divide and conquer, dynamic programming, greedy algorithms, algebraic methods, rounding linear programming relaxations

•Analysis techniques: asymptotic analysis, probabilistic analysis, average-case analysis, and amortized analysis

•Selected general paradigms: matroid theory, linear programming

•Lower bounds and NP-completeness

•Introduction to approximation algorithms

•A subset of other advanced topics: Markov chains, Fast Fourier Transform, expander graphs, number-theoretic algorithms

TEXTBOOK

Introduction to Algorithms, by T. Cormen, C. Leiserson, R. Rivest, and C. Stein, MIT Press, 2009

(Available at the bookstore and online)

Two other recommended texts are Algorithms, by Dasgupta, Papadimitriou, and Vazirani, and Algorithm Design, by Kleinberg and Tardos.

PREREQUISITES

This is a PhD core course; if you are not a PhD student in the college, then you need to get approval from the instructor. The course will be fast-paced and will cover a number of advanced topics in algorithms over the 13-week period. A good test to find out whether you are well-prepared for taking this course is to look over material from the following chapters of the textbook: 1-4, 6-7, 10-12, and 22. If you have studied the material in these chapters and are comfortable with it, then you are well-prepared. Otherwise, you should talk to the instructor before taking the course. Also it is highly recommended that you review the mathematical background covered in Appendices A, B, and C.1-C.3 by the end of the first week of class.

GRADING

Grades will be based on six problem sets (24%), 2 midterms (20% each), a final exam (30%), and class participation (6%).

CLASS PARTICIPATION

There are two components that make up class participation (6%).

•Each week, a ``Problem of the Week'' (or two) will be handed out, and a student will be called on to present his/her solution to the problem in the following week's class, and submit a writeup on the problem. Everbody is required to present once during the course. The quality of the presentation and writeup will determine the grade (3%).

•The remaining 3% will be determined by participation in class discussions and the discretion of the instructor.

IMPORTANT POLICIES

Problem sets are due at the beginning of class on the due date. No late submissions will be accepted! Tentative out/due dates for the problem sets are listed in the schedule.

Collaborating with other students in the class on homework problems is fine and encouraged, though we urge you to attempt working out all of the problems by yourself first. In any case, you must write up your solutions, in your own words. Furthermore, if you did collaborate on any problem, you must clearly list all of the collaborators in your submission.

Class:

MW 14:50-16:30

Intl. Village 22

240 WVH

Office Hours

M 17:05-18:05

Th 13:35-14:35

Discussion Forum