## Solutions to Review Questions for Final Exam

Home | | Syllabus | | Assignments | | Lecture Notes

The following problems are intended to help you study for the exam, however topics not covered here may be on the exam as well. Use your text, class notes, labs and assignments to review for the exam as well.

1) Below are several functions for computing the square of a number. For each function, what is the Big-Oh estimate of the runtime for this code, and how did you arrive at it?

```a)	int square(int n)
{
return n*n;
}
```

```b)	int square(int n)
{
int answer = 0;
for (int i = 0; i < n; i++){
}
}
```

```c)	int square(int n)
{
int answer = 0;
for (int i = 0; i < n; i++){
for (int j = 0; j < n; j++){
}
}
}
```

Answer: O(n^2), where n^2 indicates n squared.

2) Explain what the best case and worst case situations are for QuickSort. What is the running time for each of these cases and how do you arrive at that running time?

Answer: Best Case: The pivot partitions the list into two equal halves each time. In this case, QuickSort behaves like MergeSort. The running time is O(nlgn) (See the MergeSort lecture for the derivation of this).

Worst Case: The pivot partitions into a list of size (n-1) and a list of size 1. In this case the running time is the sum from k=0 to n-1 of k, which is n(n-1)/2, which is O(n^2).

3) A tri-diagonal matrix is a square matrix in which all entries are 0 except possibly those on the main diagonal and on the diagonals immediately above and below it. That is, T is a tri-diagonal matrix means that T(i, j)= 0 unless |i - j| <= 1 as shown below. Devise a space-efficient storage scheme for tri-diagonal matrices, and give the corresponding index function.

Answer: The matrix can be stored as a table in a contiguous implementation with only the non-zero positions represented as follows:

An index function that assigns a(i,j) to the appropriate position in this table is:

index = 3(i -1) + (j -i) = 2*i -3 + j

4) Trace the action of radix sort on the following list of 3 digit numbers:

342 147 257 973 552 286

```	List    Pass1    Pass2    Pass3
342     342      342      147
147     552      147      257
257     973      552      286
973     286      257      342
552     147      973      552
286     257      286      973
```

5) Write a function to insert an entry into a hash table using linear probing. (Assume the hash function has been written and returns an integer location for an entry to be stored in the table).

```Error_code Hash_table::insert(const Record &new_entry) {
Error_code result = success;
int probe_count,  // Counter to be sure that table is not full.
probe;            // Position currently probed in the hash table.
Key null;         // Null key for comparison purposes.
null.make_blank( );

probe = hash(new_entry);   //Find location to insert new_entry

probe_count = 0;
while (table[probe] != null          // Is the location empty?
&& table[probe] != new_entry 	 // Duplicate key?
&& probe_count < (hash_size) { // Has overflow occurred?
probe_count++;
probe = (probe + 1)%hash_size;
}
if (table[probe] == null)
table[probe] = new_entry;     // Insert new entry.
else if (table[probe] == new_entry)
result = duplicate_error;
else
result = overflow;           // The table is full.
return result;

}```

6) The following list of numbers is an access array for a table. Draw the 2D table that is represented by this array. What is the index function that indicates the start of each table row?

 0 1 4 9 16 25

index(i, j) = i^2 + j

7) Write a recursive function that will interchange all left and right subtrees of a binary tree. The function should take one parameter, a pointer to the root (or subroot) of the tree (or subtree) to be interchanged.

```template <class Entry>
void Binary_tree<Entry>::recursive_interchange(Binary_node<Entry> *sub_root) {
if (sub_root != NULL ) {
Binary_node<Entry> *temp;
temp = sub_root->left;
sub_root->left = sub_root->right;
sub_root->right = temp;
recursive_interchange(sub_root->left);
recursive_interchange(sub_root->right);
}
}

8 a)Trace the steps that insertion sort will take to sort the following list of
numbers from lowest to highest.  For each step, indicate the number of

Total comparisons: 12

b) Write the formula for the average number of comparisons made by insertion sort
for a random list.  How close is the total number of comparisons above to the
average number predicted by the formula?