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;
}
Answer: O(1)
b) int square(int n)
{
int answer = 0;
for (int i = 0; i < n; i++){
answer += i+i+1;
}
return answer;
}
Answer: O(n)
c) int square(int n)
{
int answer = 0;
for (int i = 0; i < n; i++){
for (int j = 0; j < n; j++){
answer++;
}
}
return answer;
}
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?
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:
4) Trace the action of radix sort on the following list of 3 digit numbers:
Answer:
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 |
Answer:
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.
Answer:
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
comparisons made.
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?
Number of comparisons on average = 0.25n*n + O(n) For n = 7, this would give 49/4 = 12.25 comparisons. This is very close to the number above.
9. Consider the following graph:
a) Draw a representation of this graph using adjacency lists.
b) If you start with vertex a, what order will the vertices be visited using breadth first traversal? If there is a choice between two vertices, visit them in alphabetical order.
a b d f e c
c) If you start with vertex a, what order will the vertices be visited using depth first traversal? If there is a choice between vertices, visit them in alphabetical order.
a b f c e d
Home | | Syllabus | | Assignments | | Lecture Notes