This course is an in-depth study of the design and analysis of algorithms and data structures. We will look at ways of solving combinatorial problems (e.g. sorting, network optimization, string search), and study classic data structures to support their solution. Following the text, we'll emphasize an abstract approach: We give algorithms in pseudocode, carefully prove their correctness, and analyze their performance. We'll also be implementing many of our ideas as real executable code.
Prerequisites: MATH 121 & 211 and basic programming proficiency in a language like Java or Python. You should already be familiar with linked data structures and recursion.

Meets: 12:00pm 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.

Assignments

homework 0 CLR(S) chapter 2.3-3,2.3-5,2-3ab,2-4abcd
program 0 write code for binary search, a sorting algorithm, and for constructing and querying a random bipartite graph.
homework 1 big-Oh, recurrences
program 1 write code for the polynomial arithmetic functions of homework 1
homework 2 quicksort, heaps
homework 3 binary search trees
homework 4 AVL and splay trees
homework 5 hashing, lower bounds, count sort
homework 6 graph search
program 2 write code that does one of the following:
   constructs a random maze represented as a spanning tree
   builds an image mosaic using bipartite matching
   analyzes or visualizes the graph structure of the web or a social network
There's also some possible starting code below under "resources"
homework 7 CLR(S) chapter 26.2-9,26.3-4,15-6,code for 15-3
homework 8 CLR(S) 32-1a,c. and also these exercises:

• using the z[...] found by the z-box algorithm, describe a method to find the longest prefix that occurs at least two other places in the string, and also the shortest prefix that occurs at only one other place.
• using a suffix tree for S, describe a method for finding the longest repeated substring and a method for finding the shortest non-repeated substring of S
• given a suffix tree for a string T and a pattern string P, describe a method that finds all occurrences of P in T, allowing for one substitution.

Lecture Misc. and Resources

Note: Some of this can be found in my Public/math382 AFS folder.

a few implementations of bubblesort.

• to compile the C code type "gcc -o bubblesort1 bubblesort1.c"
  
• to generate assembly type "gcc -S bubblesort1.c"
  
• to run the Python code type "python bubblesort1.py"

lectures about heaps, bsts and line intersection, geometic search
a binary heap package and heapsort.
a Java program that demonstrates line intersection

starting code for BSTs in python, Java, and C
a Java applet that demonstrates balanced BSTs
a paper describing AVL trees
Sleator & Tarjan paper describing splay trees

some nuggets of code that might be useful for program 2:

• Nurikabe for grid graphs and trees in Java and C
• Last year's web crawling project in Java
• Simple image file "pixel extraction" in Java for analyzing grey images, and color images.

Andrei Broder paper on uniform generation of spanning trees Bill Casselman's text on using PostScript for mathematical illustrations.

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

Supplemental Texts (on Library Reserve or in L-382)
Algorithm Design by Kleinberg and Tardos. (on reserve)
Algorithms by Dasgupta, Papadimitriou, and Vazirani. (on-line)
Data Structures and Algorithms in Java by Goodrich and Tamassia. (in the lab)

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

Week 1: Introduction. Sorting. BubbleSort. Runtime analysis. Quicksort.
Week 2: Big-Oh notation. Recurrences. Elementary data structures. Line Intersection.
Week 3: Binary heaps and HeapSort. Ordered dictionaries. Binary search trees.
Week 4: AVL trees. Splay trees. Amortized analysis.
Week 5: Graph search.
Week 6: Shortest paths. Minimum spanning trees.
Week 7: Matroids. The greedy algorithm.
Week 8: *spring break*
Week 9: Matroids. Greedy algorithms.
Week 10: Network flows. Matching. Linear programming.
Week 11: Dynamic programming.
Week 12: Suffix trees. Exact string search.
Week 13: NP-Completeness. Approximation algorithms.

Responsibilities and Evaluation

There will be written homework assignments based on the lecture and reading material, roughly, every week. In addition, there will be implementation projects, typically three. The homework and projects will be a significant portion of the final evaluation. There will be a take-home final exam and a final exam worth about 15-20%.

Late work will not be given full credit.

Computing Resources and Tools

My natural preference is that you use the Java programming language since this is the natural continuation from MATH 121. The strength of my preference for Java is waning this semester so for alternatives, you might consider C, Python, or Ruby. These share similar constructs, are readily available on any system, and have many resources on the web. Have another language in mind? Talk to me.

Using Java (and possibly the others above) allows me to provide infrastructure for the projects and to give specific implementation advice in lecture. If you use another language, just be sure you meet the spirit of the implementation project assignments. E.g. a program flexing your understanding of linked lists should not rely on prebuilt APIs or language support for lists.

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 and the Java interpreter java. 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.