CSE 203A - Advanced Algorithms

Hours

Lecture

9:30 - 10:50 AM, Tuesdays and Thursdays, CSE 2154

Discussion

3:30 - 4:50 PM, Thursdays, CSE 4258

Instructor office

5:00 - 6:00 PM, Thursdays, CSE 4246

Teaching Assistant office

Evaluation

  • Class participation --- 10%
  • Note taking --- 15%
  • Homework --- 30%
  • Multiplicative weight update method and project --- 45%

Homework

  1. Homework 1: Due 9:30 AM 1/24/2017; submit via Gradescope
  2. Homework 2: Due 9:30 AM 2/14/2017; submit via Gradescope
  3. Homework 3: Due 9:30 AM 2/21/2017; submit via Gradescope
  4. Homework 4: Due 9:30 AM 2/28/2017; submit via Gradescope
  5. Notes for multiplicative weight update method for solving semidefinite programs: Due 9:30 AM 3/24/2017; submit via Gradescope
  6. Final project: Due 9:30 AM 3/24/2017; submit via Gradescope

Class notes

  1. Max-cut 0.5 approximation algorithm, Kenneth Hoover
  2. Max-cut semidefinite program by Vahideh Akhlaghi
  3. Definition of semidefinite programming, by Jincheng Huang
  4. Linear programming duality, by Anant Dhayal
  5. Convexity by Derek Tran
  6. Farkas Lemma by Brandon Ustaris
  7. Conic programming by Cody Heiner
  8. Farkas Lemma for cones and duality for conic programs by Lingran Xia
  9. Farkas Lemma for cones and duality for conic programs by Pushen Wang
  10. Duality for conic programs by Vaishakh Ravindrakumar
  11. Regular duality and multiplicative updates method by Bowen Wang
  12. The Multiplicative Weights Update Method and Zero-Sum Games by Yi Hao
  13. Multiplicative weight update method to solve semidefinite programs by Brent Younger

Project ideas

  1. Euclidean weight matrices and applications by Krislock and Wolkowicz
  2. Coloring 3-chromatic graphs, Chapter 9 of Bernd Gärtner and Jiří Matoǔsek
  3. Maximizing a quadratic form on a graph, Chapter 10 of Bernd Gärtner and Jiří Matoǔsek
  4. Constraint satisfaction problems and relaxing them semidefinitely, Chapter 12 of Bernd Gärtner and Jiří Matoǔsek
  5. Rounding via miniatures, Chapter 13 of Bernd Gärtner and Jiří Matoǔsek