CAS CS 530 - Fall 2017

Graduate Design and Analysis of Algorithms

Syllabus

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 arithmetic.

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 knpw 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.