Information on the First Test

The first in-class test for this course will take place on Monday, March 4. You should expect a mix of definitions and essay questions; simple code analysis; understanding data structures such as B-Trees and representations of graphs; and applying basic algorithms such as merge sort, heap operations, inserting into a hash table, and graph traversal. Essay-type questions will make up the majority of the test. You will not be asked to code any complex algorithms. You might have to give an outline of an algorithm (such as heapsort or breadth-first search of a graph). You might even have to code something simple (such as quicksort, given the partitioning subroutine.)

The test covers material that is in the following chapters from the textbook (but mostly avoiding the math): Chapters 2, 3, 4, 6, 7, 8, 9, 11, 12, 18, and 22.

Here is a list of some of the things that you should know about:

problems and algorithms loop invariants using a loop invariant to prove correctness of a loop working with loop invariants: Initialization, Maintenance, Termination run-time analysis 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: T(n) = O(f(n)) if T(n) < c*f(n) for some c and for large n Big-Omega: T(n) = Ω(f(n)) if T(n) > c*f(n) for some c and for large n Big-Theta: T(n) = Θ(f(n)) if both T(n) = O(f(n)) and T(n) = Ω(f(n)) for Ω, Θ, and Big-Oh, you "ignore constant multiples and lower order terms" recurrence relations the Master Theorem for solving recurrence relations T(n) = a*T(n/b) + Θ(f(n)): Case 1: f(n) = O(n^d) where d < log_{b}(a). Then T(n) = Θ(n^{logb(a)}) Case 2: f(n) = Θ(n^d) where d = log_{b}(a). Then T(n) = Θ(n^{logb(a)}*log(n)) data structures heaps the max-heap property (or min-heap property) of a binary tree representing a heap as an array heap operations: insert and removeMax [or removeMin] priority queues using a heap as a priority queue hash tables, hash functions, and hash codes collisions in a hash table, and how they are handled open hash tables, using chaining to handle collisions closed hash tables, using open addressing to handle collisions linear probing in a closed hash table given a good hash function, operations on a hash table run in time Θ(1) binary search tree height of a tree; balanced binary tree insert, delete, find operations take time Θ(log(n)) on a balanced binary tree B-Trees minimal degree of a B-Tree data structures on secondary storage dynamic arrays amortized cost of adding an item to a dynamic array sorting algorithms and their run-time analysis: any sorting algorithm that works by comparisons has run time Ω(n*log(n)) in-place sorting algorithm (selection sort, insertion sort, heapsort) stable sorting algorithm (insertion sort, mergesort, counting sort, radix short) selection sort (run time Θ(n^{2})) insertion sort (average run time Θ(n^{2}); best case Θ(n)) mergesort (run time Θ(n*log(n)) heapsort (run time Θ(n*log(n)) quicksort (worst case run time Θ(n^{2}), average case Θ(n*log(n))) the quicksort partitioning algorithm randomizing the choice of pivot in quicksort, and why it's a good idea counting sort (run time Θ(n), but only applies in certain cases) radix sort (run time Θ(n), but only applies in certain cases) graphs: vertices and edges directed graphs and undirected graphs adjacency matrix representation of a graph adjacency list representation of a graph path in a graph cycle basic graph traversal algorithms marking vertices as "undiscovered", "discovered", and "processed" breadth-first search implementation of breadth-first search with a queue recursive depth-first search

To give you some idea of the kind of questions that might be on the test, here are just a few questions from old CS 327 exams:

**1.** Suppose A(n) is the average-case run time and W(n) is the worst-case
run time of the same algorithm. True or false: A(n) = O(W(n)). Explain your answer.
[With this question, I was probably too clever for my own good.]

**2.** The basic operation in the Quicksort algorithm is *partitioning* using a
*pivot* value. Explain the **goal** (or "postcondition") of partitioning.

**3.** Mark each of the following statements as being true or false:
(a) 5n^{3} + n2 = Θ(n^{3})
(b) n*log(n) = Θ(n)
(c) n*log(n) = Ω(n)
(d) n^{5} = O(n!)
(e) n + log(n) Θ(n)
(f) n^{3} + n^{2} = Θ(n^{5})

**4.** Give an algorithm (in clear pseudocode, with comments where needed) for
breadth-first search of a graph, starting from some given vertex v.

**5.** Draw the (undirected) graph that has the following adjacency matrix representation:
[Insert some square matrix of zeros and ons here.]

**6.** B-trees are balanced trees. Explain what this means and why it is important. (What does being balanced
say about the run time for inserting, deleting, and searching for items in the tree?)

**7.** Consider the heap shown below as a binary tree. Draw the heap after the following operations are
performed, one ofter the other: insert(24), removeMax(), removeMax().
[Insert a max-heap represented as a binary tree here.]