Algorithms

CSCI400, Fall semester, 2009

 To the Bottom of the Page

 

Instructor:         Dr. Shieu-Hong Lin

Email:  

Class: Tuesday & Thursday 10:30~2:45 pm, BUSN 210

Office Hours: Tuesday & Thursday 10:30~11:45 pm, Math & CS department

 

Books:

  • Jon Kleinberg and Eva Tardos. Algorithm Design, Addison Wesley, 2005.
  • Jones & Pevzner, An Introduction to Bioinformatics Algorithms, MIT Press, 2004.

 

Course Syllabus

 

About weekly progress report:`

  • By Thursday each week, you should spend around 5~10 minutes to write a brief progress report (see this template) regarding the latest progress made in this class, and email the report to Dr. Lin.

 

 

Week 1: Molecular Biology Primer. Progress report due: Thursday, Sept. 3

  • Reading #1: Sections 1~6 of Chapter 3 in the online slide set for Intro to Bioinformatics Algorithms. Discussion: Matthew Shaw and Josh Lawman, Tuesday Sept. 1
  • Lab #1: (i) Read Section 2.4 of Algorithm Design. (ii) Download and unzip this C++ project to feel the amount of time taken by Q(n log n), Q (n2), and Q (n5) algorithms. Start from n=100, …1000, …10000 and so forth as far as your patience allows and report your findings in the progress report. (iii) Add your own code to the project so that we can simulate the amount of time taken by Q(2n) algorithms. How much time do you think it may take to complete 2n steps of computation when n is 60? Explain why you come up with the estimates and the your underlying assumptions.

 

 

 

Week 2: Exhaustive Search and More on Algorithms for Bioinfomatics Applications. Progress report due: Thursday, Sept. 10

  • Reading #2: Sections 7~8 of Chapter 3  and the whole Chapter 4 in the online slide set of Intro to Bioinformatics Algorithms
  • Discussion of reading#2: Matthew Stoumbaugh and Trevor Harwell

 

Homework #1: Exhaustive search and the mixture sequence problem. Due: Thursday, Sept. 10

 

 

Week 3: Introduction to Greedy Algorithms. Progress report due: Thursday, Sept. 17

  • Reading #3: (i) Read Sections 4.1~4.7 of Algorithm Design (also see this slide set) on greedy algorithms.  (ii) Read this Wikipedia article on greedy algorithms.
  • Discussion of reading#3: Stephanie Greer  and Caleb Bergthold,

 

Week 4: More on Greedy Algorithms. Progress report due: Thursday, Sept. 24

Homework #2: A branch-and-bound approach to the mixture sequence problem. Due: Thursday, Sept. 24

Test cases for Homework #2:  Consider the two sequences

A =<18, 29, 31, 42, 55, 66, 71, 85, 91, 103, 114, 128, 135, 140, 155, 81, 93, 17, 24, 65, 39, 27, 58, 19, 130, 141, 182, 153, 104, 115, 18, 29, 31, 42, 55, 66, 71, 85, 91, 103, 114, 128, 135, 140, 155>,

B =<81, 93, 17, 24, 65, 39, 27, 58, 19, 130, 141, 182, 153, 104, 115, 18, 29, 31, 42, 55, 66, 71, 85, 91, 103, 114, 128, 135, 140, 155, 81, 93, 17, 24, 65, 39, 27, 58, 19, 130, 141, 182, 153, 104, 115 >, and

the following target sums: (i) 2955, (ii) 2987, (iii) 2995, (iv) 4119, (v) 4129, (vi) 4139, (vii)3534, (viii) 3539.

 

Week 5: Test and review

     Take-home Test 1 on Greedy algorithms (Due: Thursday, Oct. 1)

 

 

Week 6: Introduction to Divide and Conquer. Progress report due: Thursday, Oct. 8

  • Reading #6:  Sections 5.1~5.7 of Algorithm Design (also see slide set on inversion counting and integer multiplication) on greedy algorithms.
  • Discussion of reading#6: Joshua Chezum and Jeremy D. Fu

 

 

Week 7: More on Divide and Conquer. Progress report due: Thursday, Oct. 15

  • Reading #7: Review chapter 5 in Algorithm Design

 

 

Week 8: Review; Torrey Conference. Progress report due: Thursday, Oct. 22

  • Homework #3: A divide-and-conquer approach to the mixture sequence problem. Due: Thursday, Oct. 22

Test cases for Homework #3:  Consider the two sequences again

A =<18, 29, 31, 42, 55, 66, 71, 85, 91, 103>,

B =<81, 93, 17, 24, 65, 39, 27, 58, 19, 130>, and

the following target sums: (i) 350, (ii) 450, (iii) 500, (iv) 550, (v) 600, (vi) 650

 

Take-home Test 2 on Divide and Conquer (Due: Thursday, Oct. 22)

 

 

Week 9: Introduction to Dynamic Programming. Progress report due: Thursday, Oct. 29

  • Reading #9:  Section 2.2 on Asymptotic Order of Growth and Sections 6.1~6.3 of Algorithm Design (also see slide set )on dynamic programming .

 

 

Week 10: More on Dynamic Programming. Progress report due: Thursday, Nov. 5

  • Reading #10:  Sections 6.4~6.5 of Algorithm Design (also see slide set ) on dynamic programming.

 

  • Homework #4: A dynamic-programming approach to the mixture sequence problem. Due: Thursday, Nov. 12

 

Week 11: Applications of Algorithms in Bioinformatics. Progress report due: Thursday, Nov. 12

  • Reading #11:  Sections 6.6~6.7 of Algorithm Design (also see slide set) on sequence alignment.

 

Take-home Test 3 on Dynamic Programming (Due: Dec. 3)

 

 

Homework #5: (Due: Dec. 3)

  • Implement the dynamic programming algorithm described in Section 6.5 of the textbook for finding the most likely RNA secondary structures. Your program should be able to read in a RNA sequence given by the user and determine the base pairs form within the RNA to create the most likely secondary structure. For example, you can play with demo program below to  see how it should work.
  • Demo Program: Download this zip file for a sample executable and sample RNAs. Run the enclosed executable to analyze the sample RNAs inside and see the 2D layout of  the energy-minimization secondary structures in the resulting text files.

 

 

Week 12: More on the Applications of Algorithms in Bioinformatics. Progress report due: Thursday, Nov. 19

  • Reading #12:  Browse through chapter 6 in An Introduction to Bioinformatics Algorithms (see the online e-book version from the Biola library here) regarding the applications of dynamic programming in bioinformatics. You should identify at least two interesting problems in bioinformatics and their algorithms. Report what you find and in your progress report.

 

Week 13: More on the Applications of Algorithms in Bioinformatics. Progress report due: Thursday, Dec. 3

  • Reading #13:  (i) Browse through chapter 7 in An Introduction to Bioinformatics Algorithms (see the online e-book version from the Biola library here) regarding the applications of divide-and-conquer in bioinformatics. You should identify at least two interesting problems in bioinformatics and their algorithms. Report what you find and in your progress report. (ii) Read the two papers 1 and 2 on vehicle refueling problems.  

 

About weekly progress report:

  • By Thursday each week, you should spend around 5~10 minutes to write a brief progress report (see this template) regarding the latest progress made in this class, and email the report to Dr. Lin.

 

 

To the Top of the Page