CS 170 Reading Quiz -- Week 7, Monday

Please fill out this quiz, and press the "Submit" button at the end. Don't collaborate with anyone on quiz exercise solutions.

Please answer all questions.

Name:

SID: [No spaces and no dashes.]

1. If L is a list, a subsequence of L is a subset of the elements of L, in the same order that they appear in L. (The elements don't have to be contiguous; they can be any subset of L.) A subsequence is increasing if each number is larger than the one before it. In this question, the goal is to find the longest increasing subsequence of L that starts with the first element of L.

For instance, if we are given L=[2,3,1,7,4,9], one increasing subsequence is [2,3,7,9]; another is [2,3,9]; another is [2,3,4]; another is [2,9]; and so on. The longest one is [2,3,7,9]. [2,3,4,9] also has the same length, so it would be equally good. So, if we were given L, the desired answer would be either [2,3,7,9] or [2,3,4,9] (either one is fine).

Consider the following greedy algorithm for solving this problem. We include the first element of L in our subsequence. Then, we find the first element of L after that one that is larger than it, and include it in the subsequence. We repeatedly find the first number from L that comes after the last one selected and that is larger than the last one selected, and select it for inclusion in the subsequence. Repeat this until L is exhausted.

If you prefer to read pseudocode:

f(x, L):
1. If L = [], then return [].
2. If head(L) > x, then return head(L)::f(head(L), tail(L)).
3. Otherwise, return f(x, tail(L)).

Greedy(L):
1. Return head(L)::f(head(L), tail(L)).

(Notation: head(L) represents the first element of list L; tail(L) represents the rest of L, not including the first element; and x::y represents a list containing x followed by all of the elements of y. In Scheme terms, these three operators are car, cdr, and cons. Also, [] represents the empty list.)

Question: Is Greedy(L) guaranteed to find the longest increasing subsequence of L that starts with L's first element? If yes, explain why briefly. If no, give a counterexample.

2. Have you heard of amortized running time, before this course? A "yes" or "no" answer is sufficient. If you say "yes", it might help if you mentioned where you've seen it before. (This question will not be graded; it's just for my information, so that I can prepare Monday's lecture.)

3. What did you find difficult or confusing about the reading or the lectures, and what would you most like to see explained better? If nothing was difficult or confusing, and you understand the material pretty well, tell us what you found most interesting. Please be as specific as possible.

CS 170 home page