329E, Spring 2009, Tandy Warnow

Homeworks

• Homework #1, due January 27, in class.
• Homework #2, due Feb 5, in class. Please see this for notes on how to do some of these homework questions, and this for solutions.
• Homework #3, due Feb. 19, in class:
  • See Quiz 1, and rewrite solutions to every problem in this quiz for which you did not get full credit.
  • Prove that the ratio between lg(x) and ln(x) is a constant (where lg(x) is the log, base 2, of x).
• Homework #4, due March 10, in class.
• Homework #5, due March 24, in class. (Click here for solutions.)
• Homework #6, due April 7, in class. Click here for solutions.
• Homework #7 is to write up solutions, in detail, to every question on Quiz #3 that you did not get full points for. This homework is due on April 21, in class.

• (Jan 20 and 22) (PDF), (PPT).
• (Jan 27) Problems, algorithms, and running time analyses (PPT) (PDF)
• (Jan 29 and Feb 3) Induction, etc. (PDF) (PPT)
• (Feb 26) Phylogeny estimation (PDF) (PPT)
• March 3: Why dynamic programming and recursive algorithms work
• March 5: Dynamic programming for maximum parsimony and pairwise alignment (PPT) (PDF)
• March 10: Dynamic programming for "all pairs shortest path" (HW 4 due) (PPT) (PDF)
• March 12: Recursive algorithms
• March 24: Review (HW 5 due)
• March 26: QUIZ 2
• March 31: Combinatorics (PPT)
• April 2: Combinatorics
• April 7: Combinatorics (HW 6 due) We covered the Inclusion-Exclusion Principle. You can read about this on wikipedia, here, or at various sites (including this one).
• April 9: QUIZ 3
• April 14 and 16: Biological applications (Sequencing by hybridization at (PPT) and (PDF).)
• April 21-April 30: student project presentations (HW 7 due 4/21)
• April 21: (1) Ben Boral and Uriel Brener: discussion of paper by Edward Marcotte on identifying interacting proteins (PPT). (2) Rianna Richardson, Rubik's Cube.
• April 23: (1) Lauren Waelder, on The African Eve (PPT). (2) Andrew Oldag, "Programming a computer for playing chess" by C. Shannon, Philosophical Mag. Ser 7, Vol. 41, No. 314, March 1950 (PPT). (3) Matt Brown (PPT), Boyer-Moore string algorithm.
• April 28: (1) Laksman Veeravagu and Luis Barrera, on Dijkstra's shortest path algorithm (PPT) (2) Jun Park, talking about the birthday problem (PDF). (3) Josh and Julio, talking about the semantic web (PPT).
• April 30: Ben Casey talking about the Game of Nim (PPT), Vladimir Coxall talking about the Travelling Salesman Problem (PPT), and Mike Souza about Evolutionary Computation (PDF).
• May 5 and 7: Review of the course and last quiz.

Class Notes:

• Notes on algorithms, problems, and running time (PDF)

Suggested reading from Jones and Pevzner

• Evolutionary trees: Chapter 10, sections 10.5-10.8
• Pairwise alignment: Chapter 6, sections 6.4 to 6.6
• Algorithms and Running Time: Chapter 2, sections 2.1 to 2.9
• The "Rock Game": Chapter 1

Suggested topics for final projects

• Local Sequence Alignment (text, pages 180-183)
• Gene Prediction (text, pages 193-202, but focus on Exon Chaining)
• Motif Finding (text, pages 91-100, 108-111, 136-137)
• Manhattan Tourist (text, pages 153-160)
• The Birthday Problem (evaluating the probability that at least two people in a group of N people share a birthday, see this Wikipedia page
• Approximation algorithms (recommendations: Vertex Cover, and Travelling Salesman)
• Stable Marriage
• The Game of Nim
• The Linear Time Majority algorithm (Boyer and Moore)
• Dijkstra's shortest path algorithm
• The African Eve hypothesis
• Minimum Cost Spanning Tree algorithm
• Horizontal Gene Transfer

  Office hours week of May 11:

  • May 11, 2-3
  • May 12, 2-4
  • May 13, 4-5.