Transcript Slide 1

Lecture 12:
Algorithm Review
General Problem Solving Methods
Divide & Conquer
Greedy Method
Dynamic Programming
Graph & Tree Traversal
Backtracking
Branch & Bound
Constraint Relaxation
Reduction Methods
Searching & Sorting
Binary Search
Merge Sort
Quicksort
Topological sort
Graph & Tree Traversal
Prim's Algorithm Minimum Spanning Tree
Dijkstra's Single-Source Shortest-Path
Depth-First Search
Hamiltonian Circuits
Maximal Matching
Graph Coloring algorithm
B&B TSP
B&B TSP with Constraint Relaxation
Max-Flow Min-Cut (Ford-Fulkerson)
Dijkstra's Single-Source Shortest-Path (SSSP)
Floyd's All-Pairs Shortest-Path (APSP)
Natural Clustering (Dendrograms)
Greedy Methods
Greedy Matching
Greedy Coin Changing
Prim's Algorithm Minimum Spanning Tree
Track Correlation
Greedy Euclidean TSP
Floyd's All-Pairs Shortest-Path (APSP)
Simplex Method
Dynamic Programming
Dijkstra's Single-Source Shortest-Path
Making Change (non-Greedy)
Davis-Putnam 3-SAT Algorithm
0/1 Knapsack Problem
Constraint Relaxation Methods
Augmenting Path Algorithm
Maximal Matching
Munkres Assignment - Hungarian algorithm
Track Correlation
B&B TSP with Constraint Relaxation
Max-Flow Min-Cut (Ford-Fulkerson)
Simplex Method
Natural Clustering (Dendrograms)
General Combinatorial Algorithms
Depth-First Search
Hamiltonian Circuits
Next Permutation
Graph Coloring algorithm
Optimal Traveling Salesperson Problem
Algorithms
Cross & Insert Heuristics for Routing
Davis-Putnam 3-SAT Algorithm
Solution-Set Enumeration (3-SAT)
Sum-of-Subsets
N-Queens Problem Methods
Backtracking Algorithms
Dictionary of Algorithms and Data Structures
This web site is hosted in part by the Software and Systems Division, Information
Technology Laboratory.
This is a dictionary of algorithms, algorithmic techniques, data structures, archetypal
problems, and related definitions. Algorithms include common functions, such as
Ackermann's function. Problems include traveling salesman and Byzantine generals.
Some entries have links to implementations and more information. Index pages list
entries by area and by type. The two-level index has a total download 1/20 as big as
this page.
http://www.itl.nist.gov/div897/sqg/dads/
Graph Traversals
A
D
F
C
B
H
E
G
depth-first from node ___ : ___ ___ ___ ___ ___ ___ ___ ___
breadth-first from node ___ : ___ ___ ___ ___ ___ ___ ___ ___
hamiltonian path ___ ___ ___ ___ ___ ___ ___ ___
Greedy Tour
greedy tour starting from node ___ : ___ ___ ___ ___ ___ ___ ___ ___
lower bound heuristic computing minimum cost to leave each city _______
lower bound heuristic computing minimum cost to enter each city _______
Graph Representations
1
B
A
2
2
5
adjacency matrix
___ ___ ___ ___ ___ ___ ___
___ ___ ___ ___ ___ ___ ___
___ ___ ___ ___ ___ ___ ___
___ ___ ___ ___ ___ ___ ___
___ ___ ___ ___ ___ ___ ___
___ ___ ___ ___ ___ ___ ___
___ ___ ___ ___ ___ ___ ___
edge list
C
2
D
E
1
1
4
3
1
2
F
G
2
___
___
___
___
___
___
___
___
___
___
___
___
___
___
___
___
___
___
___
___
___
___
___
___
___
___
___
___
___
___
___
___
___
___
___
___
Minimal Spanning Tree
1
A
edge list of MST
___
___
___
___
___
___
___
___
___
___
___
___
___
___
___
___
___
___
B
2
2
5
C
2
D
E
1
1
4
3
1
2
F
G
2
Single-Source Shortest Path
1
B
A
2
2
5
from node ____
{__}
{__ __}
{__ __ __}
{__ __ __ __}
{__ __ __ __ __}
{__ __ __ __ __ __}
C
2
D
E
1
1
4
3
1
2
F
___ ___ ___ ___ ___ ___
___ ___ ___ ___ ___ ___
___ ___ ___ ___ ___ ___
___ ___ ___ ___ ___ ___
___ ___ ___ ___ ___ ___
___ ___ ___ ___ ___ ___
G
2