About the Final Exam and the optional 1/4 unit project

1. Time and place

The final will be on May 11, Tuesday, 7-10pm, in our regular classroom -- Engineering Hall Room 106B6.

2. Format

The final will be a 3-hour close book examination. You are not allowed to bring any written material. It may be slightly advantageous to bring a calculator as there will be some calculations. However, you are only allowed to use the calculator for calculations; you are not allowed to use any additional functionality of a calculator.

3. Coverage

The test will cover all the lectures but with a clear emphasis on the topics taught after the midterm. A majority of points will be on the following key algorithms. Algorithms with a star are those for which you must know precisely all the details. For other algorithms, you must know the main ideas. The format of the questions will be similar to the midterm questions with the addition of some "true or false" questions, which can potentially cover all the topics we talked about in the class including those in the last two lectures.

Pairwise alignment
- Global: Needleman-Wunsch*
- Local: Smith-Waterman*
Multiple sequence alignment
- Exact: Multidimensional dynamic programming*
- Inexact: Feng-Doolittle progressive alignment
Hidden Markov models
- Finding most likely path: Viterbi*
- Computing sequence probabilities: Forward/Backward*
- Supervised training of an HMM*
Microarray data analysis
- Agglomerative Hierarchical Clustering: Single-link, complete-link, avg/group link*
- K-means clustering*
Phylogenetic tree construction
- Neighbor-joining*
- Maximum parsimony
Pattern mining
- Deterministic: SPLASH
- Sampling: Gibbs Sampler
RNA structure analysis
- Dynamic programming:Nussinov folding*
Protein structure analysis
- Improved Chou-Fasman approach

4. The optional 1/4 unit project

The project report is the only thing you need to turn in and it is due on May 14, Friday, midnight. You are welcome to turn it in earlier. Please send an email to the instructors as soon as possible if you feel that you cannot finish it by the deadline. You can turn in either an online copy or a hard copy of your report.