www.cs.amherst/~ccm/cs341/weeks.html
CS341 Syllabus
Books and Papers
The following books are on reserve in the science
library and available in the CS Lab.
Short sections will be assigned as background reading.
There will be additional readings based on the projects you select.
The short names in italics are used in the topics list.
- Gonzalo Navarro, ``A guided tour to approximate string matching,'' ACM Computing Surveys, Vol 33, No 1, March 2001, pp 31-88.
- Skiena: Steve Skiena, The Algorithm Deisgn Manual, Springer 2008.
- Guide: C. C. McGeoch, A Guide to Experimental Algorithmics, Cambridge Univ. Press, 2012.
- AlgEng: Matthias Müller-Hannemann and Stefan Schirra (Eds.) Algorithm Engineering, LNCS 5971, Springer-Heidelberg, 2010.
- Heuristic Search: Stefan Edelkamp and Stefan Schrödl, Heuristic Search: Theory and Practice, Elsevier/Morgan Kaufmann, 2012.
- Heuristics: Z. Michaelwicz and D. Fogel, How to Solve It: Modern Heuristics,
Springer 2004.
- JLB Jon Louis Bentley, chapter on spell checkers, Programming Pearls.
- DSJ David S. Johnson, ``A theoretician's guide to
experimental algorithmics.''
Week by Week Topic List
Expect changes! This list will evolve with the course!
- Week of Sept 2. Introduction to the course. Introduction of the first
research project: build a better autocorrect. Approximate string matching; data structures
for word lookups.
- The problem; approximate string matching; real-world issues.
- Handout: JLB chapter on spell checking.
- Read: Skiena Ch 6.4
- Read: Navarro on approximate string matching.
- Read: Guide on data structures for random text generation.
- Break into groups.
- Define your problem; identify design priorities; make a plan.
- For next week: do some web research to find a lexicon. Find some corpuses for
measuring word proximities.
- Sept 9. Algorithms and data structures. Approximate string matching. Data structures
for strings. Data structures for word distributions. Discuss your options and make your choices.
- Algorithms and data structures for approximate string matching.
- Application-specific issues: Incorporating probabilities;
how to break ties; what if there is a time constraint.
- Benchmark: Demonstrate a working front end/interface with a toy lexicon. Add
some probabilities or weights to control choices.
- Sept 16. How will you evaluate it?
- Tuesday. The big picture. Basics of experimental design and
data analysis. How to compare results among groups. Choosing an input testbed.
- Thursday. The nuts and bolts. What to measure, how
to measure, useful tools. Principles of graphical analysis and presentation.
- Sept 23. Make it faster. Principles of code design.
- Assignment Handout:
what to include in your presentation; your user manual;
your developer's manual; your paper.
- Tuesday: Tuning algorithms and data structures.
- Thursday: Tuning code.
- Benchmark: Be able to demonstrate a working prototype.
- Benchmark: Have a testbed and experimental design ready to go.
- Read: DSJ on experimental methodology.
- Sept 30. Code tuning; design.
what you did and how you did it. Performance analysis.
- Thursday: class project presentations.
- Overview of your design strategy; performance results.
- Due this week: user manual; developers manual.
- Oct 7. Introduction to NP hard problems; overview of algorithm and heuristic design
strategies.
- Exact algorithms.
- Costructive algorithms, approximation algorithms.
- Local search, metaheuristics, nature-inspired approaches, integer and linear programming.
- Due this week: final papers and performance analyses.
- Oct 14. FALL BREAK. Introduction to the application problems.
- Oct 21. Introduction to the application problems.
- Graph coloring and course scheduling.
- Steiner trees and path design.
- Combinatorial auctions and a resale/swap clearinghouse.
- QUBO and/or WM 2-SAT.
- Knapsack and fantasy leagues.
- A problem on social networks.
- Break into groups; make a plan.
- Visit the library to learn about research resources.
- Choose a paper to read and report on.
- Find problem testbeds and online resources.
- Oct 28. Constructive algorithms and heuristics for these problems.
- Benchmark: Demonstrate a working user interface for a toy instance.
- Papers and handouts.
- Nov 4. Local search. Hill climbing; tabu search; simulated annealing.
- Papers and handouts on local search.
- Nov 11. Student presentations of research papers. Evaluating the research papers.
- Benchmark: inputs and/or generators are ready.
- Nov 18. Other heuristic approaches. Nature-inspired heuristics; quantum annealing; linear programming.
- Benchmark: have a working prototype. Have testbed and experimental design
ready to go.
- Nov 25. THANKSGIVING WEEK
- Dec 2. Student presentations.
- Due: user manual; design manual.
- Dec 9. (Tuesday only). Student presentations and wrap up.
- Due: final papers and code.