The first test for this class will have two parts, an in-class part and a take-home part. The in-class part will take place on Wednesday, February 27. The take-home part will be available at that time.
For the in-class part, you should expect a mix of definitions, essay questions, coding, code analysis, and other questions. For the coding questions, I might ask you to present an algorithm in pseudocode. By code analysis, I mean looking at a code segment and determining its run time efficiency. Other questions might include, for example, things like applying some operation to a given graph or array.
The in-class part of the test will not include anything about recurrence relations. There might be something about recurrence relations and their solutions on the take-home part of the test.
Here is a list of some of the things that you should know about:
algorithm
time efficiency and space efficiency of algorithms
measuring the input size of a problem
measuring the run time of an algorithm
finding the run-time efficiency of basic (non-recursive) algorithms
the "basic operation" of an algorithm
wort case, average case, and best case analysis
"order of growth" of a function
comparing order of growth of common functions:
1, log(n), n, n*log(n), n2, n3, 2n, n!
Big-Oh: O(f(n)) is the set of functions g(n)
such that g(n) < c*f(n) for some c and for large n
Big-Omega: Ω(f(n)) is the set of functions g(n)
such that g(n) > c*f(n) for some c and for large n
Big-Theta: Θ(f(n)) is the set of functions g(n) such that
c1*f(n) < g(n) < c2*f(n) for some c1,c2 and for large n
for Ω, Θ, and Big-Oh, you "ignore constant multiples and lower order terms"
brute force algorithms
brute force string matching algorithm
convex sets
the convex hull problem
brute force convex hull algorithm
exhaustive search
the Traveling Salesman problem, and its exhaustive search algorithm
the Knapsack Problem, and its exhaustive search algorithm
graphs
vertices and edges
directed graphs and undirected graphs
adjacency matrix representation of a graph
adjacency lists representation of a graph
weighted graph
path in a graph
cycles
acyclic graphs
connected component of an undirected graph
graph traversal algorithms
recursive depth-first search
marking vertices as "visited"
breadth-first search
implementation of breadth-first search with a queue
implementation of depth-first search with a stack
run-time analysis of depth-first and breadth-first search
using depth-first or breadth-first search to detect cycles
using depth-first or breadth-first search to find connected components
dag (directed acyclic graph)
topological sort of a directed acyclic graph
using depth-first search to do a topological sort
the source removal algorithm for topological sort