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.
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.
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
- 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.