CPS 130 - FALL 1998

CPS130
	Fall 1998		Introduction to the Design and Analysis of Algorithms

Background

The course builds on the study of the analysis and implementation of data structures and algorithms from CPS100. The goal is to introduce a number of important algorithms that are interesting both from a practical and theoretical point of view.

Some specific topics include: sorting, searching, dynamic structure manipulation, pathfinding, fast multiplication, nondeterministic algorithms and computationally hard problems. Not open to students who have taken Computer Science 174.

Instructor

Michael L. Littman

Office: D209 LSRC
Phone: 660-6537
Email: mlittman@cs.duke.edu
Office hours: 2:00pm - 3:00pm Wednesday, 2:00pm - 3:00pm Thursday, 30 minutes after each class, any time for quick questions, other times by request (send email)

Teaching Assistant

Hao Cheng

Office: D327
Phone: 660-6587
Email: haocheng@cs.duke.edu
Office hours: 4pm-6pm Tuesday.

Undergraduate Teaching Assistants

Mike Strauss

Phone: 613-2304
Email: mcs2@acpub.duke.edu
Office hours: 10:30am-12:00pm Monday and Wednesday, outside of the computer lab at Teer. Also, night before homework due at 215-D Alexander (please check first to make sure).

Matt Peters

Phone: TBA
Email: mrp@acpub.duke.edu
Office hours: 6pm-8pm Monday and Wednesday, outside of the computer lab at Teer.

Jimmy Nguyen

Phone: TBA
Email: jdn1@acpub.duke.edu
Office hours: TBA

Spence Shepard

Phone: TBA
Email: shs2@acpub.duke.edu
Office hours: TBA

Iris Liu

Phone: TBA
Email: il@acpub.duke.edu
Office hours: 2-4 Tuesday and Thursday, at 2nd floor LSRC lab (fishbowl).

Geoff Berry

Phone: TBA
Email: gcb@cs.duke.edu
Office hours: TBA

Meeting Times

TTh 10:55-12:10 in 125 Engineering Research (go through Hudson).

Textbook

Introduction to Algorithms by Cormen, Leiserson, and Rivest (MIT Press, 1990). (bugs)

Prerequisites

CPS 100 or equivalent and four semesters of college mathematics.

Grading

Class grade will probably be based on:

written homework assignments (30%),
programming labs (10%),
two in-class exams (40%), and
a final exam (20%).

Animations

Here is a collection of the JAWAA animations we've used in class. (Revised JAWAA documentation.)

Naive multiplication algorithm
Russian Peasant's algorithm
Comparison of naive and russian
Euclid algorithm
Recursion Tree
Merge Example
Pivot Example
Non-JAWAA animated sorts: high-level, smaller set, Sort lab
Non-JAWAA: Interactive Splay Trees, Fancy Animated Splay Tree

Last modified: Sat Aug 15 09:00:07 EDT 1998 by Michael Littman, mlittman@cs.duke.edu