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.
[No spaces and no dashes.]
Login ID :
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
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
Write a recursive formula for f(i).
You don't need to explain or justify it; just show the recursive