You can drop the final off in my office (5153 Upson). You can leave it under my door, if I am not here.
FAQ for the final:
- The final above has an improved text for the hint for problem 3. The suggestion is to have each edge of the outer cycle in exactly one node of the decomposition tree.
- Problem 1c is a special case of Problem 1a. Each process is needs two SPECIFIC resources, e.g., a specific room, like HO 305, and a specific equipment.
Office Hours During the Final week
Time: MWF 2:30-3:20 pm.
Place: 306 Hollister Hall
Handouts and Announcements
CS 681 is an introductory graduate-level course on algorithms. Although we will be covering a number of current research topics in the design and analysis of algorithms, the primary focus will be on principles in algorithm design that are conceptually clean and broadly applicable. Our goal is to make the course both accessible and useful for graduate students in any area that makes use of algorithms.
Some of the broad areas we will be considering are: basic graph
algorithms and data structures from a current perspective; the use of
randomization; intractable problems and the design of approximation algorithms;
and fundamental techniques from combinatorial optimization. We will be looking
at algorithms as they appear in a variety of settings; some of these may include
communication networks, on-line algorithm, computational geometry, computational
biology, and the design of error-correcting codes.
Pre-requisites
There is no specific course
pre-requisite, though knowledge of some material at the level of an
undergraduate algorithms course, such as CS 482 will be assumed at various
times. In particular: elementary data structures and elementary algorithms, such
as basic sorting and searching, basic graph terminology, and basic graph
algorithms, such as graph search, asymptotic order of growth notation, and basic
recurrence relations for analyzing algorithms. It will also be helpful to have
seen basic definitions of probability (e.g. random variables and their
expectations), as well as some very basic linear algebra.
The course will follow the same basic outline, with a similar set of topics as CS482. However, the actual overlap with 482 will be rather minimal, as all topics will be covered at a more advanced level.
Late homeworks will not receive credit. (If a genuine emergency situation prevents you from handing in an assignment on time, come talk to me and we can work something out.)
You are expected to support the answers to the homework with proofs. Much of the homework will consist of questions asking you to design algorithms for various problems. A complete answer consists of a clear description of an algorithm (an English description is fine), followed by an analysis of its running time and a proof that it works correctly; you do not need to implement the algorithm. You should try to make your algorithms as efficient as possible.
You may discuss the homework problems with other members of the
class, but you must write up the assignment separately and list the names of the
people with whom you discussed the assignment.
Exams
There will be take-home exams for mid-term and
final. Unlike the homework assignments, these must be done completely on your own.
Grading
The homework will count for 50% of the
grade, the mid-term for 20%, and the final for 30%.
Books
We will use two books throughout the course. The main textbook will be
In the first few weeks we will follow the book:
Some other useful books are