Final quiz solutions

Consolation question What are your first and last names?

Carl and Burch

Write a program to determine whether a name the user types begins with a vowel. Following is a sample run of the program you will write.

What is your name? CBurch
No vowel.

You may assume that the first letter is a capital letter. Do not count Y as a vowel (with apologies to all Yvonnes).

#include <iostream>
#include <string>

int main() {
    string name;
    cout << "What is your name? ";
    cin >> name;

    if(name[0] == 'A' || name[0] == 'E' || name[0] == 'I'
            || name[0] == 'O' || name[0] == 'U') {
        cout << "Vowel" << endl;
    } else {
        cout << "No vowel" << endl;
    }
    return 0;
}

Consider the following recursive function.
```
int f(int n) {
    if(n == 1) {
        return 1;
    } else if(n % 2 == 0) { // n is even
        return f(n / 2);
    } else { // n is odd
        return 2 * f((n - 1) / 2);
    }
}
```
- a. If a program calls f(42), what does the function do?
  
  It returns 4.
- b. Bonus question! What is significant about the function that the above is intended to compute?
  
  It is half the number of odd entries in the nth row of Pascal's triangle. (Except for the first row, of course.)
Using Big-O notation in terms of n, give the strongest bound you can for the following function.
```
// sorts the array arr, of length n
void sort(vector<int> &arr, int n) {
    for(int i = 0; i < n; i = i + 1) {
        // find index of minimum in arr[i...n-1]; call it minpos
        int minpos = i;
        for(int j = i + 1; j < n; j = j + 1) {
            if(arr[j] < arr[minpos]) { // we found smaller item
                minpos = j;
            }
        }

        // swap array positions i and minpos
        int temp = arr[minpos];
        arr[minpos] = arr[i];
        arr[i] = temp;
    }
    return;
}
```
Justify your answer in at most 3 sentences.

O(n²). Each time we get to the inner for loop, we go through n-(i+1) iterations of it. Since always i>=0, this is at most n-1, and so the inner for loop takes O(n) time. The rest of the inside of the outer for loop takes O(1) time, for a total of O(n) time per iteration; we go through n iterations of it, for a total of O(n * n) time.

(This sorting technique, by the way, is called selection sort. It's simpler to program than the Merge Sort we saw in class, but it's also quite a bit slower.)
Challenge question! Develop a fast algorithm for the following problem.
Problem Longest-Increasing-Subsequence:
Input: An array A of real numbers.
Output: The length of the longest increasing subsequence of A.
An increasing subsequence is a subsequence of elements, each of which is strictly larger than the last. For example, the longest increasing subsequence of the array A=<4,5,1,2,7,3,6> is <1,2,3,6>, and so your algorithm would return 4, the number of elements in this subsequence.

Your algorithm should take O(n⁵) time (probably much less), where n is the length of A. Describe your algorithm using pseudocode, and give a big-O bound for its performance.

We can apply dynamic programming to solve this problem. Our recursive solution L(k) tells the longest subsequence using A[0..(k-1)] and ending at A[k].
L(0) = 1, L(k) = max_{i<k,
A[i]<A[k - 1]} 1 + L(i)
This says that the longest tower ending with A[k] will be preceded by some longest subsequence ending with some smaller number preceding it in A. (The recurrence is slightly incorrect in that it computes the wrong number if the number is smaller than everything preceding it... The pseudocode below corrects this error by initializing L[k] to be 1.)

Now applying dynamic programming to compute this bottom up, we get the following pseudocode.
Algorithm LIS(A):
Let n be the length of A.
Let L be an array of length n.
Let L[0] be 1.
for each k from 1 to n - 1, do:
    Let L[k] be 1.
    for each i from 0 to k - 1, do:
        if A[i] < A[k] and L[i] + 1 > L[k], then:
            Let L[k] be L[i] + 1.
        end of if
    end of loop
end of loop
return max_0<=k<n L[k].
The run-time analysis for this proceeds exactly as for the sort() function of #4; it takes O(n²) time.