Posts Tagged ‘classnote’
27
Jan

Class Note for CS445 on Jan 27, 2009

No commentscomputer scienceJanuary 27th, 2009Sumin

Announcements

Optional discussion section meets on Wednesday, 7-8pm at FCS 101

Largest Empty Rectangle Problem

Divide and conquer

function DivideAndConquer(A, m, n) begin
    PrecomputeLeftRuns(...)
    PrecomputeRightRuns(...)
    return DivAndConq(A, m, 1, n, L, R)
end
DevAndConq()

T(m, n) = 2T(m, n/2) + \Theta(m^2) = \Theta(m^2n)

PrecomputeLeftRuns() + PrecomputeRightRus()

\Theta(mn) + \Theta(m^2n)

Total number of rectangles
[m 2]          * [n 2]           = m*(m-1)/2 * n*(n-1)/2
(pair of rows)   (pair of cols)  theta(m^2)  theta(n^2)

To sum up, for Largest Empty Rectangle, we’ve seen following algorithms:

  • Exhaustive search (\Theta(m^3n^3) time)
  • [Optimized exhaustive search (\Theta(m^2n^2) time)]
  • Divide and conquer (\Theta(m^2n) time)
  • [Dynamic programming (\Theta(m^2n) time)]
  • [Amortization (\Theta(mn) time)] (optimal)

,

20
Jan

Class Note for SC445 on Jan 20, 2009

No commentscomputer scienceJanuary 20th, 2009Sumin

Announcements

  • Office hours posted on the course webpage: M-F
  • Optional discussion section will be on Wednesdays at 7-8pm

Problem (Largest Monochromatic Rectangle)

Given an m*n boolean array A[1:m, 1:n] of zeroes and ones, find a subarray A[i:k, j:l] that contains only zeros.

Exhaustive Search (examine all possibilities; pick the best one)

function exhaustive(A, m, n) begin * returns the area of the largest solution
a := 0
for i := 1 to m do
for j := 1 to n do
for k := i to m do
for l := j to n do begin
scan A[i:k, j:l]
if it contains only zeroes then
a := max{a, (k-i+1)*(l-j+1)}
end (for)

return a
end (function)
  • (a) scan – a := max{}
  • (b) for l:= j to n
  • (c) for k := i to m
  • (d) for j := 1 to n
  • (e) for i := 1 to m

Analysis

  • (a) \Theta((k-i)(l-j))

  • (b) \displaystyle \sum_{j=l}^n\Theta((k-i)(l-j))\\ = \Theta(\sum_{j=l}^n (k-i)(l-j))\\ = \Theta((k-i)\sum_{j=l}^n(l-j))\\ = \Theta((k-i)\sum_{x=0}^{n-j}x)\\ = \Theta((k-i)\Theta(n-j)^2)\\ = \Theta((k-i)(n-j)^2)

  • (c) \displaystyle \sum_{i=k}^m\Theta((k-i)(n-j)^2)\\ = \Theta(\sum_{i=k}^m(k-i)(n-j)^2)\\ = \Theta((n-j)^2 \sum_{i=k}^m(k-i))\\ = \Theta((n-j)^2 \sum_{x=0}^{m-1}x)

  • (d) \Theta((m-i)^2 n^3)

  • (e) \Theta(m^3 n^3) : time for exhaustive search without any optimization

Notations and Formulas

  • \Theta(f(n)) upper- and lower-bounded by constant times f(n)
  • O(f(n)) upper-bounded by constant times f(n)

  • \Omega(f(n)) lower-bounded by constant times f(n)

  • \sum \Theta(f(i)) = \Theta(\sum f(i)) (almost always)

  • \displaystyle \sum_{i=1}^n i^k = \Theta(n^{k+1})

Divide and Conquer

Cut the input array vertically at the middle column. Then the optimal rectangle falls into three cases:

  1. It lies strictly in left half. (recurse)
  2. It lies strictly in right half. (recurse)
  3. It spans the middle. (some work to do)

If we cut it at the middle column, it breaks into a left rectangle that ends at the middle column and is optimal, and a right rectangle that starts at the middle column and is optimal. (where the start and end rows i and k are fixed -> new subproblem!)

,