CS 34 Applied Algorithms: Syllabus

Submitted by Catherine C. McGeoch on Saturday, 4/24/2010, at 11:04 AM

 

Jan 25.  Introduction.  The gap between theory and practice.   

  • For Thurs:  Surf the web to see what you can learn about the following problems:  Traveling Salesman Problem;  Graph Coloring;  Single-Pair Shortest Paths;  Reconstructing Phylogenies.   Save the links.

  • Assignment for next week:   Think about implementing  an exhaustive search method  for Graph Coloring, using the framework provided in class.   We will discuss this on Thursday. 

Feb 1.  Algorithm Engineering and  Algorithm Design.   Tuesday we will survey algorithm engineering, algorithm tuning, and code tuning ideas.  Thursday we will apply these ideas to the exhaustive search algorithm(s); and survey parsing and randomization tricks. 

  • For Tues: JLB, Faster and faster yet.
  • For Tues: JLB on performance tuning
  • Bader et al.  on Engineering Algorithms for Optimal Phylogenies
  • Skim:  Schirazi on Java Performance Tuning 
  • Assignment (start this week):   Add branch-and-bound,  algorithm tuning, and code tuning ideas to your exhaustive search implementation.   Keep separate copies of original and tuned implementations.  

Feb 8.   Tuning Algorithms + Analyzing  efficiency ( What to measure).   On Tuesday we will finish our discussion of algorithm tuning.  On Thursday we will consider ways to measure algorithm and program efficiency.  

  • For Tues: No readings.  We will finish our discussion of algorithm tuning.
  • For Thursday:  CCM on What to Measure.

Feb 8.  Analyzing program performance.  Tuesday lab work on Unix tools and tips on measuring algorithm performance.   Thursday lab work on R, a data analysis package.  The lab meets in 007 Seeley Mudd building (basement level).

  • Tuesday Lab work using Unix timing tools and shell scripts, discussion of scaffolding.
  • Thursday Lab work using R for data analysis.
  • Assignment (due March 8):   Apply branch-and-bound,  algorithm tuning, and code tuning, and memory-based tuning to your exhaustive search algorithm for graph coloring.   Measure the results.  Write a paper describing your results.  

Feb 22.  What Statisticians Know.   Basics of experimental design and data analysis.

Mar 1. Discussion of the class projects: Schedule school bus routes for the Amherst Regional School System,  and  Schedule rooms (and courses) at Amherst College. 

  • Tuesday:  A visitor from the Registrar's office to discuss course scheduling.
  • Thursday: A visitor from IT to discuss online mapping tools.
  • Assignment:   Due April 29;  an implementation and (written) progress report are due April 12.  Implement a solution to one of the application problems.   Evaluate it on a well-chosen testbed of instances.  Write a paper describing your results.

Mar 8.  Coping with NP-Hard problems.  We will  discuss constructive and approximation algorithms for TSP and Graph Coloring, and decide on a handful of promising candidates for our applications. Assignment: Come to class prepared to explain at least one (two if you can) promising TSP and one GC  algorithm.  It should be a constructive algorithm.    What are its merits (theoretically and/or experimentally), and why do you think it could work for our problems?   Here are some resources to try. 

You should understand the algorithm well enough to write pseudocode on the board, and explain why it would be a good possibility. 

  • Surf: Joseph  Culberson's  Graph Coloring Resources Page.  
  • Surf:  Skiena's   Stony Brook Algorithm Repository.
  • Surf:  DIMACS Implementation Challenges.   The Second Challenge (1993) was on Graph Coloring (and two related problems).  The Eighth Challenge (2001) was on TSP.
  • Skim:  The Traveling Salesman Problem: A Computational Study, by Applegate and Cook (in AC Science Library). 
  • Skim:  The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization,  E.L. Lawler, editor (in AC Science Library).
  • Skim: The Traveling Salesman Problem and its Variations, by Gutin and Punnen.   Available electronically from Frost Library.
  • First Paper is DUE. 
  • Tuesday: We discuss algorithms and decide who's doing what.
  • Thursday: A lecture on parsing.

Mar 15. Spring Break.

Mar 22.  Heuristic search -  Local Search: Hill Climbing,  Tabu Search, Simulated Annealing.   On Tuesday we will discuss these heuristic approaches to problem solving.   Assignment for Thursday:  Read one research paper from the list (as assigned).  Also read Hooker on experimental methodology.  Be prepared to report on:  (1) the problem analyzed in this paper;  (2) how the heuristic is applied to the problem (what neighborhood, objecctive function, etc); (3) what other algorithms are being compared;  (4) how well the heuristic performs; (5) do Hooker's criticisms apply to this research (evaluate the quality of the work). 

Mar 29. Other Strategies for Optimization Problems:   Tuesday surveys:  Hybrid metaheuristics, evolutionary algorithms,  Linear Programming and Integer Programming approaches.   Thursday: examples with experimental work (the Lagrangian Relaxation paper is a survey/tutorial). 

Apr 5.   Constraint satisfaction problems + Progress Reports.

Apr 12.   Memory-efficient algorithmics.  Cache-efficient and I/O efficient strategies.

Apr 19.  I/O - Efficient Algorithms  and Massive Data Sets:   Tuesday:  student reports on last week's I/O-efficient algorithms.   Thursday:  problems on streaming data,  everybody skims the three papers below.

Apr 26.    Bioinformatics: Sequence alignment and phylogeny reconstruction.

  • Tuesday:  Lecture on the terminology and problems of sequence alignment and phylogeny reconstruction. 
  •  Th:  Kuhner and Felsenstein, ``Simulation comparison of phylogeny algorithms under equal and unequal evolutionary rates,''   Mol. Bio. Evol.  11(3) pp 439-468.
  • Th: Leaver-Fay,  et al.,  ``Faster placement of hydrogens in protien structures by dynamic programming,'' JEA V12 No 2.4  June 2008.
  • Th: Swenson et al,  ``Approximating the true evolutionary distance between two genomes,''  JEA V12 N 3.5, August 2008.
  • Th: Wan et al, ``Phylogenetic methods for the analysis of genome rearrangmenet data: an empirical study.'' 
  • Th: Doring et al, ``SeqAn: An efficient generic C++ library for sequence analysis,''  BMC Bioinformatics, 2008, 9:11.  
  • Th: Sundquist et al, ``Whole-Genome sequncing and assembly with high-throughput, short-read technologies,  PLoS ONE  www.plosone.org, May 30, 2007

May 3.  Final Project reports.

  • Papers due; reports in class.