CS 176, Introduction to Computer Science II

Summer 2001 - Lab Test 2

Note: the phrase "the square at M[x, y]" should be read as an abbreviation for the phrase "the square area of uniform value having M[x, y] as its upper-left corner element".

The design test answer gave an algorithm for finding the largest square area of uniform value in an m-by-n matrix. This algorithm works, but is not as efficient as it could be. In particular, it may

  1. check more matrix elements than necessary. If the size of the currently largest square area is s, then it isn't necessary to find the largest square at M[x, y] if M[x, y] is within s elements of the (right or bottom) edge of the matrix.
    the margin of safety
    For example, if the size of the currently largest square area is 3, then it doesn't make sense to check M[m - 2, n - 2] because the largest square at M[m - 2, n - 2] can have size of at most 2.

  2. Take too long to find the largest square at some matrix element. If the the largest square at M[x, y] has size s then the largest square at M[x + 1, y + 1] must have size at least s - 1 (assume that s > 1).
    one square area in another
    For example if the largest square at M[2, 3] has size 5, then the largest square at M[3, 4] must have size at least 4, and it isn't necessary to look for squares of size 1, 2, or 3.
For this lab test you are to

  1. Implement the algorithm for finding the largest square area of uniform values in a m-by-n matrix. Your implementation should have the prototype 
    square find_largest_square(const int [25][25], int m, int n);
    where square is the structure 
    struct square {
  int upper_left_x, upper_left_y, size;
  };

  2. Modify your implementation to include the two optimizations described above.
You'll may need an auxiliary data structure to keep track of square sizes for the second optimization. You may assume that both m and n will be non-negative values no greater than 25.

Submit your test files using the command

/export/home/us/csfac/cs176-summer2001/bin/submit-lab-test your-files-here

where your-files-here are a list of the source files you've written for the test (your shell may let you abbreviate the command as ~csfac/cs176-summer2001/bin/submit-lab-test). You should get an e-mail response back in a few minutes. submit-lab-test is available from any linux system.

Make sure you submit something by the deadline. Unlike your programming assignments, you will not be able to submit you lab test after the 12:15 p.m. deadline.

This page last modified on 13 July 2001.