ECS 122B - Winter 2011 Advanced Algorithm Design and Analysis

New Announcements

• ps4 Solutions are under resources on smartsite
• bitonic sort link
• Sam OH Tuesday 8th, 3:15-5, My OH Wed. 9th 10:15-11:15 (none Tuesday)
• ps3 Solutions are under resources on smartsite
• Problem Set 4 Due 3/7/2011 (2/22/11)
• The following is a link to a book on approximation algorithms available for free download. Used in 2/22 lecture
• approximation book download page
• NOTE: ps3 is due Wed. the 23rd (the Day is wrong on the probelem set pdf).
• Problem Set 3 Due 2/23/11 (2/15/11)
• Midterm solutions on the smartsite web site under Resources.
• Ps2 solutions on the smartsite web site under Resources.
• sample problems chapter 6,7 (both)
• Midterm Tuesday, 2/8/11. Open book and notes
• General Information (1/1)

• Old Announcements

  • Note that the secondary text book is now the Kelinberg Tardos one (to match current 122A usage)
  • Old Announcements

  Class Information

  • Instructor: Charles Martel . Kemper Hall , #3049. martel AT cs DOT ucdavis.edu.
  • Office hours: Tuesday 11:45-12:40, F. 12:45-2:00
  • TA: Sam Johnson . Kemper Hall , #55. samjohnson AT ucdavis.edu.
  • Office hours: Thursday 4:30-5:30,
  • General Information (1/1)
  • Planned Syllabus (1/1)
  • Planned/Completed Lecture topics, this quarter
  • Lecture topics from 2007
  • profiling & timing info C - info on time, gprof and gcov
  • Programming Pearls Page .

  Homeworks and Homework Solutions (those with 2011 dates are live)

  • Problem Set 0 (1/2) Due 1/10
  • Problem Set 1 (1/11/11) Due 1/21/11
  • profiling & timing info C - info on time, gprof and gcov, used in Ps1
  • Problem Set 1 solutions on smartsite website
  • Revised Problem Set 2 (1/21/11) Due 2/2/11
  • Code used with Problem Set 2 (1/19) Due 1/31
  • Problem Set 2 Solutions on smartsite website (under resources)
  • Problem Set 3 Due 2/23 (2/15/11)
  • Problem Set 5 postscript (5/23) Due 6/5
  • Problem Set 5 PDF (5/23) Due 6/5
  • code for ps 2

  Web, Pages

  Programming Pearls Page .
  • TSP-approx. link see 3.4.1.
  • Other links

  Midterm and Final

  Syllabus, Readings, and General Information

  Some useful algorithms books

• Network Flows, by Ahuja, Magnanti, Orlin
• Approximation Algorithms for NP-hard problems, by Hochbaum
• Algorithms on Strings, Trees and Sequences, by Gusfield
• shortest A-path notes - shortest A-path notes

Programs

• coins regular C - program for min coins
• coins memeoization C - better program for min coins

Supplemental Readings

• profiling & timing info C - info on time, gprofand gcov

  Other Information

  ---