Computer Science 425 First Term (Fall Session) 1995
Analysis of Algorithms
TEXT: Introduction to Algorithms, by
Cormen, Leiserson, and Rivest.
ROOM AND TIMES:
Elliott
160, TWF 9:30-10:30.
PROF: Frank Ruskey (email:
fruskey@cs.uvic.ca)
OFFICE:
EOW
321, Tue 10:30-11:30 and Thur 9-10:30 (), or by appointment.
My door is usually open and you are free to ask questions if it is.
T.A.: Udi Taylor.
COURSE CONTENT: This course is a continuation of the study
of algorithms and data structures begun in CSC 225.
Topics include: some advanced data structures, algorithm
design techniques, and some algorithm analysis techniques,
including complexity classification.
Along the way we encounter many interesting and useful algorithms.
GRADING:
Midterm 20% (October 20, 50 min.)
Homework 30% (6 or 7 assignments)
Final 50% (3 hts.)
CHAPTERS TO BE COVERED (NUMBERING ACCORDING TO BOOK):
- III.
-
Data Structures (14,15) [red-black trees, augmenting data structures]
- IV.
-
Advanced Design and Analysis Techniques (16,17,18) [dynamic programming,
greedy algorithms, amortized analysis]
- V.
-
Advanced Data Structures (20,21,22) [binomial heaps, Fibonacci heaps, disjoint sets]
- Notes.
-
Backtracking, enumeration, branch-and-bound.
TOPICS WHICH MAY BE COVERED DEPENDING ON INTERESTS OF CLASS:
- VI.
-
Graph Algorithms (27) [maximum flow]
- VII.
-
Selected Topics (28,32,33,36) [Sorting networks, FFT,
Number-theoretic algorithms, NP-completeness, Approximation Algs.]
ADMINISTRATIVE DETAILS:
-
Homework is due at the beginning of class on the due date.
I typically go over the homework in class on the due date.
-
Here is how final letter grades are determined:
At the end of the term I will review all homework and
exams, and then decide a numeric cutoff x, below which the
grade is F, and a cutoff y for A+. Other letter grades are
determined by dividing the interval
[x,y)
into 8 equal sized sub-intervals.
-
Students taking the course for graduate credit (CSC 520) will be required
to read a relevant journal or research paper, prepare a short report on the
paper, and convince me that they understood the paper in a short
oral exam. This component of the course is pass/no-pass and doesn't
otherwise influence your grade.
Assignments:
Old Exams:
Handouts
The Final
The final has been scheduled for December 11 at 9am
in room CLE A118.
Relevant Sites:
