UNLV
CS 477 Spring 2022
The third exam is scheduled for April 20, 2022

Asymptotic complexity of code fragments and recurrences (old material)

You should understand these algorithms and data structures:

Johnson's algorithm
A* algorithm
BFPRT selection algorithm (median of medians)
Randomized selection
Huffman's algorithm
Kruskal's algorithm
Hashing (all kinds of hashing, all issues related to hashing)
Treaps (Remember?)
Sparse arrays
Implementation of a sparse array using a search structure
Represention of an array in RAM (all versions)
Dynamic Programming
Memoization

Questions about time complexity of various algorithms we've studied, not just
those listed above.

There will be no questions about NP-completeness.