## CSE 203A - Advanced Algorithms## Winter 2015## PeopleProfessor: Ramamohan Paturi
Room: CSE 4246
Email: paturi@cs.ucsd.edu
## Syllabus, projects, evaluation, and hoursSyllabusProjects Evaluation Hours ## Course PrerequisitesCSE 202 or equivalent## Homework AssignmentsFor 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 HonestyEach 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
## Resources |