CPS130: Introduction to the Design and Analysis of Algorithms
Syllabus
 Homeworks
 Office Hours
 Grades Statistics
 Grade Lookup
 Newsgroup
 Feedback
 Links
This course is an introductory undergraduate course on the design
and analysis of algorithms building on the concepts from CPS100. It
introduces a number of basic algorithms for for a variety of problems
such as searching, sorting, selection and graph problems. It discusses
analysis techniques, such as recurrences and amortization, as well as
algorithm design paradigms such as divideandconquer, dynamic
programming, and greedy algorithms.
Instructor:
TA:
 Tammy Bailey
Office: D343 LSRC Bldg
Email: tammy@cs.duke.edu
Office hours: Monday & Tuesday 2:003:30
Problem sessions: Wednesday 5:006:00, D106 LSRC
Main Topics:
 Mathematical foundation (growth of functions, summations, recurrences)
 Sorting
 Searching
 Amortized Analysis
 Paradigms (divideandconquer, greedy, dynamic programming)
 Graph Algorithms
 NPCompleteness
Course material:

Cormen, Leiserson, Rivest and Stein,
Introduction to Algorithms, 2nd Edition, McGraw Hill, New York, 1990. (bugs).
 Handouts
Other good reference books include:
 D. Kozen,
The Design and Analysis of Algorithms, Springer Verlag,1991.
 A. Aho, J. Hopcroft, and J. Ullman,
Design and Analysis of Algorithms,Addison Wesley 1974.
 G. Brassard and P. Bratley,
Algorithmic  Theory and Practice, Prentice Hall, 1988.
 R. Tarjan,
Data Structures and Network Algorithms,
SIAM Publications,1983.
 C. H. Papadimitriou,
Computational Complexity, Addison Wesley, 1994.
Grades
 Homework assignments (approx. 30%).
 Two inclass exams (20% each) and a final exam (30%).
 Class participation.
Homeworks
Homework assignments will be made available online as the semester
progresses. No credit is given for homework problem solutions received
late. For special situations contact Laura. Homework rules:
 Write your name on each sheet.
 Write the solutions in the space provided.
 Collaboration is allowed, even encouraged, provided that the
names of the collaborators are listed along with the solutions.
Solutions must be written up individually.
 Homework should be submitted at the beginning
of class on the due date.
 Students are encouraged to type their solutions!
<laura@cs.duke.edu>
Last modified: Mon May 20 11:14:14 2002 by laura.