Maximum score: 100 points + 15 extra.
Extra credit points do not affect the curve.
To be eligible for extra credit, you need to earn at least
70 regular points.
All complexity estimates are for runtime (not for memory), unless specified otherwise.
Each line in the table corresponds to an algorithm or an algorithmic problem. Write P for problems and A for algorithms. A problem gives input and output, but an algorithm additionally entails a particular method of achieving this output. Fancy data structures (e.g., heaps, BSTs and hashtables) often imply specific algorithms. Simple containers (e.g., arrays and linked lists) are typically used to store input or output and may restrict possible algorithms.
For each algorithm, write its Thetacomplexities.
For each problem, write Thetacomplexities of a best
possible algorithm that solves the problem.
There can be multiple correct answers, especially, if
there is a tradeoff between averagecase and worstcase performance.
No explanation necessary.
You can assume that operator< and operator==
for values stored in containers run in O(1) time.
You cannot make any additional assumptions about algorithms/problems
unless instructed by Prof. Brehob or Prof. Markov.
Each line is worth 2 points. Each wrong or missing
answer on a line costs 1 point.
Minimum per line = 0 points.
Algorithm or Problem:  ?  Bestcase Theta()  Avgcase Theta()  Worstcase Theta()  
1.  Find a given value in an unsorted NbyN matrix.  P  1  N^{2}  N^{2} 
2.  Binary search over N elements  A  1  log N  log N 
3.  Find the largest element in an unsorted array with N elements  
4.  Print all values appearing at least twice in a sorted stack of size N  
5.  Insert a new element into a sorted singlylinked list
with N elements
so that the list remains sorted 

6.  Given two unsorted arrays of N and N/10 elements, say whether they have at least one common element  don't bother  
7.  Shaker sort of a doublylinked list with N elements, using "early termination".  
8.  Duplicate a queue of N elements  
9.  One invocation of the partition() function used in the quicksort algorithm. Assume inplace partitioning of a complete array with N elements using a given pivot  
10.  Given a pointer to an element in a singlylinked list with N elements, remove that element from the list  
11.  Sort N 8bit characters stored in an array.  
12.  Remove the middle element from an unsorted array of N elements  
13.  Compute N! for a given N using a straightforward recursive algorithm  
14.  Find the combination of N decimal digits that opens a bank safe. The safe opens when you enter the right combination, and you can try as many combinations as you wish. No other feedback is available  
15.  Print all diagonal values of a given NbyN matrix 
Fill in the blanks
Algorithm or Problem:  Bestcase Theta()  Avgcase Theta()  Worstcase Theta()  
1.  Print all values stored at nodes of a given tree with N nodes  
2.  Convert a binary heap of N elements into a sorted array  don't bother  
3.  Test whether a given array with N values is in a binaryheap order  
4.  One search in a BST of N elements. Assume that the tree is perfectly balanced and the search results in a miss  
5.  One successful lookup in a hash table with N elements and load
ratio^{*} 1.0. The hashtable uses separate chaining with singlylinked
lists. Assume that hashfunction can be computed in O(1) time.
Note: elements contained in the hashtable may be poorly dispersed. 
^{*} The load ratio of a hashtable with N elements and M buckets is N/M.
struct Key { char p1, p2, p3 };
unsigned f1(struct Key& s)
{ return s.p1+5*s.p2; }
unsigned f2(struct Key& s)
{ return 10*s.p1+100*s.p2+1000*s.p3; }
unsigned f3(struct Key& s)
{ return 11*s.p1+101*s.p2+1001*s.p3; }
Assume a hashtable of size 1250 with linear probing.
Mark each hashfunction as good or bad.
Use space below to explain.
 5 points. Fill in the blanks.
Markov section only
In BSTs, ______ and ______ rotations have time complexity
Theta(____).
They are explicitly used in _______ insertion and ________ algorithms.
Two BSTs can be joined using a _________ algorithm, which
applies _______ ________ to one of the trees. The worstcase
complexity of such a join algorithm is Theta(_____), but
the best case can be faster when ______________________________________________________.
Brehob section only
Each node in a 234 tree has ____, ____ or ____ keys in it.
___________ trees are an implemention of 234 trees.
Insertion into a 234 tree has worstcase complexity
Theta(____) and search has worstcase complexity
Theta(____).

20 points. Algorithm design: Recursion / Divide and Conquer / Dynamic Programming
Implement the following C++
function
void makeBalancedBST(unsigned *begin, unsigned numElem);
which takes an unsorted array and makes a balanced BST out of it,
stored left to right so that children of element k be
2*k and 2*k+1. You must achieve worstcase complexity
O(numElem log^{2}(numElem)) and explain how you did it.
15 points for the case when numElem is a power of two minus one
(say, 3, 7 or 15),
5 additional points for the general case. Use a separate page.

20 points. Questions related to HWKs and Projects
 5 points. Provide a dictionary produced by the Huffman algorithm
applied to this input: AAABAABCCDCC. No explanation necessary.
 5 points. Heapify the digits of your student ID.
Start with the digits in the original order
and show the process step by step.
 10 points. You are given a function that takes N planar points
and returns all points on the boundary of the convex hull
listed clockwise.
Provide an algorithm (in pseudocode or valid C++) that
sorts N
double
s using that function
and spends O(N) time outside that function.
 Extra credit: 15 points. ``Comments not available''.
In this question you are given a printout of a C++ function,
with coke spilled over the comments (=> you can't read the comments).
You need to explain what the function does, illustrate by several
representative examples, give worstcase/bestcase Theta() for runtime
and substantiate these complexity estimates.
int L2(const char * A, const char * B)
// COMMENTS NOT AVAILABLE
{
int m=strlen(A), n=strlen(B), i, j;
int L[m+1][n+1]; // g++ extension to C++
for (i = m; i >= 0; i)
for (j = n; j >= 0; j)
{
if (A[i] == '\0'  B[j] == '\0') { L[i][j] = 0; }
else if (A[i] == B[j]) L[i][j] = 1 + L[i+1][j+1];
else L[i][j] = max(L[i+1][j], L[i][j+1]);
}
j=L[0][0];
return j;
}
Source code courtesy of Prof. David Eppstein.