[pattern]
MATH 382:
Algorithms & Data Structures


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 then analyze their performance. We'll also be implementing some of our ideas in Python.

Prerequisites: MATH 121; at least one of MATH 112 and MATH 113

Instructor: Jim Fix, jimfix@reed.edu, Library 314.

Please note: Below is the schedule of the Spring 2013 version of the course. The Spring 2016 version will cover more now that we offer MATH 221.

Course Outline

Week 1-2: Overview of course. Sorting case study.
Week 2-3: Runtime analysis. Big-Oh notation.
Week 3-4: Recurrences. Quicksort case study.
Week 5: Randomized quicksort. Sorting lower bound. Count sort. Radix sort.
Week 6-7: Graph Search using elementary data structures.
Week 8: Break.
Week 9: Link-based data structures; priority queues
Week 10: Binary heaps
Week 11-12: shortest paths; dynamic programming
Week 13: Hash tables for unordered dictionaries.
Week 14: Binary search trees as ordered dictionaries. Geometric data structures.

Computing Resources

I've chosen Scala as the programming language for both of my 300-level courses.  It has features found in Haskell and also those found in Java; I'm seeing real advantages to this combination, and to you having a large cohort (other MATH 382 students and also those taking MATH 384) learning the language together. Having everyone in the class use Scala (as opposed to allowing any language of choice) allows me to provide infrastructure for the projects and also to give specific implementation advice in lecture.

You should also 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.

Scala is available on the L-382 and ETC machines. You can also download Scala for free from the Scala web site to get a copy of the scalac compiler and the Scala interpreter scala.


Texts

Required:
Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein.
Algorithm Design by Kleinberg and Tardos.

Supplemental:
Algorithms by Dasgupta, Papadimitriou, and Vazirani.
Data Structures and Algorithms in Java by Goodrich and Tamassia.