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
-
Data Structures.
-
Stack.
-
Queue.
-
Heap.
-
Array.
-
Linked List.
-
Binary Search Tree.
-
Balanced Search Trees.
-
AVL Tree.
-
2-3 Tree.
-
Treap. (Using Randomization to Obtain Balance.)
-
Hash Table.
-
Closed or Open?
-
Linear Probing.
-
Other Probing.
-
Cuckoo Hashing.
-
Perfect Hashing.
-
Secondary Hashing.
-
Standard storage of arrays of dimensions 1, 2, or 3, in
row-major or column-major order.
-
Sparse Array.
-
Graphs.
-
Directed Graphs.
-
Weighted Graphs.
-
Matrix Representation.
-
Neighbor Lists.
-
Sparse Graphs.
-
Range Query Structures.
-
Algorithms
-
Greedy Algorithms.
-
Divide and Conquer.
-
Dynamic Programming.
-
Linear Search.
-
Binary Search.
-
Bubblesort.
-
Selection Sort.
-
Radix Sort.
-
Mergesort.
-
Polyphase Mergesort.
-
Quicksort.
-
Heapsort.
-
Huffman's Algorithm.
-
Kruskal's Algorithm.
-
Union/Find.
-
Depth-First Search.
-
Breadth-First Search.
-
Finding the Median of a Set of Numbers.
-
The Bellman-Ford Algorithm.
-
The Floyd-Warshall Algorithm.
-
Dijkstra's Algorithm.
-
The A* Algorithm.
-
Graham Scan.
-
Closest Pair from a Set of Points in the Plane.
-
Evaluation of an Expression.
-
The Pseudo-polynomial Algorithm for the Knapsack Problem.
-
Complexity Theory.
-
Big O, Omega, and Theta notation.
-
Solving Recurrences.
-
Analyzing Time Complexity of Programs.
-
Lower Bound on Sorting.
-
0-1 Problems.
-
Reduction.
-
The class P-TIME.
-
The class NP-TIME.
-
Guide String.
-
Certificate = Witness.
-
NP-Complete Problems.
-
SAT.
-
3-SAT.
-
The Clique Problem (what I called the Luce-Perry Problem on the test)
-
The Independent Set Problem.
-
The Knapsack Problem.
-
Additional Terms and Concepts.
-
Preorder, Postorder, and Inorder.
-
Lazy Deletion.
-
Connected Graph.
-
Component.
-
Complete Graph.
-
Cyclic Directed Graph.
-
Topological Order.
-
Strong Component.
-
Abstract Data Types and Operators.
-
The Primality and Factoring Problems, and RSA Coding.
(But not the full details.)

Back to
Course Page