CS 170 Reading Quiz -- Week 7, Tuesday

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. Suppose we are given an array A[1..n] of booleans. We want to find the longest interval A[i..j] such that every element in the interval is true -- in other words, so that A[i],A[i+1],..,A[j] are all true.

Professor Ecru proposes using dynamic programming, with the following choice of subproblems: a subproblem is specified by parameters r,s such that 1 ≤ r ≤ s ≤ n. He suggests we define F(r,s) = true if all of the entries A[r],A[r+1],..,A[s] are true, and F(r,s) = false otherwise.

How many subproblems are there, in Professor Ecru's approach? (It's OK to use big-O notation.) Also, show a recursive formula for F(r,s) that you could use to build a dynamic programming algorithm. Your recursive formula for F(r,s) should be defined in terms of the solution(s) to smaller/easier subproblem(s). You don't need to justify your answer.

2. Let's play a game where the input is a sequence A[1],..,A[n] of numbers. At each turn, you can either take the first number in the sequence, add it to your score, and then delete that element from the sequence; or you can delete the first number in the sequence, take the second number in the sequence and add it to your score, and then finally delete the second number from the sequence. You keep playing until all of elements in the sequence have been deleted. You want to find a choice of moves that maximize your score.

For instance, if the sequence is 5,-2,4,-4,-1,5, your best choice of moves is "take first, take second, take second, take first", for a total score of 5+4+-1+5 = 13.

Suppose we want to solve this problem using dynamic programming. Let f(i) denote the best score attainable starting from the sequence A[i],..,A[n]. Write a recursive formula for f(i). You don't need to explain or justify it; just show the recursive formula.

3. What did you find difficult or confusing about the reading for the upcoming lecture, 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.

4. What questions do you still have about previous material? 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