Course Description - CSCI 570, Spring 2004, TuTh Section

Course Description - CSCI 570, Spring 2004, TuTh Section

Textbook

Required textbook:

T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein. Introduction to Algorithms. MIT Press, 2nd Edition, 2001.

Prerequisite

The prerequisite for this class is that you are familar with Chapters 1, 2, 3, 4, 10, 22 and appendix VIII of the textbook.

Course Outline

The topics covered and the corresponding chapters and sections in the textbook are as follows:

Introduction
- Divide and conquer: 2.3.
- Heapsort: 6.1 - 6.5.
Design and analysis techniques
- Dynamic programming: Ch. 15.
- Greedy algorithms: 16.1, 16,2, 16.3.
- Amortized analysis: 17.1 - 17.3.
Data structures
- Binomial heaps: 19.1 - 19.2.
- Fibonacci heaps: 20.1 - 20.4.
Graph algorithms:
- Minimum spanning trees: 23.1 - 23.2.
- Shortest Paths: 24.1 - 24.3, 25.1 - 25.3.
NP-Completeness: 34.1 - 34.5.
Approximation Algorithms: 35.1 - 35.2
Number Theoretic Algorithms: 31.1 - 31.7

Workload

Homework: There will be 8 assignments. They will be posted on the Homeworks page.

Exams: There will be three in class quizzes on homework problems. Your homework grade will be based on the scores of the three quizzes. There will be an in-class midterm exam and a final exam. The exams are closed book and closed notes.

Any schedule conflicts involving exam dates must be reported to the instructor within one week of the announcement of the exam date.

Academic Integrity Policy

Please make sure you read the Academic Integrity Policy of this course.

Grading (Tentative)

Homeworks: 30%
Exam 1: 30%
Exam 2: 40%

The weights are approximate and may change by up to 5%.