Due: Friday, March 30th at the beginning of class (but not to hand in)
Read: Carrano & Prichard, Chs. 5, 6, 10
Solutions: Here
Problem 0: Review old quizzes, exams, and homeworks.
Problem 1: What can you say about the running time of the following two pieces of code as n gets large?
int sum = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
for (int k = 0; k < 2; k++)
sum += (i + 1) * (i + j - k);
int sum = 0;
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
for (int k = 0; k < n; k++)
sum += (i + 1) * (j + 1) * (k + 1);
Problem 2: Consider an array that contains the following elements.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| alpaca | bear | bunny | earwig | hyena | koala | octopus | slug | tapir | zebra |
Show which elements are checked when using binary search to attempt to find
Problem 3: Show the recursion tree for quicksort when called on an array that initially contains the following elements.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| my | split | personality | goes | and | comes | like | two | people | trapped | inside | of | one |
Show the result of partition on the invocations at the top two levels of the tree.
Trace through the operation of selection sort and insertion sort on the array given above, keeping track of the "important" operations done by each.
Problem 4: Consider the following grammar (ε stands for the empty string).