CPS 296.3 Algorithms in the Real World
Instructor: Bruce Maggs (bmm@cs.duke.edu)
Class meets MW 2:50-4:05pm LSRC D243
Decoding Reed-Solomon Codes (.pdf)
Andrew Brown’s Python Code for Decoding Reed-Solomon Codes
Cryptography (.pdf) Note bug fix: In section 5.2 (RSA), the statement "But m is relatively prime to n (because n = pq ...)" is not necessarily true. Nevertheless, m^{ed} = m (mod n) even if m is not an element of Z_n^*.
Lectures:
January 20: Introduction (.ppt) (.pdf)
January 20, 25: Entropy, Huffman Codes, Arithmetic Codes (.ppt) (.pdf)
January 27: Run Length, Move to Front, and Residual Coding (.ppt) (.pdf)
January 27, February 1: Lempel-Ziv, Burroughs-Wheeler (.ppt) (.pdf)
February 1, 3: Transform Coding, JPEG, Wavelets, Compressing Graphs (.ppt) (.pdf)
February 8: Error Correcting Codes, Hamming Codes, Linear Codes (.ppt) (.pdf)
February 10: Finite Fields Review (.ppt) (.pdf)
February 10, 15: Reed-Solomon Codes (.ppt) (.pdf)
March 24: Decoding Reed-Solomon Codes (lecture by Andrew Brown) (.pdf)
February 15, 17: Expander Graphs, LDPC codes, Tornado Codes (.ppt) (.pdf)
February 22: Convolution Coding and Viterbi Decoding (.ppt) (.pdf)
February 24, March 1: Introduction to Cryptography, AES (.ppt) (.pdf)
March 1, March 3: Public-Key Cryptosystems, RSA (.ppt) (.pdf)
March 15: Suffix Trees (.ppt) (.pdf)
March 17, 22: Akamai Load Balancing (.ppt) (.pdf)
March 29: Nested Dissection (.pdf)
March 31: Graph Separators (.ppt) (.pdf)
April 5: Iterative Methods, Preconditioners (.ppt) (.pdf)
April 7, 12: Linear Programming: the Simplex Method (.ppt) (.pdf)
April 14, 16: The Ellipsoid Algorithm, Interior Point Methods (.ppt) (.pdf)
April 16, 19: Integer Programming (.ppt) (.pdf)
April 19: Case Study: Airline Crew Scheduling (.ppt) (.pdf)
April 21: How Computers Really Do Arithmetic (.ppt) (.pdf)
Homework Assignments:
Due February 10: Compression (.pdf) util.c
Due February 26: Compression and Error Correcting Codes (.pdf)
Due March 5: Midterm (.pdf)
Due April 9: Cryptography and Suffix Trees (.pdf)
Due April 21: Final (.pdf)