University of Nevada Las Vegas
Howard R. Hughes
College of Engineering
School of Computer Science
My Home Page
![](../bluhorsa.gif)
UNLV CS 477/677 Fall 2015 Topics
(Not Necessarily in Chronological Order)
This Version August 25, 2015
Complexity Theory.
-
Big O, Ω, and Θ notation.
-
Examples of Recursive Algorithms: Mergesort and Binary search.
-
Solving Recurrences.
-
Master Theorem.
-
Analyzing Time Complexity of Programs.
Data Structures.
-
Linked Lists.
-
Abstract Data Types and Operators.
-
Integer:
Plus, Minus, Less Than, Etc.
-
Boolean:
And, Or, Not.
-
Priority Queue:
-
Delete Highest Priority, Insert.
-
Unfulfilled Obligations.
-
Stack, Queue, Min-heap, Max-heap, Other.
-
Search Structure:
-
Insert, Find, Delete.
-
Ordered List.
-
Unordered List.
-
Binary Search Tree.
-
B-Tree.
-
Hash Table.
-
Array:
-
Store, Fetch.
-
Stacks.
-
Push, Pop.
-
Stack Algorithms.
-
Depth First Search.
-
Evaluation of Expressions.
-
Run-Time Stack During Execution of a Program.
-
Queues.
-
Binary Search Trees.
-
Heaps.
-
Balanced Search Structures.
-
AVL Trees.
-
2-3 Trees.
-
Treaps. (Using Randomization to Obtain Balance.)
-
Hash Tables.
-
Closed or Open?
-
Linear Probing.
-
Other Probing.
-
Cuckoo Hashing.
-
Perfect Hashing.
-
Secondary Hashing.
-
Arrays.
-
Standard storage of arrays of dimensions 1, 2, or 3, in
row-major or column-major order.
-
Sparse Arrays.
-
Range Query Structures.
Graphs.
-
Directed Graphs.
-
Weighted Graphs.
-
Matrix Representation.
-
Neighbor Lists.
-
Sparse Graphs.
-
Connected Graphs.
-
Components.
-
Strongly Connected Directed Graphs.
-
Strong Components.
-
Directed Acyclic Graphs.
-
Topological Order.
-
Complete Graphs.
-
Planar Graphs.
-
Cliques, Independent Sets, Colorings.
Algorithms
-
Paradigms.
-
Greedy Algorithms.
-
Divide and Conquer.
-
Dynamic Programming.
-
Searching.
-
Linear Search.
-
Binary Search.
-
Depth-First Search.
-
Breadth-First Search.
-
Preorder, Postorder, Inorder, Level Order.
-
Sorting.
-
Bubblesort.
-
Selection Sort.
-
Mergesort.
-
Polyphase Mergesort.
-
Quicksort.
-
Heapsort.
-
Lower Bound on Sorting in the Comparison Model.
-
Radix Sort.
-
Shortest Paths.
-
The Bellman-Ford Algorithm.
-
The Floyd-Warshall Algorithm.
-
Dijkstra's Algorithm.
-
Johnson's Algorithm.
-
The A* Algorithm.
-
Miscellaneous Other Algorithms.
-
Huffman's Algorithm.
-
Kruskal's Algorithm.
-
Union/Find.
-
Finding the Median of a Set of Numbers in O(n) Time.
-
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, Again.
-
0-1 Problems.
-
Reduction.
-
The class P-TIME.
-
The class NP-TIME.
-
Guide Strings.
-
Certificates = Witnesses.
-
NP-Complete Problems.
-
SAT.
-
3-SAT.
-
The Clique Problem. (The Luce-Perry Problem.)
-
The Independent Set Problem.
-
The Knapsack Problem.
Additional Terms and Concepts.
-
Concurrent Algorithms.
-
The Primality and Factoring Problems, and RSA Coding.
(But not the full details.)
![](../bluhorsa.gif)
Back to
Course Page