# CSE203A_WI15

## CSE 203A - Advanced Algorithms

## Winter 2015

### People

**Professor:** Ramamohan Paturi

**Room**: CSE 4246

**Email:** paturi@cs.ucsd.edu

### Syllabus, projects, evaluation, and hours

### Course Prerequisites

CSE 202 or equivalent

### Homework Assignments

For each homework, solve the listed problems. Consult the style guide for writing solutions.

Homework should be turned in at the beginning of the class on the date indicated.

Homework I, Problems 1.22, 1.23, 1.24, 1.25, 2.8, 2.9, 2.13, 2.14, 2.21, 2.32 from Mitzenmacher and Upfal. Discussion date: 1/26/2015

Solution for problem 1.24 (Shrestha Malik)

Solution for problem 1.25 (Sergio Martin)

Solution for problem 2.8 (Hongzuo Chen)

Homework II, Problems 3.8, 3.18, 3.20, 3.24, 3.25; Discussion date: 2/2/1015

Homework III, problems 4.8, 4.9, 4.10, 4.11, 4.12, 4.20, 4.21, 4.22; Discussion date 2/23/2015

Homework IV, problems 5.3, 5.4, 5.5, 5.21, 5.22, 5.23, and 5.24; Discussion date 3/2/2015, solutions to 5.3, 5.4 and 5.5 (Baiyu Li)

Homework V, problems 6.3, 6.15, 6.16, 6.17, and 6.18; Discussion date 3/9/2015

### Academic Honesty

Each student is expected to work by herself/himself to complete homework and exams. However, in the case of homework, students are encouraged to discuss high-level ideas and strategies among themselves in small groups. This in no way relieves the responsibility on the part of each student to work out all the details and to write the solutions by herself/himself.

The authorized materials for this course include the course text book, lecture notes, solutions and other handouts provided by the instructor or TA, and textbooks and lecture notes from the prerequisite UCSD courses. Use of any other materials requires an explicit approval from the instructor. Here is the detailed policy on Integrity of Scholarship Agreement.

### Notes

Testing matrix multiplication and randomized algorithm for Min Cut (Shreshta Malik)

Randomized algorithm for median (Aaron Arpi)

Algorithms for approximate MAXSAT - Conditional Expectation Method,

Streaming algorithms (Hongzuo Chen)

Chernoff bounds (Vignesh Gowda)

Hashing (Sergio Martin)

Routing on a hypercube (Myron Liu)

Markov Chains (Eugene Kolinko)

Monte-Carlo Method