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 NP-Complete problem, that some other problem is NP-Complete.

Math Basics

• Big-O vs Theta vs Omega and Little-O 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

• 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
  • Topological sort using DFS
• Minimum Spanning Tree
• Runtime analysis of graph algorithms using various data structures
• Shortest Path - Runtime using Dijkstra's Algorithm
• Maximum Flow
• Be able to demonstrate Ford-Fulkerson 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

• Come up with the dynamic programming solution; e.g. a D[current-sized-problem] = D[smaller-sized-problem]
• An understanding of how the following examples work will help you to solve the test problem
  • Floyd-Warshall All Pairs Shortest Path algorithm
  • Approximate String Matching
  • Knapsack Problem