CAS CS 530 - Fall 2018

Graduate Design and Analysis of Algorithms

Syllabus

Steven Homer (homer@bu.edu)

Office: MCS 281

Phone: 353-8927

Office hours: Tuesday 11-12 and and Wednesday, 12-1

Teaching Fellow: Nithin Varma (nvarma@bu.edu)

Office: Room MCS 148

Office hours are: Monday 2:30-3:30 and Thursday 12-1 in room MCS 148

Text Algorithms by Cormen, Rivest, Leiserson and Stein, Edition 3

Sections The discussion sections will start on September 7/

The 4 section are

Section A2: 9:05am - 9:55am in MCS B23, Section A3: 10:10am - 11:00am in MCS B19

Section A4: 11:15am - 12:05pm in CAS 225, Section A5: 12:20pm - 1:10pm in CAS 324

Sections are required and important as often new information, hints on homework and answers to problems will be discussed there.

Please select one of the lab section to attend each week.

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 semester include

-matrix decomposition methods

-linear programming and its applications,

-review of elementary complexity theory including NP-complete and NP-hard problems

-discrete optimization methods (including submodular functions and NP-problems)

-approximation algorithms, and

-probabilistic algorithms, specifically those related to finding cuts in graphs, polynomial identity testing and matching,

-algorithms for internet applications; k-means, clustering, cuts in graphs

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 graded homework assignments, 4 quizzes, and a final exam. The grade will be determined by: HW 25%, 3 quizzes 40% (quiz 1 - 12%, quiz 2 - 14%, quiz 3 - 14%), and a final 35%. No incompletes will be given.

Late policy: A penalty of 10% per day will be assessed for late homeworks, furthermore 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.

Collaboration Policy

You are strongly encouraged to collaborate with one another in studying the lecture materials and preparing for homework, quizzes and exams.

You may discuss ideas and approaches to the assignments with others but such discussions should be kept at a high level, and should not involve actual details of the answers or code. You must complete and write the actual solutions on your own.

Academic Misconduct;

We will assume that you understand BU's Academic Conduct Code: see http://www.bu.edu/academics/policies/academic-conduct-code