CSCI 3104
Algorithms
Fall 1995

Class notes

Page 1

Miscellaneous information

1. CSCI 3104 is the future regular number for this course. Currently the number being used is still CSCI 4830.
2. Schedule information.
3. Instructors: Andrzej Ehrenfeucht and Karl Winklmann.
4. Textbook and other references.

Syllabus

There are three groups of topics, or "themes" if you like:

• Classes of algorithms

  The challenge here is to acquire a repertoire of methods, not merely a collection of unrelated examples, and be able to apply these methods to create algorithms for new problems. These methods include

  • divide-and-conquer algorithms,
  • greedy algorithms,
  • randomized algorithms,
  • local optimization,
  • dynamic programming,
  • branch-and-bound.

• Specific problems and algorithms

  There is a number of specific algorithms that you need to know about.

  • Various graph algorithms
  • Network flow algorithms
  • Graph matching
  • Cryptography
  • Computational geometry algorithms
  • Skiplists as an alternative to balancing trees
  • Pattern matching

• Miscellaneous goodies

  These are topics that don't fit easily into the above two categories but which shed light on some profound issues in algorithm design and analysis. We may not have time to cover all of these.

  • Amortized analysis
  • How to be sure your algorithm works
  • When not to bother: intrinsic complexity
  • Computation by other means, e.g. chemistry?
  • Simulated annealing, genetic algorithms

Last edited (or copied to this place) at 7:55 AM, Friday, November 10, 1995.