Information on the First Test

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), n^{2}, n^{3}, 2^{n}, 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 c_{1}*f(n) < g(n) < c_{2}*f(n) for some c_{1},c_{2}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