Introduction to Algorithms

This web page details teaching modules related to basic algorithms that are under development at the ANU. Modules are written in LaTeX and published in three formats: MathML, Post Script (PS), and the Portable Document Format (PDF). You will need to configure your browser correctly to view the MathML versions of the documents (see"Note on MathML").

Comments/Questions can be sent to Weifa.Liang AT anu.edu.au and Alistair.Rendell AT anu.edu.au.

Note on MathML

To view the MathML documents you will need a MathML compliant browser:

Amaya: Amaya is a web browser and editor written by W3C. http://www.w3.org/Amaya/
Netscape, Mozilla, and Mozilla Firefox: These browsers all support MathML natively, however they need certain fonts installed in order to render it correctly. See http://www.mozilla.org/projects/mathml/fonts/ for instructions on downloading/installing these fonts. (Note for Mac OS X users: Firefox 1.0.5 on Mac OS X, without the font problem fixed, does not display "-" (minus) signs. Use Mozilla 1.3a instead)
Internet Explorer: Design Science has produced a plugin for Internet Explorer version 6.0 called MathPlayer. http://www.dessci.com/en/products/mathplayer/download.htm

Module Listing

Module 1 - Introduction to Algorithms

Introduction to Algorithms (XHTML) (PS) (PDF)
Growth of Functions (XHTML) (PS) (PDF)
Comparison of Functions (XHTML) (PS) (PDF)
Recurrences (XHTML) (PS) (PDF)
Tutorial (XHTML) (PS) (PDF)

Module 2 - Data Structures 1

Hash Tables (XHTML) (PS) (PDF)
Binary Heaps (XHTML) (PS) (PDF)
- Python Example: binary_heap.py
Binomial Heaps
- Python Example: binomial_heap.py
Fibonacci Heaps
- Python Example: fibonacci_heap.py requires: util.py
Tutorial (XHTML) (PS) (PDF)

Module 3 - Data Structures 2

Binary Search Trees (XHTML) (PS) (PDF)
- Python Example: binary_search_tree.py
Red Black Trees (XHTML) (PS) (PDF)
- Python Example: red_black_tree.py requires: binary_search_tree.py
B-Trees (XHTML) (PS) (PDF)
- Python Example: b_tree.py requires: util.py
Disjoint Sets (XHTML) (PS) (PDF)
- Python Example: disjoint_set.py
- Python Example: disjoint_set_alternative.py
Tutorial (XHTML) (PS) (PDF)

Module 4 - Graphs

Basic Graph Algorithms (XHTML) (PS) (PDF)
- Python Example: graph.py
Minimum Spanning Trees (XHTML) (PS) (PDF)
- Python Example: minimum_spanning_tree.py requires: disjoint_set_alternative.py, binary_heap.py, fibonacci_heap.py, graph.py, util.py
Single Source Shortest Paths (XHTML) (PS) (PDF)
- Python Example: single_source_shortest_path.py requires: graph.py, fibonacci_heap.py, util.py
All Pairs Shortest Paths (XHTML) (PS) (PDF)
- Python Example: all_pairs_shortest_paths.py requires: matrix.py
Tutorial (XHTML) (PS) (PDF)

Module 5 - Design of Algorithms

Divide-and-Conquer
Greedy Algorithms
- Python Example: greedy_algorithms.py requires: binary_heap.py
Dynamic Programming
Tutorial

Example Python Code

Some of the Python code examples import shared Python files. Thus, it is better to download all the code into a local directory before running. For your convenience, the code has been packaged up into archives of different formats. Both contain the same code and choice of which to download is entirely up to you.

When executed individually, each Python source file will run its test script. For example "python binary_heap.py" will run the binary heap test. Alternatively, running "python test.py" will run all the test scripts automatically.

More information about the Python programming language can be found at http://www.python.org.