Fall 2016
CS 331 01 Design and Analysis of Algorithms
TuTh 3:00 p.m. - 4:50 p.m.
Room 3/2636
Instructor Dr. G. S. Young
- Office 8/14
- Office Hours
Tu / 4:55 – 6:25 p.m.Th / 4:55 – 6:25 p.m.
Or by appointment
- Phone 909-869-4413
Web Site https://www.cpp.edu/~gsyoung/CS331/16F/cs331.htm
Course In this course we will look at techniques used to describe and analyze
Description the amount of time and space used by algorithms, techniques for
designing efficient algorithms, and examples of efficient algorithms
for various problems. We will also discuss the theory of NP.
Prerequisites: CS 241 Data Structures and Algorithms II.
Textbook R. Neapolitan
Foundations of Algorithms, 5th Edition, Jones and Bartlett, 2015
ISBN-13: 9781284049190
References E. Horowitz, S. Sahni and S. Rajasekaran
Computer Algorithms, Computer Science Press, 1998
S. Baase and A. Gelder
Computer Algorithms, 3rd edition, Addison Wesley, 2000
M. Garey and D. Johnson
Computers and Intractability: A Guide to the Theory of NP-Completeness,
W.H. Freeman and Company, 1979
Grading Homework ...... …...... …………...... …...... 20%
Projects .....……………………………….....……...... …...…...... 15%
Midterm (TBD) ……………...…………...... ….....……...... …..... 30%
Final (Comprehensive, 12/6, 1:40 p.m. - 3:40 p.m.) ...... 35%
A: 90-100%, B: 80-89%, C: 70-79%, D: 60-69%, F: 59% and below
+ and – grades will be assigned within the same grade,
e.g. B+ for upper 80’s, B for mid 80’s, and B- for lower 80’s.
Outline Introduction (Chap 1, Appendix A)
What is an algorithm?
Algorithm analysis - Complexity measures, Asymptotic notation
Average, Worst-case analysis, Lower bounds.
Divide-and-Conquer (Chap 2,7, Appendix B)
The general method.
Binary search, Finding the maximum and minimum,
Mergesort, Quicksort, Integer multiplication, Matrix multiplication.
The Greedy Approach (Chap 4)
The general method.
Minimum spanning trees, Single source shortest paths,
Optimal storage on tapes, Knapsack, Job sequencing with deadlines.
Dynamic Programming (Chap 3)
The general method.
Multistage single-source single-destination shortest path,
All pairs shortest paths, Chained matrix multiplication, 0/1 knapsack,
Optimal binary search trees, The traveling salesperson problem.
An Introduction to the Theory of NP (Chap 9)
"easy" vs. "hard" problems.
P, NP, NP-complete, NP-hard, Reductions.
Important Notes
(1) Regular attendance is recommended. In the event of an absence, it is the student's responsibility to learn of any material missed. Lectures and demonstrations will not be repeated during office hours.
(2) All assignments are due at the beginning of class on the specified day. Late homework will NOT be accepted. Projects submitted late will be subject to a penalty of 10% per calendar day (weekends and academic holidays excluded). I encourage discussion among students, but I expect each student to hand in original work. You are responsible for doing your own work and for insuring that your work is protected from copying. The University’s policy on Academic Integrity, as stated in the catalog, will be enforced.
(3) Rescheduling of exams must be arranged at least one week in advance. Exams missed without prior permission will be given a failing grade.