Topics for Final Exam
The final exam is open book and open notes. You are free to
use any computing devices as long as you do not communicate/search on the
Internet. The test is not comprehensive and will only cover the
material since the midterm (i.e. the Automata and Complexity material will
not be on the test, except for P/NP).
NP
 What it means for a problem to be in P, NP, or NP Complete
 You will definitely be given a problem where you prove, using
reduction from a known NPComplete problem, that some other problem is
NPComplete.
Math Basics
 BigO vs Theta vs Omega and LittleO notations
 You may need to solve summations (will give you the needed formula so
you don't need to memorize summations)
Solving recurrence relations
 You will definitely have to solve a recurrence relation on the exam.
 Substitution
 Iteration / Recursion Tree
 Master Method
Selection Problem
 How to partition an array in linear time, no additional space
 Good, bad cases for partitioning and impact on the algorithm
runtime
 Different methods for selecting the partition element
 Using the partition routine to select the ith largest element in
expected linear time
Sorting
 Insertion Sort
 Merge sort
 Quick sort
 Count sort
 Radix sort
 Bucket sort
Graphs

Basic concept, edges, vertices, relationship

Directed, Undirected

Adjacency List vs. Adjacency Matrix, advantages/disadvantages

Properties of connected graphs, relationship between E and V

Breadth First Search

Algorithm, Purpose, space/time behavior

Run on a graph, be able to identify when it may be useful

Use to detect a bipartite graph

Depth First Search

Algorithm, Purpose, space/time behavior

Run on a graph, be able to identify when it may be useful

Detecting cycles

DAG, Directed Acyclic Graph

Minimum Spanning Tree

Shortest Path  Runtime using Dijkstra's Algorithm

Maximum Flow

Be able to demonstrate FordFulkerson method on a graph

Be able to calculate residual network

Reduce some other problem to the maximum flow for a graph

There will be a graph problem that incorporates aspects of several
of the above
Dynamic Programming