## 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:
1. Randomization: the power of randomization, the design of randomized algorithms, the analysis of randomized algorithms using `basic' probability.
2. Approximation: the effective solution of NP-hard 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.
• Max-cut and derandomization. Permutation routing in a hypercube. Basic Chernoff bound.
• Markov chains and random walks (2-SAT 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 primal-dual
• k-median on a cycle
• Max-Sat
• 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 (Take-Home, 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:30-9: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.