CS 3343 Analysis of Algorithms Exam 1 Review

• 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

• Back to CS 3343 Homepage