October 15th, 2014

Classwork:
Previous assignments discussions in class and Classroom Salon.

Homework:
Local minimum of a matrix. Given an N-by-N array a[] of N^2 distinct integers, design an algorithm that runs in time proportional to N to find a local minimum: a pair of indices i and j such that a[i][j] < a[i+1][j], a[i][j] < a[i][j+1], a[i][j] < a[i-1][j], and a[i][j] < a[i][j-1]. The running time of your program should be proportional to N in the worst case.