Algorithmics
Animation Workshop
List of
possible new candidates for animation
Some CSE3101 Topics and more:
- Recursive picture drawing [ Jeff Edmonds can offer code in C and
Turing]
- Long Integer Multiplication [Karatsuba-Offman]
- Dynamic Programming:
- Optimal Static
Binary Search Tree (done)
- Longest Common Subsequence
- Optimal Weighted Event Scheduling
- Optimal (Simple or Convex) Polygon Triangulation
- String Pattern Matching
- o o o
Graph Algorithms (CSE 3101 &
4101/5101/6121):
- Depth First Search (of undirected and directed graphs)
- Breadth First Search (of undirected and directed graphs)
- Biconnected Components (of an undirected graph)
- Strongly Connected Components (of a digraph)
- Minimum Spanning
Trees
(MST): (done)
- Prim
(done)
- Kruskal
(done)
- Cheriton-Tarjan
(done)
- Shortest Paths:
- Dijkstra's Single
Source Shortest Paths (done)
- Floyd-Warshal's All Pairs Shortest Paths
- Graph Matching:
- Traveling Salesman Problem:
- Metric TSP -
double MST (done)
- Metric TSP - Christofides (MST + Matching)
- Euclidean TSP - Sanjiv Arora (Dynamic Programming)
- o o o
Data Structures (CSE 4101/5101/6121
& 6114):
- Leftist Heaps
(done)
- Skew Heaps
(done)
- B-trees
- 2-3-4 trees
- Skip Lists
- kD trees
- Interval Trees
- o o o
Computational Geometry (COSC 6114):
- Linear Programming Algorithms
- Simple Polygon Triangulation [Mirzaian's algorithm by
Pseudo-Triangulations]
- Minimum Weight Triangulation of Point Sets
- Voronoi Diagram
(done)
- Delaunay
Triangulation (done)
- o o o
Last modified on
July 16, 2009,
by Andy
Mirzaian