CPS 296.3: Algorithms in Real World

Instructor: Bruce Maggs (bmm@cs.duke.edu)
Weekly Meetings: Wednesday & Friday, 2:50-4:05 PM
Venue: Perkins Library, Link Classroom 3
TA: Harish Chandran (harish@cs.duke.edu)

Course Structure: 6 Assignments
1 Take Home Mid-Term
1 Take Home Final

Compression (.pdf)

1. Introduction (.ppt) (.pdf)
2. Entropy, Huffman Codes, Arithmetic Codes (.ppt) (.pdf)
3. Run Length, Move to Front, and Residual Coding (.ppt) (.pdf)
4. Lempel-Ziv, Burroughs-Wheeler (.ppt) (.pdf)
5. Transform Coding, JPEG, Wavelets, Compressing Graphs (.ppt) (.pdf)
6. Error Correcting Codes, Hamming Codes, Linear Codes (.ppt) (.pdf)
7. Finite Fields Review (.ppt) (.pdf)
8. Reed-Solomon Codes (.ppt) (.pdf)
9. Decoding Reed-Solomon Codes (.pdf)
10. Expander Graphs, LDPC codes, Tornado Codes (.ppt) (.pdf)
11. Introduction to Cryptography, AES (.ppt) (.pdf)
12. Public-Key Cryptosystems, RSA (.ppt) (.pdf)

1. Assignment 1 Due on Feb 9th 2011 util.c Files.zip: Useful files including input_tiny.comp, input_small.comp and input_large.comp
2. Assignment 2 Due on Mar 16th 2011
2. Midterm Due on April 3rd 2011