Lectures
-
Weeks 1-2: String Matching: Exact Matching.
- Algorithms on Strings, Trees and Sequences, Gusfield.
- Cormen, Ch 34.
- Design and Analysis of Computer Algorithms, Aho, Hopcroft and Ullman.
Topics:
- Introduction
- Matching with Finite Automata
- Rabin-Karp
- Knut-Morris-Pratt
- Boyer-Moore
- Matching with Suffix Trees
-
Week 3:
-
Computers and Intractability: A Guide to the Theory of NP-Completeness. Garey & Johnson.
- Handbook of Combinatorics. Graham, Grotschel and Lovasz. (Ch. 28).
- The Traveling Salesman Problem. Lawler, Lenstra, Rinnooy Kan, Shmoys.
Topics:
- Introduction to NP-Completeness
- Brief overview of general heuristics: local search , greedy , simulated
annealing , genetic algorithms .
- Greedy algorithms for TSP , Bin packing and knapsack with
performance bounds .
-
Week 4-6: Greedy algorithms and Simmulated Annealing.
Simulated Annealing and Boltzmann Machines, Aarts and Korst. Chapters 1-3.
Topics:
- Minimum Spanning Tree (Kruskal Prim).
- Nearest Insertion.
- Heuristics for TSP with triangle inequality.
- Christofides algorithm -- greedy TSP with bound 3/2.
- TSP with no triangle inequality is non-approximable.
- General Framework of Greedy Algorithms and matroids.
- Simulated Annealing.
-
Week 7: ORFans.
-
Week 8: Blind Search Algorithms and Informed Search.
Russel and Norvig, "Artificial Intelligence - A Modern Approach", Prentice Hall, 1995.
Topics:
- BFS, DFS, UCS, DLS, IDS, Bi-directional
- A*, IDA*, SMA* and other heuristics.
-
Week 9: Iterative Improvement Algorithms
Topics:
- More on Hill Climbing, Greedy, Simulated Annealing.
-
-
Week 10: Alignments and Dynamic Programming.
- Algorithms on Strings, Trees and Sequences, Gusfield.
- Biological sequence analysis. Durbin, Eddy, Krogh, Mitchison.
Topics:
- Edit distance, string alignment, Dynamic Programming.
- String similarity.
- Global and space free alignments.
- Local and local suffix alignments.
- Gapped Alignment.
-
Week 11: More on Gapped Alignment.
- Gusfield.
- Setubal & Medianis: Introduction to Computational Molecular Biology.
Topics:
- Arbitrary gaps.
- Affine and constant gaps.
- Convex gaps.
- Space and Time speedups.
- DNA computing.
- TSP with DNA.
-
Week 12: Genetic Algorithms
Topics:
-
Week 13: Hidden Markov Models
- Biological sequence analysis. Durbin, Eddy, Krogh, Mitchison.
Topics: