CS329E Fall 2006 Dr. David Kincaid
Welcome CS329E Students
Elements of Algorithms in BioInformatics
Fall 2006 Dr. David Kincaid
Dr. David R. Kincaid, PAI 5.48, Tel: 4719783, Fax: 4718885
Office Hours: immediately after class in RLM 13.158
or via email
kincaid@cs.utexas.edu
or by appointment.
TA: Nathan Paczan
Office Hours: MW 23pm, PAI 5.38 (Elements Lab) or
via email
npaczan@cs.utexas.edu
Class Syllabus
Lectures:

(Aug 31)
Overview of class.

(Sep 05)
Rock Game

(Sep 07)
More on Rock Game ,
BigO Notation

(Sep 12)
Fibonacci Numbers

(Sep 14)
Notes and Problems,
Tower of Hanoi

(Sep 19)
Sorting Problem,
Change Problem

(Sep 21)
Algorithm Design Techniques,

(Sep 26)
Dynamic Programming Algorithms,

(Sep 28)
Manhattan Tourist Problem,

(Oct 03)
Recurrences,
Review,

(Oct 10)
Edit Distance & Alignment,

(Oct 12)
Longest Common Subsequence,

(Oct 17)
Graph Theory,

(Oct 19)
Graph Theory (cont.)

(Oct 24)
Partial Digest Problem (PDP)

(Oct 26)
More PDP

(Oct 31)
Sorting by Reversals;
Sorting by Divide and Conquer PDP

(Nov 3)
Combinatorial Patterm Matching

(Nov 7)
Motif Finding/Median Finding;
Reveiw

(Nov 11)
More Reveiw
Assignments:

HW1
Due: 09/12 (Tue); Can use any word processing system: Word, LaTeX, etc.

CP1 (Due: 9/21)
Fibonacci Algorithms

HW2 (Due: 9/28)
Chapter 2, Problems 2.2, 2.3, 2.11, 2.15, 2.16 < Assume n is
less than or equal to 10 and the size of each of the two new piles
must be equal or approximately equal and must add up to the size of the
original big pile. Extra Credit: 2.16 as given in textbook.

CP2 (Due: 10/17)
Cp2.ps,
Cp2.pdf

HW3 (Due: 10/26)
Chapter 8, Problems 8.1, 8.2, 8.3, 8.6, 8.9

CP3 (Due: 11/5)
Pattern Matching and Searching:
CP3.ps,
CP3.pdf

HW4 (Due: 11/9)
4.2,4.4,4.5,6.1.7.1

Extra Credit (Due: 12/12):
extra.ps,
extra.pdf
Examinations:

Exam I (10/5)

Exam II (11/14)

Final Exam (12/14) WEL 3.422
General questions on material covered in textbook and lectures
wrt concepts, algorithms, and problems.
Objective Format: Fillin the blank, True/False, Short answers.
Miscellaneous Information:
Special Office Hours, Monday (12/11) and Tuesday (12/12), 23pm, Dr. Kincaid, PAI 5.48
Review Session: Nathan Paczan, Elements Lab, Monday (12/11), 7pm.

No Class Tuesday 11/21

Student Presentations:

Tuesday (11/28)

Tara Long  Randomized Algorithms: Gibbs Sampling, Random Projects

Thursday (11/30)

Layla Young  Protein ID (Sec. 8.108.15)

John Leavitt  Hidden Markoff Methods

Tuesday (12/5)

Kristin Schroter  Genes and DNA (3.33.6, 3.8)

Erika Kase  Combinatorial Pattern Matching

Ajay Mody  Combinatorial Problems

Santosh Dawson  Randomized Algorithms

Thursday (12/7)

Beatrie Santillan  Gibbs Sampling

David Rushworth  Neutral Networks

Marcus Reid  Trees and clustering (Chp 10)

Todd Gillespie 

Louis Guzick 
08 Dec 06