CSE 203A - Advanced Algorithms

Winter 2015


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.

  1. 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
  2. Solution for problem 1.24 (Shrestha Malik)
  3. Solution for problem 1.25 (Sergio Martin)
  4. Solution for problem 2.8 (Hongzuo Chen)
  5. Homework II, Problems 3.8, 3.18, 3.20, 3.24, 3.25; Discussion date: 2/2/1015
  6. Homework III, problems 4.8, 4.9, 4.10, 4.11, 4.12, 4.20, 4.21, 4.22; Discussion date 2/23/2015
  7. 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)
  8. 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.


  1. Testing matrix multiplication and randomized algorithm for Min Cut (Shreshta Malik)
  2. Randomized algorithm for median (Aaron Arpi)
  3. Algorithms for approximate MAXSAT - Conditional Expectation Method,
  4. Streaming algorithms (Hongzuo Chen)
  5. Chernoff bounds (Vignesh Gowda)
  6. Hashing (Sergio Martin)
  7. Routing on a hypercube (Myron Liu)
  8. Markov Chains (Eugene Kolinko)
  9. Monte-Carlo Method


  1. Guidelines for writing solutions