Class Notes

Browser-based capability for viewing and printing files in postscript form may not be available yet in all campus labs, but it is generally available in Unix workstation labs. If you have your own PC you can (and should) install a postscript viewer on it. The Aladdin Ghostview page offers free downloads for various platforms. For a Windows PC, get gsv27550.exe (self-extracting archive file); I haven't tried the downloads for other platforms.

The Adobe Acrobat Reader is installed on most lab worstations for viewing and printing files in PDF format. If you have your own PC you can (and should) install Acrobat Reader on it. You can download it free from Adobe's download page.

Browser-based capability for viewing and printing files in latex form is not generally available yet in campus labs, but will be soon under license agreements Rensselaer has for Maple. If you have your own Windows 95/98/NT PC you can (and should) install the techexplorer plugin. You can download the Introductory Version for free from IBM's techexplorer web page. (The Maple license agreement will provide the Professional version of techexplorer.)

Powerpoint slides can be viewed in the Windows-based labs, or on any platform that has Microsoft Office. (Or, if you don't have Microsoft Office but do have Windows, you can get a free Powerpoint slides viewer.) Clicking on the link to the uncompressed file, and then on ``Open It,'' brings up the file in Microsoft Powerpoint in a separate window. Click on View/Slide Show and use the PgDn or PgUp keys to move forward or backward through the slides. Use Esc to stop the show before the end.

Generic Programming and the Standard Template Library

The Weiss textbook briefly describes some parts of STL in an appendix.
The STL web site is a comprehensive references resource: http://www.sgi.com/Technology/STL/
Supplementary material: draft chapters from the 2nd edition of STL Tutorial and Reference Guide--C++ Programming with the Standard Template Library by David R. Musser and Atul Saini, to be published by Addison-Wesley in 1999.

Chapter 1: postscript or PDF format

zip

tar

Chapter 2: postscript or PDF format

zip

tar

Two example programs using the STL.

Chapter 1 --- Discrete Mathematics Review

Class notes: html and postscript;

techexplorer

Note: The Introductory Edition of techexplorer doen't allow you to print documents. (The Professional Edition does.) Here are printable versions of the files with some of the answers included (others are available below):
Part A: postscript and pdf
Part B: postscript and pdf

Solution to summation problem.
Flaw in the inductive proof that all horses are the same color.
Solution to review problems in postscript, pdf, and latex (techexplorer) form.

Chapter 2 --- Algorithm Analysis

Class notes: html and postscript;

Solution (html and postscript) to the last in-class problems.
Solution to review problems, in html and postscript

Chapter 3 --- Linear Structures

Example code
- simple_vector.txt
- simple_list.txt
Class notes: html and postscript
Code for the polynomial example in class. The solution is available as well. Note that this will build under either g++ or VC++.
Slightly revised and extended version of the polynomial code.
Further extensions of the polynomial class to have a public iterator type defined by a nested class definition. Studying this example may be helpful to understanding how to define the binary_tree iterator type for Project 2.
Solution to review problems, in html and postscript
Step-by-step animations: detecting cycles in a linked list (relates to one of the questions on Quiz 3, Dr. Musser's class). Powerpoint slides: uncompressed or zip compressed.

Chapter 4 --- Trees

Example code:
- simple_bst_dictionary
- simple_skiplist_dictionary
Class notes: html and postscript
Code for the AVL tree example in class. Note that this will build under either g++ or VC++.
Solution to review problems, in html and postscript
Step-by-step animations of binary search trees. Powerpoint slides: uncompressed or zip compressed.
Step-by-step animations of AVL balanced binary search trees. Powerpoint slides: uncompressed or zip compressed.
Supplemental notes on trees and huffman coding by Eric Breimer.
Supplemental notes on huffman coding and AVL trees by Eric Breimer.
Supplemental notes on AVL trees by Eric Breimer.

Chapter 5 --- Hashing

Class notes: html and postscript
Code for the HashTable example in class.
Solution to review problems, in html and postscript
Step-by-step animations of hash tables:

Part 1: Basic concepts. Powerpoint slides: uncompressed or zip compressed.
Part 2: Separate chaining method. Powerpoint slides: uncompressed or zip compressed.
Part 3: Linear and quadratic probing methods. Powerpoint slides: uncompressed or zip compressed.

Chapter 6 --- Priority Queues

Example code
- simple_priority_queue.txt
Class notes: html and postscript
Code for the binary heap example in class.
Solution to review problems, in html and postscript
Binary heaps and leftist heaps. Powerpoint slides: uncompressed or zip compressed.

Chapter 7 --- Sorting

Example code
Class notes: html and postscript
Code for the sort comparison example in class.
Solution to review problems, in html and postscript

Chapter 9 --- Graphs and Graph Algorithms

Class notes: html and postscript
Solution to review problems, in html and postscript
Illustrations of graph concepts and algorithms:

Definitions: Powerpoint slides, uncompressed or zip compressed.
Graph representations: Powerpoint slides, uncompressed or zip compressed.
Topological sort: Powerpoint slides, uncompressed or zip compressed.
Shortest paths: Powerpoint slides, uncompressed or zip compressed.
Minimum spanning tree: Powerpoint slides, uncompressed or zip compressed.

Go Back Home