CS 8803 GA Graduate Algorithms

Eric Vigoda

 
Eric Vigoda
Creator, Instructor
 

Overview

This course is a graduate-level course in the design and analysis of algorithms. We study techniques for the design of algorithms (such as dynamic programming) and algorithms for fundamental problems (such as fast Fourier transform FFT). In addition, we study computational intractability, specifically, the theory of NP-completeness.  The main topics covered in the course include dynamic programming; divide and conquer, including FFT; randomized algorithms, including RSA cryptosystem and hashing using Bloom filters;  graph algorithms; max-flow algorithms; linear programming; and NP-completeness.  

Prerequisites

Students are expected to have an undergraduate course on the design and analysis of algorithms. In particular, they should be familiar with basic graph algorithms, including DFS, BFS, and Dijkstra's shortest path algorithm, and basic dynamic programming and divide and conquer algorithms (including solving recurrences). An undergraduate course in discrete mathematics is assumed, and students should be comfortable analyzing the asymptotic running time of algorithms.

Course Webpage

Detailed information will be available on the course webpage:  https://8803ga.wordpress.com

Homework, projects, and lecture material will be primarily distributed through the class website.

Grading

Grades will be based on a combination of homework, midterm exams, programming projects, and a final exam; the detailed breakdown will be announced at the start of the course on the current course web page.

Required Course Readings

The course uses the textbook Algorithms by Sanjoy Dasgupta, Christos Papadimitriou, and Umesh Vazirani. 

Other Info

Academic Honesty 

All Georgia Tech students are expected to uphold the Georgia Tech Academic Honor Code.