Steven Homer (homer@cs)
Office: MCS 281
Phone: 353-8927
Office hours:Tuesday 11-12 and and Wednesday, 2-3
Teaching Fellow: Hannah Flynn (hmflynn@cs)
Hannah will lead the lab sections (which are not required). However, each of you should choose one of these three hours below to attend the section each week. Generally during the sections homework will be discussed and some details of the class material will be clarified.
The lab section times are:
Wednesdays: 3:30 - 4:30pm in PSY B51
Thursdays: 3:30 - 4:30pm in PSY B51
Fridays: 3:30 - 4:30pm in PSY B55
Her office hours are: Wednesday 4:30-5 and Friday 2-3, and by appointment.
The office hours will be held in the undergrad computer lab which is in room 302 of the EMA building at 730 Commonwealth Avenue (above the Radio shack).
Text Algorithms by Cormen, Rivest, Leiserson and Stein Edition 3 (or edition 2 if you already own it)
Prerequisites and Related Courses
CS530 is the core graduate algorithms course, graduate-level successor of CS330. Its only prerequisite is CS330 (or consent of the instructor).
Also required is a working knowledge the basic mathematical skills needed to design, write and analyze algorithms and their efficiency.
List of topics
Some of the topics planned for CS 530 this year include
-network flow (including multi-commodity flow and related graph algorithms),
-matrix decomposition methods
-linear programming and its applications,
-probabilistic algorithms, specifically those related to finding min-cuts in graphs, polynomial identity testing and matching,
-approximation algorithms for hard problems, and
-polynomial and matrix algebra and their applications.
Background
In CS 530 we will very briefly review some of the central topics already studied in CS330 Mainly though, class time will be spent covering a selection of advanced topics, and more modern tools for designing and analyzing efficient algorithms.
CS 530 is a "continuation " of CS 330 and the background material covered in CS 330 is assumed in this class. That which you do not already know must be studied on your own or by taking CS330 if needed. The background material includes,
-the basic algorithms concerning sorting and searching, graphs, algebraic operations including integer matrix and polynomial multiplication, NP completeness, and elementary approximation and heuristic algorithms for combinatorial problems.
-basic algorithm techniques such as exhaustive search algorithms, greedy algorithms, recursion, and dynamic programming
-the background necessary to analyze the efficiency of these algorithms and basic discrete mathematics, probability and linear algebra.
If this material is unfamiliar to you, you will have to spend some time doing supplementary reading or sitting in on the prerequisite classes.
Grading
There will be about five or six graded homework assignments, a midterm, one quiz and a final exam. The grade will be determined by: homework 30%, midterm 20%, quiz 10% and final 40%. No incompletes will be given.
Late policy: A penalty of 10/% per day will be taken off for late homeworks, however homework will only be accepted up until the answers are posted on-line. You may request an extension of the homework due date once (or maybe twice) during the term.