28 Feb 1996

Outline

Today we will review for tomorrow's midterm. Topics for the midterm include:

C++ programming (especially classes)
lists, stacks and queues,
recursion
analyzing correctness/running times of programs
order notation
dynamic programming and memoizing
trees, including binary search trees

We'll be going over several examples, in the following areas:

Analyzing the running times of programs
Dynamic programming
Memoizing
Binary search trees

We'll also cover questions from last year's midterm.

Analyzing the running times of programs

The following questions appeared on Assignment 3 last year.

Use Theta asymptotic notation to describe the running time of the following routines. Express your answer in the simplest form you can (e.g. Don't say Theta(5n+3). Say Theta(n) instead).

int
fee(int n) {
    int i, j, k, result = 5;
    for(i=0; i < n; ++i)
        for(j=0; j < 2*n; ++j)
            for(k=0; k < n/2; ++k)
                ++result;
    return result;
}

int
fie(int n) {
    int i, j, result = 0;
    for(i = 0; i < n; ++i) {
        result = result + i;
        for(j = 0; j < i; ++j) result += j;
    }
    return result;
}

int
foe(int n) {
    int i, j, result = 5;
    for(i = n; i > 1; i /= 2) {
        for(j = 0; j < i; ++j) ++result;
    }
    return result;
}

int
fum(int n) {
    int i, result = 0;
    for(i = 1; i < n; i *= 2) result = result + i;
    return result;
}

int
foo(int n) {
    if(n < 1) return 1;
    else return 2 * foo(n - 1);
}

int
foo2(int n) {
    if(n < 1) return 1;
    else return foo2(n - 1) + foo2(n - 1);
}

And here are the answers:

T(n) = Theta(n^3)
T(n) = Theta(1+2+3+...+n) = Theta(n^2)
T(n) = Theta(n/2 + n/4 + n/8 + ... + 1) = Theta(n)
T(n) = Theta(log n)
T(n) = T(n-1)+c_1, T(0) = c_2, where c_1, c_2 are constants therefore T(n) = Theta(n)
T(n) = 2T(n-1)+c_1 T(0) = c_2, where c_1, c_2 are constants therefore T(n) = 4T(n-2)+c_2+c_2 = 8T(n-3)+c_2+c_2+c_2 = 2^n T(0)+ n*c_2 = Theta(2^n)

Dynamic programming

Consider how we would write a program to find the longest increasing subsequence of a sequence of integers, represented by an array. (Here we're using subsequence like before: the elements need not necessarily be adjacent in the array.)

Here's a program to do it:

// input in array a of length N
// length[i] is length of longest increasing subsequence ending with a[i]

for(i = 0; i < N; i++) {
    length[i] = 1;  // a[i] by itself is a subsequence of length 1
    for(j = 0; j < i; j++) {
        if(a[j] < a[i] && length[j] + 1 > length[i]) {
            length[i] = length[j] + 1;
        }
    }
}

What's its runtime? (Theta(1+2+3+4+...+N) = Theta(N^2).)

Memoizing

The following recursive program is a solution to Assignment 3. It is not the dynamic programming solution that we asked for, however.

// N is number of different investments
// T is number of weeks
// sell[i] is the cost to sell investment i
// buy[i] is the cost to buy investment i
// gain[i,w] is the increase in value of investment i during week w
// maximize returns maximum value possible if all money is in investment i
//   at end of week w

double
maximize(int i, int w) {
    double best_value = 0.0;
    double next_value;
    if (w == 0 && i == 0) return 1.0;
    if (w == 0 && i > 0) return 0.0;
    for (int j = 0; j < n; j++){
        if (j == i) next_value = maximize(i, w - 1) * gain[i, w];
        else next_value = maximize(j, w - 1) * sell[j] * buy[i] * gain[i, w];
        if (next_value > best_value) best_value = next_value;
    }
    return best_value;
}

This is pretty simple, but it's not a good solution. The running time is Theta(N^T) -- superexponential! (Time(T) = N*Time(T-1), Time(0) = constant.)

The program can easily be made efficient using memoizing. (Using only 2 additional lines of code!)

// best[i,w] is the maximum value possible if all money was in
//           investment i at end of week w
//           initially best[i,w] == -1 for all i and w

double
maximize(int i, int w){
    double best_value = 0.0;
    double next_value;

    if (best[i, w] != -1) return best[i, w];

    if (w == 0 && i == 0) return 1.0;
    if (w == 0 && i > 0) return 0.0;
    for (int j = 0; j < n; j++){
        if(j == i) next_value = maximize(i, w - 1) * gain[i, w];
        else next_value = maximize(j, w - 1) * sell[j] * buy[i] * gain[i, w];
        if(next_value > best_value) best_value = next_value;
    }
    best[i,w] = best_value;
    return best_value;
}

Now the running time is Theta(N^2 * T) - we compute best[i,w] exactly once, and it takes N time to do it.

Binary Search Trees

Here's a standard routine for searching for a key k:

node*
search(node *root, int k) {
    if(root == NULL) return NULL;
    if(root->value > k) return search(root->left, k);
    if(root->value < k) return search(root->right, k);
    return root;
}

Now suppose we want to write a function that returns a pointer to the node containing k if it finds it, and otherwise returns a pointer to the node holding the largest key smaller than k in the subtree rooted at root (NULL if there is no such node). Here's the code:

node*
search(node *root, int k) {
    node *right_search;
    if(root == NULL) return NULL;
    if(root -> value > k) return search(root->left, k);
    if(root -> value < k) {
        right_search = search(root->right, k);
        if(right_search == NULL) return root;
        else return right_search;
    }
    return root;
}