Midterm Study Guide
CSE 490 GZ: Introduction to Data Compression
Winter 2002

Midterm Exam, February, 2002

• Midterm Policies
  • An 8 1/2 X 11 inch blue (or green) book is required. The exam will be taken in the book.
  • You may put your own hand written notes in your blue book to aid you during the exam.
  • You may bring the class handouts and assignment solutions.
  • You may bring the Sayood book.
  • You may bring a caclulator, but it should be needed only seldom if at all.
  • The exam begins promptly at 8:30 and ends at 9:20.
• Topics Covered
  • Basic information theory, first-order entropy
  • Huffman coding, adaptive Huffman coding
  • Golomb coding
  • Tunstall coding
  • Arithmetic coding. Scaling, context, adaptivity.
  • LZW
  • LZ77
  • Sequitur
  • Predictive coding, move to front coding
  • Burrows-Wheeler transform
  Study suggestions
  • Work in study groups to help each other out in preparation. Give each other problems to do in an exam setting. After doing the problems alone, critique each others answers.
  • You will want to work out small examples of both encoding and decoding for all the algorithms we have covered.
  • The following problems from the book are worth trying for practice. Pages 74-76, problems 4, 11, 12, 13. Pages 115-126, problems 5, 6, 8. Pages 136-138, problems 3, 4, 5, 6, 7. Page 177, problem 3.
  • Review all the solutions for the weekly assignments to make sure you understand them.
  • Do the practice assignment 4.

  ---

  ladner@cs.washington (Last Update: )