ECS 122A, Winter 2012

Algorithm Design and Analysis

Announcements

• Final Exam on March 21, 8-10am, in 226 Wellman
  • Exam is open notes and books
  • Exam is comprehensive
  • Emphasis on last third of material (from Dijkstra on)
  • Advice: study from lecture notes and problem sets
  • Lecture schedule is updated with sections of book and handouts we covered
• Problem Set 7 (3/9/12)(Due: Monday, 3/19/12)

Lecture Schedule - Topics of completed and future lectures

Syllabus, Class Rules, and General Course Information - You are responsible for everything on this

Homeworks and Homework Solutions

• Problem Set 0 PDF (1/9/12) Problem Set 0 solutions
• Problem Set 1 PDF (1/11/12)(Due : 1/18/12)
• NEW Problem Set 2 PDF (1/18/12)(Due : 1/27/12)
• Problem Set 3 PDF (1/27/12)(Due : 2/1/12)
• Problem Set 4 PDF (2/7/12)(Due : 2/13/12)
• Problem Set 5 PDF (2/15/09)(Due : 2/22, 3:15)
• Problem Set 6 PDF (2/28/09)(DUE 3/9, 3:15)
• Problem Set 7 PDF (3/9/09)(DUE 3/19, 3:15)

Programs

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

Supplemental Readings

• Handout 1 - Simplified Master Theorem
• Handout 2 - Subset Sum notes and pseudo-code
• Handout 3 - Hashing Passwords. Link on how to use hashing to store a password table.
• Handout 4 - Lempel-Ziv and gzip
  • Handout 4.1 - Gzip Notes: huffman codes and Lempel-Ziv
  • Handout 4.2 - Cook/Martel - Gzip Notes
  • Handout 4.3 - Lempel Ziv variant article
  • Handout 4.4 - gzip information doc
• Handout 6 - Notes for approximate string matching by Chip Martel

Other Information

• Hard Problems and solutions - A listing of NP-hard problems and approximation results
• Ghostscript/Ghostview/GSview - If you need software to preview/print PostScript