The following pages contain some of the Python programs I've written for solving "bread-and-butter" (standard) problems in Computer Science. I originally wrote these programs for 2 classes I took from Stanford On-Line: "Design and Analysis of Algorithms: Parts 1 and 2".
The Python code listings contain optional print statements used in testing the code. These programs are designed for instructive purposes, and could be made more efficient if they were intended for applications in production. As Tony Hoare, the "inventor" of the QuickSort algorithm famously stated: "Premature optimization is the root of all evil."
Most of the algorithms listed below are illustrated with graphical animations displaying their action. In The Art of Computer Programming, Donald Knuth emphasised: "An Algorithm must be seen to be believed." I hope these animations provide some entertainment to this often difficult subject of Algorithms.
Table of Contents
Most of the following entries are planned articles. Only the clickable links have been written at this time.
Heaps and Priority Queues
- Heaps and Priority Queues
- Application to Median Maintenance
Undirected Graph Algorithms
Directed Graph Algorithms
- Directed Graph Class
- Cycle Detection
- Topological Sort
- Shortest Path (Dijkstra's Algorithm)
- Strongly Connected Components
- Binary Search Trees
- Red-Black Trees
- Universal Hashing Functions
- Separate Chaining Hash Tables
- Double Hashing Probing Hash Tables
- Case Study: Horner's Method vs. Optimized Hashing