1. Consider the word search problem. The input to this problem consists of three integers m, n, and w, an m×n matrix of letters, and a list of w words. All of the words in the list are hidden inside the matrix of letters (forwards, backwards, up, or down, but not diagonally), and the solution to a word search consists of w ×2 array containing the row and column of the first letter of each word in the list, where the coordinates appear in the same order as the words. (If one of the words in the list does not appear in the matrix of letters, this row of the output may contain any values. If it appears more than once, you may return any of its locations.) Design an algorithm to solve the word search problem. Take care not to read past the top, bottom, left, or right of the letter matrix. Hint: you may wish to use subarray notation, like letters[a..b, c], to denote words formed by scanning the matrix letters vertically (or horizontally). 2. Prove that your algorithm for WordSearch is correct.
