UNLV CS 477/677 Spring 2011 Second Examination

Date: Thursday, March 31, 2011, 4:00 PM.

1. Huffman's Algorithm.
2. The Hu-Tucker Algorithm.
3. Kruskal's Algorithm.
4. Union-Find.
5. Shortest Path Algorithms.
   1. Simple dynamic programming.
   2. Bellman Ford Algorithm.
   3. Floyd Warshall Algorithm.
   4. Dijkstra's Algorithm.
   5. A* Algorithm.
6. Dynamic Programming.
   1. Finite Deterministic Games, such as chess, checkers, tic-tac-toe, and chomp.
   2. Counting arrangements, such as sequences, the knapsack problem, and combinatorial problems that are difficult to handle using standard combinatorial techniques.
   3. Optimal substructures and the Principle of Optimality.
7. Hashing
   1. Closed or Open?
   2. Linear Probing.
   3. Other Probing.
   4. Cuckoo Hashing.
   5. Perfect Hashing.
   6. Secondary Hashing.
8. Stack Algorithms. Stack Algorithms.
   1. Run-time stack in an operating system.
   2. Evaluation of expressions.