UNLV CS 477/677 Spring 2012 Fall 2013 Topics

For Preparation for the Final Exam, December 11, 2013, 3:10 - 5:10 PM

This Version May 3, 2012 December 10, 2013

1. Data Structures.
   1. Stack.
   2. Queue.
   3. Heap.
   4. Array.
   5. Linked List.
   6. Binary Search Tree.
   7. Balanced Search Trees.
      1. AVL Tree.
      2. 2-3 Tree.
      3. Treap. (Using Randomization to Obtain Balance.)
      4. Splay Tree
   8. Hash Table.
      1. Closed or Open?
      2. Linear Probing.
      3. Other Probing.
      4. Cuckoo Hashing.
      5. Perfect Hashing.
      6. Secondary Hashing.
   9. Standard storage of arrays of dimensions 1, 2, or 3, in row-major or column-major order.
   10. Sparse Array.
       1. What is a sparse array?
       2. Search structure implementation of a sparse array.
   11. Graphs.
       1. Directed Graphs.
       2. Weighted Graphs.
       3. Matrix Representation.
       4. Neighbor Lists.
       5. Sparse Graphs.
   12. Range Query Structures.
2. Algorithms
   1. Greedy Algorithms.
   2. Divide and Conquer.
   3. Dynamic Programming.
   4. Linear Search.
   5. Binary Search.
   6. Bubblesort.
   7. Selection Sort.
   8. Radix Sort.
   9. Mergesort.
   10. Polyphase Mergesort.
   11. Quicksort.
   12. Heapsort.
   13. Huffman's Algorithm.
   14. Kruskal's Algorithm.
   15. Union/Find.
   16. Depth-First Search.
   17. Breadth-First Search.
   18. Finding the Median of a Set of Numbers.
   19. The Bellman-Ford Algorithm.
   20. The Floyd-Warshall Algorithm.
   21. Dijkstra's Algorithm.
   22. Johnson's Algorithm.
   23. The A* Algorithm.
   24. Graham Scan.
   25. Closest Pair from a Set of Points in the Plane.
   26. Evaluation of an Expression.
   27. The Pseudo-polynomial Algorithm for the Knapsack Problem.
3. Complexity Theory.
   1. Big O, Omega, and Theta notation.
   2. Solving Recurrences, including hard ones, such as:
      F(n) = √ n  F(√ n ) + n
   3. Analyzing Time Complexity of Programs using amortized analysis.
   4. Lower Bound on Sorting using information theory analysis.
   5. 0-1 Problems.
   6. Reduction.
   7. The class P-TIME.
   8. The class NP-TIME.
   9. Guide String.
   10. Certificate = Witness.
   11. NP-Complete Problems.
       1. SAT.
       2. 3-SAT.
       3. The Clique Problem (what I called the Luce-Perry Problem on the test)
       4. The Independent Set Problem.
       5. The Knapsack Problem.
   12. Nick's Class
4. Additional Terms and Concepts.
   1. Preorder, Postorder, and Inorder.
   2. Lazy Deletion.
   3. Connected Graph.
   4. Component.
   5. Complete Graph.
   6. Cyclic Directed Graph.
   7. Topological Order.
   8. Strong Component.
   9. Abstract Data Types and Operators.
   10. The Primality and Factoring Problems, and RSA Coding. (But not the full details.)
   11. Information Theory Analysis
   12. Memoization