This course is an in-depth study of the design and analysis of algorithms and data structures. We will look at ways of solving problems by a computer (e.g. sorting, combinatorial optimization on graphs), and study classic ways of organizing data to support their solution. Particular emphasis will be placed on expressing algorithms abstractly using pseudocode, proving their correctness, and analyzing their running time and memory requirements. We will also implement many of our ideas on a computer. Prerequisites: MATH 121 & 211 and basic programming proficiency. This should include familiarity with basic linked data structures and recursion.

Meets: 11:00am MWF in Physics 240A.
Course web: http://www.reed.edu/~jimfix/382

Instructor: Jim Fix
E-mail: jimfix@reed.edu
Office: Library 314
Office Hours: TBA or by appointment.

Required Text
Introduction to Algorithms by Cormen, Leiserson, Rivest, (and Stein).

Assignments
program 0: sorting by prefix reversals, using arrays and linked lists.
program 0 solutions: in many languages
homework 1: algorithm analysis, big-Oh, divide-n-conquer
homework 2: heaps, quicksort
homework 3: sorting lower bound, radix sort
homework 4: binary search trees
homework 5: balanced search tree variants
program 1: exploring,visualizing a graph
homework 6: graph algorithms
program 2: the z-box algorithm for exact string search
final: 3-hour take-home exam

Misc
sorting experiment
sorting applets
binary heaps
fast line intersection demo
search tree applet
SIGMETRICS paper on real BST performance

Course Outline
This should give you a rough idea of the weeks ahead but is subject to change.

Week 1: Introduction. Sorting. BubbleSort. MergeSort.
Week 2: Runtime analysis. Big-Oh notation. Recurrences.
Week 3: Elementary data structures. Priority queues.
Week 4: HeapSort. QuickSort. Sorting lower bound.
Week 5: Ordered dictionaries. Binary search trees.
Week 6: AVL trees. Splay trees.
Week 7: Graph search
Week 8: *spring break*
Week 9: Shortest paths, minimum spanning trees
Week 10: Matroids, the greedy algorithm
Week 11: Exact string search
Week 12: Suffix trees, dynamic programming
Week 13: NP Completeness

Responsibilities and Evaluation

There will be weekly or semi-weekly written homework assignments based on the lecture and reading material. In addition, there will be three implementation projects. The homework and projects will be a significant portion of the final evaluation. There will be a take-home mid-term exam and a final exam worth approximately 15-20% and 20-25%, respectively.

Late work will not be given full credit.

Computing Resources and Tools

My preference would be that students use the Java programming language since this is the natural continuation from MATH 121. It also allows me to provide infrastructure for some of the projects, and execute them on my machines. However, if you have a strong preference to code an assignment in another language and system, talk to me. Note: my preference for Java is waning this semester.

Sun's Java Development Kit is available on the UNIX servers, the Linux machines in L-382, and on the Macs in the IRCs. Sun's JDK includes the javac compiler, the Java interpreter java, and an applet runner appletviewer. If you wish to use your own computer, you can download the JDK from Sun's web site. Just transfer your completed assignments to your home directory for my evaluation.

You can get an account and access to the machines and lab in L-382. These machines run Linux and have many useful development tools and more. I recommend using this course as an opportunity to become facile with Unix/Linux if you have not already. To obtain L-382 access, talk to me at the beginning of the semester.

Course Mailing List

I will use math382-s@lists.reed.edu to post announcements about the course. Check your e-mail regularly. Feel free to use the mailing list to discuss the course.