CS 3343 Analysis of Algorithms Final Exam Review
Most of this is from the first two exams.
- Big O and Big Omega notation
You should know the definitions of big-Oh and big-omega.
You should be able to show a particular function is or is not O of some
other function.
- Determining the order of a program segment
- You should understand the following abstract data types,
how they are represented, and the order of the basic operations on them:
- Directed graphs
- Directed acyclic graphs (dag)
- Undirected graphs
- Free trees
- Sets (with MERGE and FIND)
- You must know the following algorithms and understand:
what problem they solve
the order of the algorithm
trace on an example
general idea of the algorithm (in words)
implementation methods
- Named Algorithms (you must know them by name):
- Dijkstra (Single Source Shortest Path)
- Floyd (All-Pairs Shortest Path)
- Warshall (Transitive Closure)
- Prim (Minimum-Cost Spanning Tree)
- Kruskal (Minimum-Cost Spanning Tree)
- Unnamed Algorithms:
- Depth-First Search
- Depth-First Spanning Forest
- Test for Acyclicity
- Topological Sort
- Growth rates of functions
- big-oh, big-omega, big-theta
- Stirling's approcimation
- lg*
- simple proofs
- Determining the order of a program segment
- Sorting algorithms:
For each of the following sorting algorithms you should know:
- the algorithm used
- the order of the algorithm for best, worst and average case
- how to apply the algorithm to a particular example
- bubble sort
- insertion sort
- selection sort
- Quicksort
- heap sort
- bin sort
- radix sort
- Decision trees
- Simple recurrence relations
- Solving recurrence relations
- guessing an answer
- substitution
- Master Theorem
- Greedy Algorithms