CS 327, Spring 2018 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), n2, n3, 2n, 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"