Final Exam Topics
++++++++++++++++++++++++++++++++++++++++++++


Midterm Topics


Minimum Spanning Trees (Chapter 21)
=================================
Spanning Trees
DFS spanning tree
BFS spanning tree
Major minimum spanning tree algorithm:
1) Kruskal's algorithm
2) Prim's algorithm


Single-Source Shortest Paths (Chapter 22)
=================================
Related Algorithms / Variants
Challenging Attributes
+ Negative-weight Edges
+ Negative-weight Cycles
+ Cycles
Relaxation
Bellman-Ford (Section 24.1)
+ Run-time
Single-source shortest paths in DAGs (directed acyclic graphs) (Section 24.2)
+ Run-time
Dijkstra's (Section 24.3)
+ Run-time


Parallel Algorithms (Chapter 26) 
=================================
Concurrency platform
Speedup
Amdahl's law
Race conditions
Example parallelizations


Linear Programming (Chapter 29)
=================================
Applications
Terms
Standard Form


NP-Completeness (Chapter 34)
=================================
Complexity Classes
How knowing about complexity can help you
Showing a Problem is NP-Complete
Decision Problems vs. Optimization Problems
Reductions


Approximation Algorithms (Chapter 35)
=================================
Approximation Ratio (ρ(n) or rho(n))
Approximation Schemes
Approximate Vertex Cover Solution
Approximate Traveling-salesman Solution
Approximate Set-covering Solution