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

Source: georgehart.com

Source: georgehart.com

Administration

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:

LecturesTue, Thu: 3:05-4:20 pm
in French Science 2231
RecitationsFri: 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

Overview

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

Prerequisite

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.

Textbooks

[DPV]  S. Dasgupta, C. Papadimitriou, and U. Vazirani, Algorithms, McGraw Hill, 2006.
[KT]J. Kleinberg and E. Tardos, Algorithm Design, Addison Wesley, 2005 (optional).

Reference Books

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

Grading

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

page top