
Recurrence
Equations
 Solve the recurrence equation T_{N} = 3T_{N/2} + N, where T_{1} = 1, using the Master Theorem. SHOW YOUR WORK.
 Solve the recurrence equation T_{N} = 3T_{N/2} + N, where T_{1} = 1, using the method of backward substitutions. SHOW YOUR WORK.
 Exponentiation
What is the order of magnitude of the following section of code that changes each element in an array to itself raised to the kth power. For example, if k=6 and a[2] is 4 then a[2] would become 4^6=4096. Show your work!!
void raise(int K) {
int j, rest;
for (int i = 0; i < N; i++ {
j = K;
rest = 1;
while (j > 1) {
if (j % 2 == 1) rest = rest * a[i];
a[i] = a[i] * a[i];
j = j / 2;
}//while
a[i] = a[i] * rest;
}//for
}
 Grouping Sort
Grouping sort works when there are N values placed in a RxS matrix where
N == RxS, R is divisible by S (that is R % S = 0), and R >= 2(S1)(S1).
After Grouping Sort runs, the matrix will have the values sorted when accessed from the first column to the Nth column (called columnmajor order).
The Algorithm
This is an 8step algorithm. The columns are sorted in steps 1,3,5 & 7 and the data is rearranged in steps 2, 4, 6 & 8 as follows:
 Step 2: Transpose – Access the values in columnmajor order and return them to the matrix in rowmajor order.
 Step 4: UnTranspose – Access the values in rowmajor order and return them to the matrix in columnmajor order.
 Step 6: Slide – In a columnmajor order sense, slide the data forward by floor(R/2) positions. This creates an extra column. Fill the emptied positions in the first column with MAXINT and the unused positions in the new column with MAXINT.
 Step 8: Unslide – Slide all values back (undo step 6) eliminating the extra column and the MAXINT and MAXINT values.
Example
Assume N=27, R=9 and S=3. The matrix is initialized as follows:
14 25 9
3 1 27
21 12 7
24 23 16
8 13 18
26 4 5
19 17 22
10 15 11
2 20 6
Step 1: The columns are sorted
2 1 5
3 4 6
8 12 7
10 13 9
14 15 11
19 17 16
21 20 18
24 23 22
26 25 27
Step 2: Transpose the Matrix
2 3 8
10 14 19
21 24 26
1 4 12
13 15 17
20 23 25
5 6 7
9 11 16
18 22 27
Step 3: The columns are sorted
1 3 7
2 4 8
5 6 12
9 11 16
10 14 17
13 15 19
18 22 25
20 23 26
21 24 27
Step 4: Untranspose
1 9 18
3 11 22
7 16 25
2 10 20
4 14 23
8 17 26
5 13 21
6 15 24
12 19 27
Step 5: The columns are sorted
1 9 18
2 10 20
3 11 21
4 13 22
5 14 23
6 15 24
7 16 25
8 17 26
12 19 27
Step 6: Slide
MI stands for MaxInt
MI 6 15 24
MI 7 16 25
MI 8 17 26
MI 12 19 27
1 9 18 MI
2 10 20 MI
3 11 21 MI
4 13 22 MI
5 14 23 MI
Step 7: The columns are sorted
MI 6 15 24
MI 7 16 25
MI 8 17 26
MI 9 18 27
1 10 19 MI
2 11 20 MI
3 12 21 MI
4 13 22 MI
5 14 23 MI
Step 8: Unslide
1 10 19
2 11 20
3 12 21
4 13 22
5 14 23
6 15 24
7 16 25
8 17 26
9 18 27
Questions
 What is the order of magnitude of this algorithm?
 How much extra space does it use?
 Is this a stable sort? Justify your answer.
 Are you convinced it will really work? Why or why not?
 Would you ever choose this sort over other sorting algorithms? Why or why not?
 Extra Extra Credit:Implement and run tests on Grouping Sort
 Triple Search
Consider the Triple Search algorithm for searching in a sorted array A[0..N1]:
 If N==1, compare the searchedfor key K with A[0].
 Otherwise compare K with A[n/3] and, if K is larger, with A[2n/3] to determine in which third of the array to continue the search.
Questions
 Set up and solve the recurrence for N = 3^{k}
 Compare this algorithm’s efficiency with binary search.
 Interpolation Search
There is a claim that interpolation search is worth considering for large files and for applications where comparisons are expensive or access costs very high. Do you agree? Why or why not? (Be specific. Convince me. Using math might be helpful).
 Linear Search vs Binary Search
Binary Search is typically a O(LgN) algorithm while Linear Search is O(N). Under what circumstances is it more efficient to sort an array and then perform a binary search vs what circumstances is it better to just go ahead and perform a linear search?
 Graphs
Given a graph G = (V,E), there are two ways we looked at to represent G in a program.
 Describe these two representations
 Describe the tradeoffs for picking one representation over another.