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. Students will be exposed to some advanced subjects such as randomized algorithms and algorithms applied to some problems in molecular biology.

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.

Seven 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-24 (3 weeks)
Part VII. Selected topics: Chapters 29, 31, 34, 35 (4 weeks)

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.