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, March 7. The take-home part will be handed out at that time.

For the in-class part, you should expect a mix of definitions and essay questions; simple code analysis; and applying basic algorithms such as merge sort, heap operations, and graph traversal. Essay-type questions will make up the majority of the test.

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 finding the run-time efficiency of basic (non-recursive) algorithms 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: g(n) = O(f(n)) if g(n) < c*f(n) for some c and for large n Big-Omega: g(n) = Ω(f(n)) if g(n) > c*f(n) for some c and for large n Big-Theta: g(n) = Θ(f(n)) if both g(n) = O(f(n)) and g(n) = Ω(f(n)) for Ω, Θ, and Big-Oh, you "ignore constant multiples and lower order terms" proof of correctness of algorithms loop invariants summation notation proof by induction any sorting algorithm that works by comparisons has run time Ω(n*log(n)) basic data structures efficiency of various operations on linked lists and arrays dynamic arrays amortized cost of adding an item to a dynamic array binary search tree height of a tree; balanced binary tree insert, delete, find operations take time Θ(log(n)) on a balanced binary tree hash tables, hash functions, and hash codes open hash tables versus closed hash tables collisions in a hash table, and how they are handled linear probing in a closed hash table heaps heap operations: insert and removeMax [or removeMin] using a heap as a priority queue storing a heap in an array sorting algorithms and their run-time analysis: selection sort insertion sort heapsort mergesort quicksort the quicksort partitioning algorithm radix sort (with run time Θ(n)) graphs applications of graphs vertices and edges directed graphs and undirected graphs adjacency matrix representation of a graph adjacency lists representation of a graph path in a graph cycle connected component of an undirected graph graph traversal algorithms recursive depth-first search marking vertices as "undiscovered", "discovered", and "processed" 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 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