Fitting last class, draws on much of what we've learned:
- Analysis: Critical for understanding why the problem is so
difficult in the first place!
- Sorting: Used in Kruskal's algorithm.
- Statistics: Useful for comparing algorithms empirically.
- Heap: Used in Dijkstra's algorithm.
- Binary Search Trees: splay trees provide efficient implementation
of local-search heuristics.
- Hashing: can map node labels to identifiers.
- Matching: Important approximation method.
- Matrix Algorithms: linear programming (which builds on solving
systems of linear equations) used extensively
in generating lower bounds.
- Graphs: Special type of graph problem, tree walk is a DFS.
- Minimum Spanning Tree: Simple approximation method.
- Shortest Paths: Search the graph of partial tours.
- DP: New approximation schemes for 2-d TSP.
- Complexity: NP-complete.
Next: The Course
Up: CONCLUSION
Previous: CONCLUSION