CPS130: Introduction to the Design and Analysis of Algorithms
| Office Hours
| Grades Statistics
| Grade Lookup
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 divide-and-conquer, dynamic
programming, and greedy algorithms.
- Tammy Bailey
Office: D343 LSRC Bldg
Office hours: Monday & Tuesday 2:00-3:30
Problem sessions: Wednesday 5:00-6:00, D106 LSRC
- Mathematical foundation (growth of functions, summations, recurrences)
- Amortized Analysis
- Paradigms (divide-and-conquer, greedy, dynamic programming)
- Graph Algorithms
Cormen, Leiserson, Rivest and Stein,
Introduction to Algorithms, 2nd Edition, McGraw Hill, New York, 1990. (bugs).
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,
- C. H. Papadimitriou,
Computational Complexity, Addison Wesley, 1994.
- Homework assignments (approx. 30%).
- Two in-class exams (20% each) and a final exam (30%).
- Class participation.
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!
Last modified: Mon May 20 11:14:14 2002 by laura.