CPS 130 - SPRING 1999

CPS130
	Spring 1999		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

John H. Reif

Office: D223LSRC
Phone: 660-6568
Email: reif@cs.duke.edu
Office hours: Tues, Thurs: 12:30 - 1:30

Teaching Assistant

Ravin de Souza

Office: D339
Phone: 660-6594
Email: ravin@cs.duke.edu
Office hours: Tues, Thurs : 3:30 - 4:30, anytime by appt. (call me or send me mail)

Undergraduate Teaching Assistants

Charles S. Lin

Phone: 613-2445
Email:csl6@duke.edu
Office hours: Monday 7:00 - 9:00 p.m. , Teer Basement Lounge

Meeting Times

TTh 10:55-12:10 in D106 LSRC

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%).

Comments and Suggestions

Send anonymous e-mail to the instructor.

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: Thu Apr 22 08:54:36 EDT 1999