Design & Analysis of Algorithms — COMPSCI 330 and COMPSCI 590 — Spring 2013

Design & Analysis of Algorithms

COMPSCI 330 / COMPSCI 590.4

Spring 2013

Instructor: Pankaj K. Agarwal

TAs: Sudhanshu Garg & Jiangwei Pan

UTA: Melissa Dalis

Times & Locations:

Lectures | Tue, Thu: 3:05-4:20 pm in French Science 2231 |

Recitations | Fri: 11:45am-1:00pm in Old Chem 116 |

Office Hours:

Agarwal: | Tue: 4:45-5:45 pm Fri: 2:45-3:45 pm (LSRC D214A) |

Garg: | Tue, Thu: 1:30-2:30 pm (FFSC 5316) |

Pan: | Mon, Wed: 3:00-4:00 pm (LSRC D309) |

Dalis: | Tue: 7:00-9:00 pm (The Link) Or by Appointment melissa.dalis AT duke.edu |

Discussion Forum/Mailing Lists:

Forum: | PIAZZA |

CPS330: | compsci330 AT cs.duke.edu |

CPS590.4: | compsci590.4 AT cs.duke.edu |

This undergraduate course covers techniques for designing and analyzing algorithms and data structures for a wide range of problems. Topics include:

- Design Techniques: Divide-and-conquer, recurrence relations, prune and search, greedy algorithms, dynamic programming, randomization, local search
- Data structures: Binary search tree, red-black tree, skip list, hashing, union-find, amortization
- Graph algorithms: graph traversal, strongly connected components, minimum spanning tree, shortest path
- Linear Programming: modeling, simplex algorithm, duality
- Algebraic algorithms: polynomial multiplication, FFT
- Intractability: Easy and hard problems, NP-Completeness, reducibility, approximation algorithms

CPS201 and 230 (formerly 100 and 102, respectively), or equivalent courses. This course requires undergraduate background in data structures as well as a certain amount of mathematical sophistication.

[DPV] | S. Dasgupta, C. Papadimitriou, and U. Vazirani, Algorithms, McGraw Hill, 2006. |

[KT] | J. Kleinberg and E. Tardos, Algorithm Design, Addison Wesley, 2005 (optional). |

[CLRS] | T. Cormen, C. Leiserson, R. Rivest, and C. Stein. Introduction to Algorithms. MIT Press, 2009. |

[Ta] | R. E. Tarjan. Data Structures and Network Algorithms. Society for Industrial Mathematics, 1987. |

[MG] | Jiri Matousek, Bernd Gartner. Understanding and Using Linear Programming. Springer Berlin Heidelberg, 2007. |

- Assignments (five out of six): 30%
- Midterm exams (two): 35%
- Final exam: 35%
- Both midterm and final will be in-class closed-book exams.
- For assignments, discussion among students is permitted, but students MUST write up solutions independently on their own. No materials or sources from prior years' classes or from the Internet can be consulted.
- Students are expected to use Latex or MS-word for writing their assignments and pdf files for submitting them.
- No credit is given for late solutions.