CSCI 356:  Design and Analysis of Algorithms

E-version of most current syllabus available in

Spring 2001 Schedule Information

TRACS Call#	Section	Act	Days	Time	Room	Instructor
11084	CSCI 356-01	DIS	TR	0800-0915	LANG 104	Juliano

Prerequisites

CSCI 311(151), Programming and Algorithms II
MATH 317(120), Discrete Mathematics Structures

Description

Algorithms from many areas of computer science will be analyzed. Topics include algorithms from combinatorics, graph theory, artificial intelligence, and systems programming.

Required Accounts

	Students officially registered for the course will have their own Chico State Connection (CSC Portal) account.
	Students are responsible for regularly checking their WebCT account (automatically generated through the CSC Portal) to access an up-to-date on-line calendar of events, current scores, on-line quizzes, etc.

Required Text

Computer Algorithms: Introduction to Design and Analysis, 3/e S. Baase and A. Van Gelder, 2000. Addison Wesley, Reading, Massachusetts. ISBN 0-201-61244-5

Recommended Supplmentary References:

Introduction to Algorithms T.H. Cormen, C.E. Leiserson, and R.L. Rivest, 1990. MIT Press, Cambridge, Massachusetts. ISBN 0-262-03141-8

The Design and Analysis of Computer Algorithms A.V. Aho, J.E. Hopcroft, and J.D. Ullman, 1974. Addison Wesley, Reading, Massachusetts. ISBN 0-201-00029-6

The Algorithm Design Manual S. Skiena, 1997. Springer-Verlag, New York, New York. ISBN 0-387-94860-0 (See The Stony Brook Algorithm Repository.)

Objectives

1. To develop an awareness of algorithm design techniques such as divide-and-conquer, greedy algorithms, dynamic programming, and others.
2. To become familiar with the most popular and powerful algorithm analysis techniques.
3. To develop a fundamental understanding of difficult problems, classes of difficult problems, and the underlying theoretical implications of such problems.

Grade Evaluation

Theoretical Component  (50%)
	27.5%		Exam 1
	27.5%		Exam 2
	45.0%		Final Exam (as scheduled in the Class Schedule)
Practical Component  (50%)
	50.0%		Written Homework
	40.0%		Programming Assignments/Projects
	10.0%		Participation in class discussions

Students are required to earn a C- or better in both the Theoretical and the Practical components; otherwise, the minimum of the scores of the two components will be used to calculate the student's final grade.

Note: Homework will be regularly assigned in class. Not all homework will be collected for grading. However, it is the student's responsibility to prepare for and participate in class discussions regarding all homework-related material.

Final Grades

Final grades shall be expressed as a percentage of the maximum possible score of all evaluated materials. Letter grades will be given according to the following scheme:

Real Interval	Letter Grade	University Definition
[96.25,100.00]	A	Superior Work
[92.50, 96.25)	A-
[88.75, 92.50)	B+	Very Good Work
[85.00, 88.75)	B
[81.25, 85.00)	B-
[77.50, 81.25)	C+	Adequate Work
[73.75, 77.50)	C
[70.00, 73.75)	C-
[66, 70)	D+	Minimally Acceptable Work
[60, 66)	D
[ 0, 60)	F	Unacceptable Work

Note:  It is Dr. J's policy not to assign a final grade of D or D+ to graduate students. Hence,
graduate students with a class standing less than C- (70%) earn a final grade of F.

General Policies

Dr. J has some general policies that apply to all courses that he teaches. Students are expected to read and understand these policies upon registration of the course. What follows below are course-specific policies.

Attendance and Homework

The instructor reserves the right to call on students at random and to required them to present lecture-related ideas and/or their own homework solutions during the class. If a student is not present during any of these random selections, points will be deducted from that students' overall Homework score.

Tentative Schedule

The following tentative schedule is subject to change without notice:

Week	Chapter	Coverage/Comments
1	1 2	Introduction: Principles and Examples;   Data Abstraction and Basic Data Structures
2	3	Recursion and Induction
3	4	Sorting
4	4 5	Sorting     Selection and Adversary Arguments
5	5	Selection and Adversary Arguments     Exam 1, class time
6	6	Dynamic Sets and Searching
7	7	Graphs and Graph Traversals
8	8	Graph Optimization Problems and Greedy Algorithms
9	9	Transitive Closure, All-Pairs Shortest Paths
10	10	Dynamic Programming     Exam 2, class time
11	10 11	Dynamic Programming     String Matching
12	11	String Matching
13	12	Polynomials and Matrices
14	13	Introduction to NP-Completeness
15	13	NP-Complete Problems
16		Final Exam, as scheduled (see Class Schedule)