cs504 Notes

cs504, S99/00 Notes

PDF Format

Note, some of the files in this site are in pdf (Portable Document Format) format. They can be read using the stand-alone application Acrobat Reader or the Acrobat web browser plug-in. Both are available from Adobe. They are free and versions exist for many computer systems.

On the WPI CCC UNIX systems, a downloaded pdf file can be read using the command

acroread [filename]

You can also configure your browser to open and read pdf files directly by setting the Netscape default application for "Application/PDF" to

/usr/local/bin/acroread %s

Useful Information

Recurrence Relations - Additional notes on recurrence relations

Practice Problems - Covers material presented during the first half of the semester.

Useful Formulæ - a six-page pdf file of formulæ useful for analyzing algorithms.

Lecture notes from previous semesters follow. There is some overlap between the sets. Also, the 1998 and 1999 sets contain some spreadheet files which can be read using Excel 8.0 (Excel 97 for Windows or Excel 98 for Macintosh).

Lecture Notes from Spring 1999 Semester

Class 1 - Introduction, Proofs, Algorithms, Resources

Class 2 - Summations, Probability, Random Variables, Combinations and Permutations

Class 3 - Probability, Random Variables, Perturbation Method

Class 4 - Binomial Distribution, more on Summations

Class 5 - Recurrence Relations, Summations

Class 6 - Introduction to Generating Functions

Class 7 - Solution Techniques for Ordinary Generating Functions

Class 9 - Generalization of Generating Functions

Class 10 - Probability Generating Functions

Class 11 - Finite State Machines, Enumerations

Class 12 - Inclusion/Exclusion

Class 13 - Non-Static Systems

Class 14 - Trees

Lecture Notes from Spring 1998 Semester

Note, Excel 8.0 (Office 97) spreadsheet demonstrations of some of the results in the lecture notes are available as indicated.

LN1 - Sums

LN2 - Recurrences

LN3 - Integer Functions - spreadsheet

LN4 - Binomial Distributions

LN5 - Generating Functions

LN6 - Probability

Lecture Notes from Spring 1997 Semester

Some of this material has been incorporated into the Spring 1998 lecture notes.

LN1 - Asymptotic Estimation

LN2 - Elementary Probability

LN3 - Summation

LN4 - Binomial Distribution

LN5 - Simple Linear Recurrence

LN6 - Generation Functions

LN7 - Probability

Other Books and Resources

M Hofri, Analysis of Algorithms, (1995, Oxford University Press), ISBN 0-19-509954-0. Note that a list of errata is available.

R Sedgewick and P Flajolet, An Introduction to the Analysis of Algorithms (1996, Addison-Wesley), ISBN 0-201-40009-X. Note that a list of errata is available.

RW Hamming, The Art of Probability (1994, Perseus Books), ISBN 0-201-40686-1. This is a good introduction to probablity theory and experiement.