Carl and Burch
You may assume that the first letter is a capital letter. Do not count Y as a vowel (with apologies to all Yvonnes).What is your name? CBurch No vowel.
#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; }
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); } }
It returns 4.
It is half the number of odd entries in the nth row of Pascal's triangle. (Except for the first row, of course.)
Justify your answer in at most 3 sentences.// 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; }
O(n2). 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.)
Problem Longest-Increasing-Subsequence: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.
Input: An array A of real numbers.
Output: The length of the longest increasing subsequence of A.
Your algorithm should take O(n5) 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) = maxi<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):The run-time analysis for this proceeds exactly as for the sort() function of #4; it takes O(n2) time.
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 max0<=k<n L[k].