We devised the following divide and conquer strategy in which we eliminate about half of the rows in each step. We "probe" the middle row (among those remaining) and find the largest element in that row by brute force. If it happens to also be a peak for the matrix, we are done! Otherwise we recursively find a peak among the elements among the rows in an "uphill" direction (eliminating the others). Below is pseudo-code describing this algorithm. 1// m: the 2d matrix // n: the matrix dimension (nxn) 3|// lowRow/hiRow: range of rows under consideration find peakB (m, n, lowRow, hiRow) { 2 if(lowRow==hiRow) { return largest entry in m[lowRow] else { 10 (lowRow + hiRow) /2; find largest entry in row r if it happens to be a peak in m return it else { if (the entry above it is larger) 11 12 13 14 15 return find_peakB (m, n, lowRow, r-1) else { 16 // entry below it must be larger return find peakB (m, n, r+1, hiRow) 17 18 } This approach has a worst case runtime of O(n log n): The recursion examines about log n rows in total and, for each such row spends O(n) time to scan it to find the max Can we improve the runtime to O(n)? We suspect an O(n)worst case runtime might be within reach. Here are some observations: While the "problem size" shrinks during recursion, the number of columns remains fixed -- and the time required to scan the "probe row" at each recursive step is also fixed. Maybe if we can find a way to shrink the time taken by the "scan" step? Columns vs. Rows: as presented, the algorithm probes and scans rows, but could have just as easily probed and scanned columns. Here's an idea: Instead of always probing and scanning the middle row in the remaining sub-matrix, we alternate probing/scanning middle rows and middle columns. The policy determining the sub-matrix is logically the same. For example, if we start with a 15x15 matrix, after one probe and scan, we have a 7x15 submatrix; then we probe and scan the middle column of this 7x15 submatrix to yield a 7x7 submatrix and so on. TODO A (10 pts): The good news: this approach which alternates horizontal and vertical "cuts" does indeed result in O(n) runtime. Your job: show that this is indeed true. TODO B (15 pts): The bad news: unfortunately, this approach is buggy! Your job: Devise a 7x7 instance of the peak finding problem on which this alternating approach fails. Walk the reader through what happens on your instance (via annotated diagrams) and why the result is incorrect. TODO C (25 pts): Devise a correct O(n) time algorithm for the peak-finding in a matrix problem. Hint: the idea of making sure the "time-to-scan" shrinks with recursion as suggested above is sound; give some thought to alternative "things" to probe/scan. We devised the following divide and conquer strategy in which we eliminate about half of the rows in each step. We "probe" the middle row (among those remaining) and find the largest element in that row by brute force. If it happens to also be a peak for the matrix, we are done! Otherwise we recursively find a peak among the elements among the rows in an "uphill" direction (eliminating the others). Below is pseudo-code describing this algorithm. 1// m: the 2d matrix // n: the matrix dimension (nxn) 3|// lowRow/hiRow: range of rows under consideration find peakB (m, n, lowRow, hiRow) { 2 if(lowRow==hiRow) { return largest entry in m[lowRow] else { 10 (lowRow + hiRow) /2; find largest entry in row r if it happens to be a peak in m return it else { if (the entry above it is larger) 11 12 13 14 15 return find_peakB (m, n, lowRow, r-1) else { 16 // entry below it must be larger return find peakB (m, n, r+1, hiRow) 17 18 } This approach has a worst case runtime of O(n log n): The recursion examines about log n rows in total and, for each such row spends O(n) time to scan it to find the max Can we improve the runtime to O(n)? We suspect an O(n)worst case runtime might be within reach. Here are some observations: While the "problem size" shrinks during recursion, the number of columns remains fixed -- and the time required to scan the "probe row" at each recursive step is also fixed. Maybe if we can find a way to shrink the time taken by the "scan" step? Columns vs. Rows: as presented, the algorithm probes and scans rows, but could have just as easily probed and scanned columns. Here's an idea: Instead of always probing and scanning the middle row in the remaining sub-matrix, we alternate probing/scanning middle rows and middle columns. The policy determining the sub-matrix is logically the same. For example, if we start with a 15x15 matrix, after one probe and scan, we have a 7x15 submatrix; then we probe and scan the middle column of this 7x15 submatrix to yield a 7x7 submatrix and so on. TODO A (10 pts): The good news: this approach which alternates horizontal and vertical "cuts" does indeed result in O(n) runtime. Your job: show that this is indeed true. TODO B (15 pts): The bad news: unfortunately, this approach is buggy! Your job: Devise a 7x7 instance of the peak finding problem on which this alternating approach fails. Walk the reader through what happens on your instance (via annotated diagrams) and why the result is incorrect. TODO C (25 pts): Devise a correct O(n) time algorithm for the peak-finding in a matrix problem. Hint: the idea of making sure the "time-to-scan" shrinks with recursion as suggested above is sound; give some thought to alternative "things" to probe/scan
