|
|
|
|
|
Suggested reading will be given from time to time during the course.
It is highly recommended that students become familiar with chapters 1-13 in
"Introduction to Algorithms" by Cormen, Leiserson, and Rivest (CLR). Generally,
the recommended reading below will augment the lectures.
- Basics of graph algorithms including depth first search and breadth first
search. CLR, pp. 462-497. March 29 - April 2.
- Minimum spanning tree. CLR, pp. 498-513. March 29 - April 2.
- Disjoint union / find. CLR, pp. 449-464. March 29 - April 2.
- NP-Completeness CLR 916-963. April 4 - April 9.
- Cache Conscious Sorting.
"The Influence of Caches on the Performance of Sorting". A. LaMarca and R.E. Ladner. To appear in the
Journal of Algorithms. A preliminary version of this paper
appeared in Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, January, 1997, 370-379.
April 4 - April 9.
PDF version
Postscript
version
- Information Theory. The text "Introduction to Data Compression" by Khalid
Sayood is a good resource. Also the seminal 1948 paper,
"A Mathematical Theory of Communication" by Claude E. Shannon who
invented the whole field is a good resource. April 26 - April 30.
Shannon's paper
- Huffman Coding. Again look at Sayood's book. The algorithm is also
covered in CLR pp. 337-345. April 26 - April 30.
- Arithmetic Coding. Sayood's book. May 3 - May 7.
- Dictionary Coding. Sayood's book. May 3 - May 7.
- Sequitur. There is an accessible paper by Craig G. Nevill-Manning
and Ian H. Witten titled "Identifying Hierarchical Structure
in Sequences: A Linear Time Algorithm. May 10 - May 14.
Sequitur Paper
- Vector Quantization. Sayood's book. May 17 - May 21.
- Wavelet Compression. Sayood's book. May 17 - May 21.
- SPIHT Wavelet Coding. See the original Said-Pearlman paper on the
SPIHT website. May 17 - May 21.
SPIHT Paper
|
CSE Home
