| |
|
Lecture Slides for CSCI 311 (Algorithms and Data Structures) |
| |
| |
| CONTENT |
SLIDES |
NOTES |
Source
Code |
Safari
Online | Animation
Demo |
| |
| |
| Adelson-Velskii-Landis (1962) AVL
tree |
 |
|
|
 | |
| Source code
from Weiss 2/e (1999): AvlTree.h,
AvlTree.cpp,
Doxygen |
|
|
|
| Bayer (1972) red-black tree |
|
|
|
| |
| Source code
from Weiss 2/e (1999): RedBlackTree.h, RedBlackTree.cpp,
Doxygen |
|
|
|
| Sleator-Tarjan (1985) splay
tree |
|
|
|
| |
| Source code
from Weiss 2/e (1999): SplayTree.h, SplayTree.cpp,
Doxygen |
|
|
|
| |
| Atkinson,
Sack, Santoro, & Strothotte (1986) (binary) heap |
|
|
|
| |
| Source code
from Weiss 2/e (1999): BinaryHeap.h, BinaryHeap.cpp,
Doxygen |
|
|
|
| |
| |
|
|
|
| |
| Online animations for sorting algorithms |
|
|
|
| |
| From sorting-algorithms.com |
|
|
|
| |
| From
coderaptors.com |
|
|
|
| |
| From Jason
Harrison, CS @ University of British Columbia |
|
|
|
| |
| |
|
|
|
| |
| Mergesort |
|
|
|
| |
| Hash-based
search |
|
|
|
| |
| Fagin (1979) extendible hashing |
|
|
|
| |
| Fredkin (1960) Trie |
|
|
|
| |
| |
|
|
|
| |
| Galler & Fischer (1964) disjoint-set data structure (or,
Union-Find algorithms) |
|
|
|
| |
| Source code
from Weiss 2/e (2007): DisjSets.h, DisjSets.cpp,
Doxygen |
|
|
|
| |
| |
|
|
|
| |
| Vuillemin (1978) binomial heap (a.k.a. binomial queue) | | | | | |
| Source code
from Weiss 3/e (2008): BinomialQueue.h, Doxygen | | | | | |
| Fredman & Tarjan (1987) Fibonacci heap | | | | | |
| | | | | | |
| 2-3-4 Trees (a.k.a. B-Trees of order 4) | | | | | |
| Additional notes from Purdue ... | | | | | |
| Bayer & McCreight (1971) B-Trees, and B+ Trees | | | | | |
| Source code written in C `99: bpt.c | | | | | |
| | | | | | |
| Graphs | | | | | |
| Source code
from Heineman (2008): Graph.h, Graph.cxx,
Doxygen | | | | | |
| | | | | | |
| Disjoint Set ADT / Union-Find Algorithms |
|
|
|
| |
| Source code
from Weiss 3/e (2008): DisjSets.h, DisjSets.cpp,
Doxygen |
|
|
|
| |
| | | | | | |
| Bellman (1957) dynamic programming |
|
|
|
| |
| Hu
& Shing
(1984) Matrix
chain-multiplication |
|
|
|
| |
| 0/1
Knapsack Problem |
|
|
|
| |
| | | | | | |
| |
| |