Complexity and Asymptotic Analysis

• For the following C++ code, identify the overall running time in terms of the “Big-Oh” notation” as a function of N, the number of elements in the l_int list. Briefly explain your reasoning for how you arrived at that running time. You may assume that each list and list iterator operations are done in constant time.
  
  Josh Allen (Fall 2013)
  
  

Trees

• Write a pseudocode for a recursive function that returns the height of a binary tree. You must check for an empty tree. You may assume a “max” function exists where it returns the maximum of two integer arguments. Your pseudocode does not have to be in any particular programming language, but it must be reasonably easy to follow.
  
  Cameron Kates
  
• For the following inorder and postorder sequences, reconstruct the original binary tree:
  inorder: γ α β
  preorder: γ α β
  
  Brandon Ray (Fall 2013)
  
• Write a pseudocode for a recursive function that returns the number of external nodes in a binary tree. You must check for an empty tree. Your pseudocode does not have to be in any particular programming language, but it must be reasonably easy to follow.
  John Marbach (Fall 2013)
  

Hash Tables

• Given the input values (in order) { 999, 99, 99, 88, 8 } and the hash function h(x) = x mod 10, construct diagrams reflecting the resulting hash tables of size 10 that resolve collisions via a) separate chaining, b) linear probing, and c) quadratic probing.
  
  Billy Humphrey (Spring 2014)
  

Binary Heaps and Binomial Queues

• Change the following minimum binary heap code into one that is appropriate for a maximum binary heap code. Briefly explain the algorithm and justify why the change is necessary.
  
  Gaurav Sheni (Spring 2014)
  
• For the following array of a random sequence of numbers, build a minimum binary heap using an algorithm that is performed with a running time of O(N). Briefly describe this algorithm and show the process using tree diagrams (i.e., not array).
  
  Jamie Floyd (Fall 2013)
  
• Perform the merge operation on the following two binomial queues.
  
  Claire Sheridan (Fall 2013)
  

Sorting Algorithms

• a) Sort the following list of numbers using the merge sort algorithm: (r, u, l, e, s)
  
  You must show every split and merge for full credit for full credit. What is the running time for the sorting?
  
  b) Taking the resulting list from a), apply the bubble sort algorithm. You must show every pass for full credit. What is the running time for the sorting?
  
  Tim Kreutzfeldt (Fall 2013)
  
• a) For the following data in the format (number, string), sort them in increasing order using the bubble sort algorithm keyed on the first value (number):
  
  (42, “Answer to the Ultimate Question of Life, the Universe, and Everything”)
  (42, “Kwon”)
  (3.14, “pi”)
  (2.718, “e”)
  (1.618, “Golden Ratio”)
  
  b) Sort the exact same list in (a) and apply the merge sort algorithm. You must show every split and merge for full credit.
  
  Niclas Ladd (Spring 2014)
  
• Recall that the merge sort algorithm consists of recursively dividing a list exactly in half, sorting each half, and merging the result. Prove the merge sort running time for the best, worst, or average case. You must show all work for full credit. Note: you only need to prove only one of the cases. There is no extra credit for proving all three cases. Hint 1: Think about the best case running time of the quick sort algorithm. Hint 2: Consider a substitution of k = log N in your proof.
  
  Rebecca Kotsonis (Fall 2013)
  
• Perform the insert operation for a) a binary heap and b) a binomial queue for the follow sequence of numbers: 1, 2, 3, 4, 5, 6, 7.
  
  Riana Freedman (Fall 2013)
  
• Write an insertion sort code into one that sorts the list in decreasing order.
  
  Jason Kholodnov (Fall 2013)
  

Parallel Sorting Algorithms

• Derive and identify the following expression:
  
  where p is the number of processors and f is the fraction of the inherently sequential portion of the computation. Assume that the communication between the processors is trivial (=0). You must explicitly identify each new variable introduced in your derivation.
  8 7 6 5 4 3 2 1
  
  Michael McGuiness (Spring 2014)
  
• As we discussed in class, Donald Knuth famously stated, “The bubble sort seems to have nothing to recommend it, except a catchy name and the fact that it leads to some interesting theoretical problems.” A) Correctly and explicitly identify a sorting algorithm that is related to bubble sort and B) show and briefly explain how to sort in increasing order the following unsorted list of using the sorting algorithm from (A):
  
  Kevin Davis (Spring 2014)
  
• In class, we discussed that one approach for implementing the radix sort algorithm is to bucket sort each of the digits. Recall that a bucket sort algorithm is a stable sorting algorithm.
  
  Show the steps of the radix sort algorithm that instead uses the odd-even transposition algorithm, which is not stable, to sort (in increasing order) each of the digits for the following sets of numbers:
  A) { 1011, 1010, 1001, 1000 }, B) { 83, 79, 67, 27 }. You must show all of the steps for full credit.
  C) Based on your observations in (A) and (B), is a stable sorting algorithm keyed on each of the digits required to correctly implement the radix sort algorithm?
  
  Austin Koeppel (Spring 2014)
  

Graph Algorithms

• List two topological sortings for the following directed acyclic graph.
  
  Sprigg Duvall (Spring 2014)
  
• Using Kruskal’s Method, find the minimal spanning tree of the graph below.
  
  Vicky Sostilio (Spring 2014)