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

UNLV CS 477/677 Fall 2015 Topics

(Not Necessarily in Chronological Order)

This Version August 25, 2015

  • Complexity Theory.
    1. Big O, Ω, and Θ notation.
    2. Examples of Recursive Algorithms: Mergesort and Binary search.
    3. Solving Recurrences.
      1. Master Theorem.
    4. Analyzing Time Complexity of Programs.
  • Data Structures.
    1. Linked Lists.
    2. Abstract Data Types and Operators.
      1. Integer: Plus, Minus, Less Than, Etc.
      2. Boolean: And, Or, Not.
      3. Priority Queue:
        1. Delete Highest Priority, Insert.
        2. Unfulfilled Obligations.
        3. Stack, Queue, Min-heap, Max-heap, Other.
      4. Search Structure:
        1. Insert, Find, Delete.
        2. Ordered List.
        3. Unordered List.
        4. Binary Search Tree.
        5. B-Tree.
        6. Hash Table.
      5. Array:
        1. Store, Fetch.
    3. Stacks.
      1. Push, Pop.
      2. Stack Algorithms.
        1. Depth First Search.
        2. Evaluation of Expressions.
        3. Run-Time Stack During Execution of a Program.
    4. Queues.
    5. Binary Search Trees.
    6. Heaps.
    7. Balanced Search Structures.
      1. AVL Trees.
      2. 2-3 Trees.
      3. Treaps. (Using Randomization to Obtain Balance.)
    8. Hash Tables.
      1. Closed or Open?
      2. Linear Probing.
      3. Other Probing.
      4. Cuckoo Hashing.
      5. Perfect Hashing.
      6. Secondary Hashing.
    9. Arrays.
      1. Standard storage of arrays of dimensions 1, 2, or 3, in row-major or column-major order.
      2. Sparse Arrays.
    10. Range Query Structures.
  • Graphs.
    1. Directed Graphs.
    2. Weighted Graphs.
    3. Matrix Representation.
    4. Neighbor Lists.
    5. Sparse Graphs.
    6. Connected Graphs.
    7. Components.
    8. Strongly Connected Directed Graphs.
    9. Strong Components.
    10. Directed Acyclic Graphs.
    11. Topological Order.
    12. Complete Graphs.
    13. Planar Graphs.
    14. Cliques, Independent Sets, Colorings.
  • Algorithms
    1. Paradigms.
      1. Greedy Algorithms.
      2. Divide and Conquer.
      3. Dynamic Programming.
    2. Searching.
      1. Linear Search.
      2. Binary Search.
      3. Depth-First Search.
      4. Breadth-First Search.
      5. Preorder, Postorder, Inorder, Level Order.
    3. Sorting.
      1. Bubblesort.
      2. Selection Sort.
      3. Mergesort.
      4. Polyphase Mergesort.
      5. Quicksort.
      6. Heapsort.
      7. Lower Bound on Sorting in the Comparison Model.
      8. Radix Sort.
    4. Shortest Paths.
      1. The Bellman-Ford Algorithm.
      2. The Floyd-Warshall Algorithm.
      3. Dijkstra's Algorithm.
      4. Johnson's Algorithm.
      5. The A* Algorithm.
    5. Miscellaneous Other Algorithms.
      1. Huffman's Algorithm.
      2. Kruskal's Algorithm.
      3. Union/Find.
      4. Finding the Median of a Set of Numbers in O(n) Time.
      5. Graham Scan.
      6. Closest Pair from a Set of Points in the Plane.
      7. Evaluation of an Expression.
      8. The Pseudo-polynomial Algorithm for the Knapsack Problem.
  • Complexity Theory, Again.
    1. 0-1 Problems.
    2. Reduction.
    3. The class P-TIME.
    4. The class NP-TIME.
    5. Guide Strings.
    6. Certificates = Witnesses.
    7. NP-Complete Problems.
      1. SAT.
      2. 3-SAT.
      3. The Clique Problem. (The Luce-Perry Problem.)
      4. The Independent Set Problem.
      5. The Knapsack Problem.
  • Additional Terms and Concepts.
    1. Concurrent Algorithms.
    2. The Primality and Factoring Problems, and RSA Coding. (But not the full details.)

    • Back to Course Page