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"
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