CSE 552 Fall 2010
Randomized and Approximation Algorithms Syllabus
This document is available at http://www.public.asu.edu/~ccolbou/src/552syllabusf10.html
CSE 552 is an advanced course in the design and analysis of algorithms.
It treats two main topics:
 Randomization: the power of randomization, the design of randomized algorithms, the analysis of randomized algorithms using `basic' probability.
 Approximation: the effective solution of NPhard optimization problems to approximate the correct answer within a specified accuracy, the design and analysis of such algorithms.
Topics to be Covered:
(The specific syllabus will be made more explicit as the semester
progresses.)
Topics for randomized algorithms include:
 Introduction to probability and randomized algorithms. Examples: quicksort, randomized mincut algorithm.
 Basic inequalities (Markov, Chebyshev) and random variables.
 Maxcut and derandomization. Permutation routing in a hypercube.
Basic Chernoff bound.
 Markov chains and random walks (2SAT example, random walk on a path example). Cover times. Universal traversal sequences.
 Generation of combinatorial arrays. Random constructions and derandomized algorithms.
Possible topics for approximation algorithms include:
 Set cover
 Steiner tree and TSP
 Knapsack, bin packing
 Euclidean TSP
 LP duality introduction; set cover randomized rounding
 Set cover via primaldual
 kmedian on a cycle
 MaxSat
 Multiway cut
 Steiner forest
 Group Steiner trees
The grading for the class is as follows:

Homework Assignments  three at 10% each  30%
Always due at the start of class.
Written documentation detailing medical treatment or a family emergency is required in order to make alternate arrangements for homework submission.
Homework 1 (Handed Out 13 September, Due 28 September).
Sample solutions are here.
Grades out of 100 are: 46 47 49 57 58 63 71 72 74 80 83 85 86 93.
Homework 2 (Handed Out 05 October, Due 21 October).
Sample solutions are here.
Grades out of 100 are: 41 47 52 55 59 60 68 69 72 77 90 99.
Homework 3 (Handed Out 09 November, Due 23 November).
Grades out of 100 are: 66 68 68 70 74 80 84 86 86 88 98 100.
 Midterm Exam (TakeHome, Individual)  30%  Out 23 October, Due 02 November by start of class
The questions are posted here.
Very sketchy sample solutions are posted here.
Grades out of 100 are: 70 71 77 80 81 83 86 90 94 96 100 100.
 Project  40%  Due 09 December 2010 no later than 9:20 a.m. by email to colbourn@asu.edu 
OR Final Examination, 09 December 2010, 7:309:20 a.m.
Each student must decide which of these to do, and report their decision to the instructor by 05 November 2010.
If no decision is made by then, the student is expected to write the final examination.
General Course Information:
Students may discuss homework
assignments with their classmates; however all work turned in is expected
to be that of the individual. If you have any questions regarding appropriate
collaboration please see the instructor.