California State University, Chico
Department of Computer Science
CSCI 650 Syllabus/Course Requirements
Design and Analysis of Algorithms
CSCI 650 Syllabus/Course Requirements
Design and Analysis of Algorithms
Prerequisite: CSCI 311(Algorithms and Data Structures), MATH 317 (Discrete Math Structures) and classified status or faculty permission
Prerequisite by Topic: Experience, skill, and a love of abstractions, mathematical proofs and computers
Units: 3
Class Dates and Times: TR , 9:30PM-10:45AM (Pacific)
Instructor: Anne Keuneke
Office Hours: see http://www.ecst.csuchico.edu/~amk/foo/hours.html for current information
Office Phone: (530) 898-5998
email: akeuneke@csuchico.edu
WWW Homepage: http://www.ecst.csuchico.edu/~amk/foo/csci356
FAX: (530) 898-5995
Textbook Required:
Course Description:
Course Objectives:
Course outline:
Grade Evaluation Procedures: Any academic dishonesty
will
be grounds for receiving a grade of F. See the campus policy
"Few technical terms have gained such notoriety as the appelation 'NP-complete. ' In the short time since its introduction in the early 1970's, this term has come to symbolize the abyss of inherent intractability that algorithm designers increasingly face as they seek to solve larger and more complex problems. A wide variety of commonly encountered problems from mathemetics, computer science, and operations research are now known to be NP-complete, and the collection of such problems continues to grow almost daily. Indeed, the NP-complete problems are now so pervasive that it is important for anyone concerned with the computational aspects of these fields to be familiar with the meaning and implication of this concept." (Computers and Intractability , Garey and Johnson,W.H. Freeman and Co, 1979)
Computer Algorithms , Horowitz, Sahni, Rajasekaran,
Computer Science Press (W. H. Freeman Press), 1998, ISBN 0-7167-8316-9 (Pseudocode version) or Second Edition (2007) ISBN 978-0-929306-41-4
Suggested Reading: Computers and Intractability: A Guide to the Theory of NP-Completeness , Garey and Johnson,
W. H. Freeman Press, 1979, ISBN 0-7167-1044-5
Algorithms from many areas of computer science will be analyzed. Topics include algorithm design techniques (such as divide-and-conquer, greedy algorithms, dynamic programming, and others), mathematical and empirical analysis of algorithms and NP-completeness.
A student will:
Lower Bound Theory
i. Satisfiability
i. Halting Problem
Homeworks and Exams might be take-home or in-class. It depends on the semester.
Homeworks: The best way
to learn the material is by solving problems. You are encouraged to work with others, for the best way to understand the subtleties of the homework problems is to argue about the answers with someone. Each of you should look at all the problems independently, and not just divide the problems. The only way to learn how to do these problems is by intensely thinking about them.
Tests: Tests must be
done individually (whether in-class or take-home). Unless you
learn how to solve problems through the homeworks, you will have trouble
on the exams and thus for your final grade.