University of Nevada Las Vegas
Howard R. Hughes College of Engineering
School of Computer Science
My Home Page

UNLV CS 477/677 Spring 2012 Topics

For Preparation for the Final Exam

This Version May 3, 2012

  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.)
    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.
    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. The A* Algorithm.
    23. Graham Scan.
    24. Closest Pair from a Set of Points in the Plane.
    25. Evaluation of an Expression.
    26. The Pseudo-polynomial Algorithm for the Knapsack Problem.
  3. Complexity Theory.
    1. Big O, Omega, and Theta notation.
    2. Solving Recurrences.
    3. Analyzing Time Complexity of Programs.
    4. Lower Bound on Sorting.
    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.
  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.)

Back to Course Page