EECS 144/244
Fall 2015
Contents
Home
Overview
Logistics
Lectures
Homeworks
Reading
Resources
Projects
Fall 2015 edition
Fall 2014 edition
Fall 2013 edition
Spring 2013 edition
Fall 2011 edition
bCourses
Course Development
Wiki
SVN
|
EECS 144/244 Resources
Here are two introductory textbooks on Algorithms for further reference:
This page lists a few basic algorithms and data structures
that prove useful for constructing other algorithms and data structures.
This page is a work in progress.
Tools
Building Block Algorithms
- Breadth-first search and Depth-first search
-
Dijkstra's algorithm: Find the least-weight path from a given node
to all other nodes in a graph (directed or undirected)
with edge weights that all have the same sign.
-
Bellman-Ford algorithm: Find the least-weight path from a given node
to all other nodes in a directed graph with edge weights that can have
different signs. Note that if there is a cycle with negative weights,
then there is no least-weight path. This algorithm can detect such cycles.
-
Floyd-Warshall algorithm: Find the lengths (sum of weights) of the shortest
path between all pairs of nodes in a graph with edge weights that can be positive or negative.
Building Block Data Structures
-
Hash table: A
collection of elements, each associated with a key, supporting efficient
extraction of an element given only the key.
-
Priority queue: A queue of elements sorted by priority so that the highest-priority element can be extracted efficiently.
Some Algorithm Implementations
- Perl Graph package
|