Programming the web in San Francisco


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.

These animation programs run in the browser, and so they are written in JavaScript, where the primitive graphical (HTML5 Canvas) operations are performed by the Kinetic.js library. On top of this library, I wrote my own asynchronous framework which defines custom animation objects and property objects similar to CSS3 KeyFrames. These objects are executed by a custom set of parent and child queues of Promises, which I wrote on top of the "When.js" Promise library. Developing these animation programs was far more difficult that the Python code presented, and will be subject of future articles in the JavaScript section of this web site.

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

Undirected Graph Algorithms

Directed Graph Algorithms

  • Directed Graph Class
  • Cycle Detection
  • Topological Sort
  • Shortest Path (Dijkstra's Algorithm)
  • Strongly Connected Components

Search Trees

  • Binary Search Trees
  • Red-Black Trees

Hash Tables

  • Universal Hashing Functions
  • Separate Chaining Hash Tables
  • Double Hashing Probing Hash Tables
  • Case Study: Horner's Method vs. Optimized Hashing