Assignment #3: Maximum Increasing Subsequence

Covers

Recursion, backtracking, java.util classes such as Lists and Sets.

Basic problem

Find the longest increasing sequence in a two-dimensional grid of numbers. A sequence is simply a series of adjacent squares. Squares may not be used twice. Example: in the following grid:

97 47 56 36 60 31 57 54 12 55 
35 57 41 13 82 80 71 93 31 62 
89 36 98 75 91 46 95 53 37 99 
25 45 26 17 15 82 80 73 96 17 
75 22 63 96 96 36 64 31 99 86 
12 80 42 74 54 14 93 17 14 55 
14 15 20 71 34 50 22 60 32 41 
90 69 44 52 54 73 20 12 55 52 
39 33 25 31 76 45 44 84 90 52 
94 35 55 24 41 63 87 93 79 24
the longest increasing sequence has length 10, consisting of entries (r,c) (row and column, starting at zero) as follows:
(5,0)	with cost 12
(6,0)	with cost 14
(6,1)	with cost 15
(6,2)	with cost 20
(7,2)	with cost 44
(7,3)	with cost 52
(7,4)	with cost 54
(6,3)	with cost 71
(5,3)	with cost 74
(4,3)	with cost 96
Note that the 96 adjacent to the 96 in the answer reported above could be substitued in the maximum increasing sequence, but both cannot be in the sequence, because the sequence msut be strictly increasing.

The Input

The input file consists of the grid of numbers. You'll need to figure out the size of the grid. Read the file into an List of Strings; the size of the List is the number of rows. Then use a StringTokenizer.

Strategy

You'll need to use recursion. Although a non-recursive solution is possible, I want a clean recursive backtracking algorithm; otherwise, no credit. I will have some hints in class. I will not answer general questions about the algorithm outside of class, so make sure you come to class and pay attention and take good notes.

What To Submit

Submit complete source code and run your program on a small grid, a large grid, and a very large grid. Your program must include code that prints the elapsed time required to solve each instance, and your output should display the elapsed time for each instance solved.