Computational Molecular Biology



Algorithms:

Fall 2011 (30 - + meetings, ~15 weeks)

|Date |Activities Planned |Comments |

|Aug 23, T |Intro, obviously! |Asked stds to implement Fibonacci recursive and |

| |2. Max-sub-sum alg |iterative code to check time-growth with input. |

| |3. #arcs on complete graph: Inductive pf. | |

|Aug 25, R |Divide & conquer: Insertion sort-proof, |Asked: implement quick sort. |

| |Merge Sort, Quick Sort, Quick sort-cases | |

| |Recurrence Eq | |

|Aug 30, T |Comp-sort-omega, count-sort | |

| |D&Q: Matrix Mult, Strassen Alg, FFT | |

|Sep 1, R |D&Q: FFT |Asked: complete recursive-FFT algorithm stepping |

|(Drop w/o W grade, Sep |UG Prog Asnmnt 1: Max-sub-Seq |with 8 co-eff. |

|2) |Grad Prog Asnmt 1: complete FFT example: |In-class assignment on Sep 8 Thursday, 40 min. |

| |hard copy submit in next class | |

|Sep 6, T |--- |Project announced |

|(Sep 5, Labor day) | | |

|Sep 8, R |FFT contd. |ok |

| |Quiz 1– OPEN BOOK, 40 min, syllabus – up to | |

| |this point | |

|Sep 13, T |DP 0-1KS, |I need project grouping information |

| |Matrix chain mult introduced | |

|Sep 15, R |DP Matrix chain mult. | |

|Sep 20, T |DP: Optimal Binary-tree organization |(1) Opt bin-search tree organization: Grad |

| | |syllabus. |

| | |(2) Floyd-Warshan all pairs shortest path: read |

| | |yourself, both Grad & UG |

|Sep 22, R |Greedy: Multi-proc Last-FT, | |

| |Huffman encoding , | |

| |Rational-KS | |

|Sep 27, T |ME: complexity of Huffman |Given a set of coeff evaluate at corresponding |

| |Presentations/ Demo: Grad groups |omega’s |

|Sep 29, R |Backtracking: basics, 0-1KS, Bounding fn | |

| |Grad Project demo finished | |

|Oct 4, T |Backtracking: Game search |UG Project-1 report due |

| |Graph Alg: Basics, | |

| |Intro to topological sort | |

|Oct 6, R |Topological-sort, |UG: Project-2 Phase-1 report due |

| |Q-based topo-sort | |

| |Djikstra’s algorithm | |

|Oct 11, T |- - - - - | |

|(Fall Break Oct 10-11) | | |

|Oct 13, R |Guest lecture |Need more discussion (expt methodology, results, |

| | |space consumption, etc.) on Proj-1 report, I will |

| | |discuss & return previous reports, |

| | |Resubmission DUE: Nov 1 |

|Oct 18, T |Discussion of UG reports |UG Proj2: Everybody has same game! (1) I may ask |

| |Graph Alg: Dijkstra & proof Graph Alg: DFS, |competetion between teams, or (2) compare codes |

| |SCC |between teams by an automated tool. |

|Oct 20, R |UG Presentations/ Demo |UG Project-1 demo: you may improve your grades by |

| |Project-1: Looking for GUI targeted to |rearranging your demo again in my office, before |

| |general public |the final exam date! |

| | |Grades spreadsheet is online now |

|Oct 25, T |Quiz2 on DP including Floyd-Warshall alg, |40pts, open book+my lecture notes minus any |

| |Greedy, BackTracking, Graph Alg |personal notes, electronic aids, etc… |

|Oct 27, R |NP-hardness basics, SAT | |

|(Drop with ‘W’, Oct 28)| | |

|Nov 1, T |NP-hardness: proving 3SAT is NP-C; |UG Proj1 Phase1 report |

| |What to do with NP-C problems; |Re-submission |

| |Complexity FAQ | |

|Nov 3, R |Complexity theory: FAQ |Read on motivating scenario in the Linear |

| |Linear Programming: intro |Programming Chapter |

|Nov 8, T |UG Presentations/ Demo: Proj-2 |10 min each group: Explain the game, do a sample |

| | |run, your GUI, your source code, board evaluation |

| |Quiz 2 papers return and discussion |function, and answer questions… |

| | |10 min compete pairing groups: Play against |

| | |another group’s program: Good job, 2 groups! |

|Nov 10, R |Linear Programming: Ch 29 |Everyone who made ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download