Instructor : Liming Cai
Office: 213 Barrow Hall
Phone : 2-6081
Email : cai@cs.uga.edu
Meeting room: 306 Boyd GSRC (M) and 551 Chemistry (TR)
Meeting hours: 12:20 - 1:10 (M) and 12:30-1:45 (TR)
Office hours: 3:30 - 4:30 (R), or by appointment
Teaching Assistant: Yin Xiong
Homework Assignment
assignment 1
assignment 2
assignment 3
assignment 4
assignment 5
assignment 6
assignment 7
Lecture Notes
Note1
Note2
Note3
Note4
Slides for RNA Secondary Structure Prediction
Readings
Paper 1 in pairwise alignment
Paper 2 in linear space for LCS
Paper 3 in how DP algorithms fold RNAs
Course contents:
This course provides an introduction to the modern study
of computer algorithms. Topics include: asymptotic notations and
basic algorithm analysis techniques, analysis of sorting algorithms,
algorithm design techniques such as divide-and-conquer, greed, and
dynamic programming, fundamental graph algorithms, and a glance at
the theory of NP-completeness. In addition, students will be exposed to
some advanced subjects such as
randomized algorithms, approximation algorithms, and algorithms applicable
to some computational problems
in molecular biology.
Prerequisites:
CSCI 2670 Introduction to Theory of Computing.
CSCI 2720 Data Structures.
Texts:
Introduction to Algorithms, T. H. Cormen, C. E. Leiserson,
R. L. Rivest, and C. Stein, 2nd ed,
McGraw-Hill, 2001.
Grading policy:
Written assignments : 50%
Midterm exam : 20%
Final exam: 30%
All homework answers need to be typed or word-processed.
Late homework answers will not be accepted.
Tentative schedule:
Part I. Introduction: Chapters 1-5 (1.5 weeks)
Part II. Sorting and order statistics: Chapters 6-9 (1.5 weeks)
Part IV. Advanced design and analysis techniques: Chapters 15-17 (4 weeks)
Part VI. Graph algorithms: Chapters 22-26 (4 weeks)
Part VII. Selected topics: Chapters 34, 35 (3 weeks)
Academic Dishonesty:
It is expected that the work you submit is your own. Plagiarism and other
forms of academic dishonesty will be handled within the guidelines of
the Student Handbook. The usual penalty for academic dishonesty is loss of
credit for the assignment in question; however,
stronger measures may be taken when conditions warrant.
Attendance policy:
Regular class attendance is required though class attendance may not be
used in the final determination of grades.
Students are required to attend class during the regularly scheduled
tests and the final exam unless prior arrangements have been made.