Computer Science 341

`www.cs.amherst.edu/ccm/cs341/`

Computer Science 341: Applied Algorithms, Fall 2013

Course Overview

This course is about understanding -- and shrinking -- the gap between theory and practice in algorithm design and analysis. Theoretical bounds on algorithm performance are important to know, but theory is not always adequate to answer our questions about performance in the real world. This is especially true with algorithms and heuristics for NP-Hard problems. We will look at how experiment-driven design and analysis can be used to ``flesh out'' the theory, to produce faster programs and tighter predictions about their performance. Students will undertake two projects to implement programs to solve real-world problems, and participate in seminar-style discussions of research papers in experimental algorithmics.

Course Information

The course instructor is Catherine McGeoch. My office is Room 401, Seeley Mudd Building. My phone number is x7913.
You can send me email at .
We meet TuTh at 2:30pm in Seeley Mudd 207. Some class sessions will meet in one of the labs (006, 007) on the basement level of Seeley Mudd.
Office hours: I am available for drop-in conversations MW afternoons, after 2:00. Or send me a note to set up an appointment for another time.

Grades will be based on:

Two research projects carried out in small groups. In each, you will be given a real-world problem and asked to: define the abstract problem, research your options and implement a suitable algorithm or heuristic, develop experiments to evaluate it, and write a paper describing your results.
Much of the class time will be conducted in seminar style: you will be responsible for showing up participating in in-class discussions.
There will also be a few additional small assignments and presentations. For example everyone will read a reasearch paper and present it to the class.

Your work on the first project (code, reports, and a paper) represents 1/3 of your grade; this will be a combination of a group grade for the overall product, and an individual grade (mostly based on your contribution and on your paper). The second project will also count for 1/3 of your grade, and will be evaluated in the same way. Your overall contribution in course discussions and presentation of the research paper will make up the other 1/3 of your grade.

Here is a syllabus and topic list.