CS 170 Reading Quiz -- Week 9, 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. Suppose we are given a mxn matrix M[1..m][1..n]. We want to find the largest subrectangle of the matrix, such that all of the entries of the matrix within the subrectangle are zero. (By largest, we mean largest by area.)

Professor Celadon proposes using dynamic programming, with the following choice of subproblems: a subproblem is specified by parameters r,s,t,u such that 1 ≤ r ≤ s ≤ m and 1 ≤ t ≤ u ≤ n. He suggests we define F(r,s,t,u) = 1 if all of the entries in the rectangle M[r..s][t..u] are zero (i.e., if M[i][j] = 0 for all i,j that satisfy r ≤ i ≤ s and t ≤ j ≤ u), or 0 otherwise.

How many subproblems are there, in Professor Celadon's approach, as a function of m and n? It's OK to use big-O notation.

2. Professor Ecru suggests a different approach. In his approach, a subproblem is specified by parameters x,y, where 1 ≤ x ≤ m and 1 ≤ y ≤ n. He suggests we define E(x,y) to be the dimensions of the largest all-zeros subrectangle that is contained entirely within M[1..x][1..y] and that has its lower-right corner at M[x][y], or 0 if no such subrectangle exists.

How many subproblems are there, in Professor Ecru's approach, as a function of m and n? It's OK to use big-O notation.

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