## CSE 552 Fall 2013 Randomized and Approximation Algorithms Syllabus This document is available at http://www.public.asu.edu/~ccolbou/src/552syllabusf13.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.

## 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 09 September, Due 25 September). Some sample solutions.
Grades out of 50 are: 17 18 19 20 21 22 23 24 24 24 26 33 34 37 40 40 40 41 41 41 43 43 44 44 46 47 47 48 49 50
Homework 2 (Handed Out 02 October, Due 23 October). Some sample solutions.
Grades are: 16 20 21 21 21 23 23 23 24 25 27 27 30 33 35 36 36 37 37 39 40 40 41 42 44 46 46 46 50
Homework 3 (Handed Out 04 November, Due 25 November). Some sample solutions. Grades out of 50 are: 13 19 23 24 27 29 30 30 32 33 36 38 41 42 42 42 42 42 43 43 45 45 46 46 48 49 50 50 50
• Midterm Exam (Take-Home, Individual) - 30% - Out 23 October, Due 28 October by start of class
• Here is the midterm. Here are some sketchy solutions.
Grades out of 40 are: 16 18 19 19 20 21 21 24 25 25 28 31 31 32 33 34 35 36 36 36 36 37 37 37 37 37 37 37 37 38
• 40% - Final Examination, 09 December 2013, 12:10-2:00 p.m. OR Project - Due 09 December 2013 no later than 2:00 p.m. by email to colbourn@asu.edu

Students who (1) earn at least an A grade on the midterm examination, and (2) have completed all of homeworks 1 and 2 successfully have the option of doing a project in place of the final examination. Students who elect to do a project must submit a brief (one paragraph) proposal for a topic by 10 November. Students not meeting any of these conditions are 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.