ECS 122A - Winter 2009 Algorithm Design and Analysis
New Announcements
Final exam median: 66
Solutions for ps7 are now posted on the myucd web page.
End of Term OH: Normal T,W 10th, 11th. Thursday: ME 1:30-3 (no TA OH)
Xiang: 1-3 T 17th, 2-3 W 18th; George: M,W(16,18) 3-4, T 17th 4-5.
password and login for sample exam is 122a
Handout D1 - - Gzip Notes (more links under "Supplemental Readings").
Sample Midterm pdf (1/31)(Solutions: 5/3)
Mid solutions pdf (2/1)
Handout 1 - Simplified Master Theorem
Course information sheet - You are responsible for everything on this
lectures - Lecture topics
Old Announcements
Discussion Section: F 3:10-4:00 1204 Haring [NOTE ROOM Change]
discussions will begin January 9
The text is Introduction to Algorithms, second edition by Cormen, Leiserson, Rivest, and Stein
Text Notes: Be sure to get 2nd Edition. Also, the book is a good reference so may be worth getting in hardcover (but heavier)
General Information
TA, Instructor Info
- Charles Martel .
Kemper Hall , #3049.
martelATcsDOTucdavis.edu.
Office hours: M: 12:45-2:00 W: 9:45-10:45 .
Teaching Assistants
- Xiang Wang .
-
xiang AT ucdavis DOT edu.
- Office hours (in 55 Kemper): T: 1:00-2:00, Th:- 10-11 .
- George Chen, class assistant .
-
cchchen AT ucdavis DOT edu.
- Office hours (in 55 Kemper): M,Th: 2:00-3:00 .
Syllabus, Readings, and General Information
- Course information sheet - You are responsible for everything on this
- Planned Syllabus for this Course
-->
- lectures - Topics of completed and future lectures
- lectures - W06 lectures
Homeworks and Homework Solutions
-
- NOTE: Links for later problem sets not yet live.
- Problem Set 0 PDF (1/5/09)
- Problem Set 0 solutions text
-
- Problem Set 1 PDF (1/7)(Due : 1/14)
-
- PS1 stats: Ave= 72.5, median 75, standard deviation=14.
-
- Problem Set 2 PDF (1/14/09)(Due : 1/26/09)
- PS2 stats: Ave= 73.5, median 76, standard deviation=18, high: 101/105.
-
- Problem Set 3 PDF (1/26/09)(Due : 2/04/09)
- PS2 stats: Ave= 63.5, median 64, standard deviation=18, high: 93
-
- Problem Set 4 PDF (5/4)
-
-
- Problem Set 5 PDF (2/9/09)(DUE 2/19, 3:15)
- ps5 Stats: Ave 78, median 79, high 105/105.
-
- Problem Set 6 PDF (2/19/09)(DUE 3/3, 3:15)
- Avg 57, Med 57, High 88/95, Low 28, Stdev 14
-
- Problem Set 7 PDF (3/3/09)(DUE 3/10, 3:15)
- Avg: 53 Med: 55 Stdev: 15 High: 75/75
Midterm and Final
Programs
Supplemental Readings
- Handout 1 - Simplified Master Theorem
- Handout 2 - Subset Sum notes and pseudo-code
- a folksier writeup Stable Marriage
-
- Handout B - - Lempel Ziv (not exactly as I will use)
- LZ
writeup
- 2nd writeup a varient: LZW
-
-
Handout C - gzip information doc
- Handout D - - Gzip Notes: huffman codes and Lempel-Ziv
- Handout D1 - Cook/Martel - Gzip Notes
- Handout D - - Notes on FSM and KMP: PDF
- Handout E - Notes on FSM and KMP:postscript
- Suffix Tree notes, from Algorithms on Strings, Trees and Sequences
- By Dan Gusfield
- Handout F - Notes on suffix trees:pdf
- Handout G - Martel - Notes for approximate string matching from Martel's class
- Handout E - Notes on FSM and KMP:pdf
-
Other Information