## Executive Summary: Optimum Route

Important: This is a combination Project 2 and Problem Set 3. That means that it is to be done as a group. The rules for the assignment follow those for the Problem Sets rather than programming projects, which is to say that there is to be no discussion or exchange of ideas with anyone outside your group. Discussion within the group is, of course, not only OK, but kind of the whole point!

 Example: route USDDDSSUUSD on 7x12 grid
Consider an $N_r \times N_c$ grid of points, where $N_r$ is odd. [Note: we will address points using row,col coordinates in which rows are numbered $0, 1, \ldots, N_r-1$ top-to-bottom, and columns are numbered $0, 1, \ldots, N_c-1$ left-to-right.] A route through this grid is a sequence of moves, starting from point $(\text{row}=\lfloor N_r/2 \rfloor, \text{col}=0)$, that are either one step to the right, one step right-and-up, or one step right-and-down. These moves must end at column $N_c-1$, and must never go outside of the grid. A route is represented as a length $N_c-1$ string of S's, U's and D's, where S means step right, U means right-and-up, and D means right-and-down. An example of a route on a 7x12 grid is shown to the right.

We will assign some subset of the grid points to be "targets", and the value of a route will be the number of targets it hits, i.e. the number of target points on the route. Your ultimate goal is to deliver a program that finds optimum routes, meaning routes of maximum value, and does so as efficiently as possible. This program takes as input a file with first row is $N_r\ \ N_c$, and in which each subsequent row lists the row col position of target point on the $N_r \times N_c$ grid. The targets don't come in any particular order, but there will never be duplicates. The program will output an optimum route given, of course, as a $N_c-1$ length string of of S's, U's and D's.

 Example: optimum route UDDSUUUUUUDDDDSDDDS on 11x20 grid (in01.txt)

These problems can get quite big. And we'd like to have algorithms that are efficient even for huge values of $N_r$ and $N_c$. I will say, though, that I'm more interested in cases where the number of targets is much smaller than $N_r \cdot N_c$.

## What you get from me

I'm giving you two helper programs:
• createInput.jar: This program creates input files. It takes three arguments, Nr, Nc and N. Nr is the number of rows in the grid (it must be odd). Nc is the number of columns in the grid. N is the number of targets (it cannot exceed 50% of the number of grid cells).
~/$java -jar createInput.jar 5 8 3 > tmp1 ~/$ cat tmp1
5 8 ← means 5 rows and 8 columns in the grid
3 6
1 1
1 4
• rplot.jar: This program takes a problem input file as an argument and reads a route string from standard input, plotting the route on the grid. Sometimes it's helpful to see something like this rather than look at text dumps.  file: tmp1 command: echo USSSDDS | java -jar rplot.jar tmp1 5 8 3 6 1 1 1 4

## Problem 1: A Greedy Algorithm

Solving our route planning problem is easy to phrase as a sequence of "moves", because the route itself is simply a sequence of moves! So, we can consider greedy algorithms that simply have to choose which move to make next: S, U or D. Here's one proposal for a greedy choice:
1. if there are no reachable targets to the right of our current position, choose move = S, otherwise ...
• In the nearest column to the right of our current position that has reachable targets, choose the target from that column whose row position is nearest the center row. If there is a tie, chose from amongst those two targets the one in the higher row (smaller row index)
• If the chosen target's row position is above our current position choose move = U, below our current position choose move = D, otherwise choose move = S.

Part 1.a: Show that this greedy choice does not always produce optimum routes.

Part 1.b: Write down a complete algorithm that realizes this greedy choice. This means specifying things sufficiently that it can be analyzed and implemented.

Part 1.c: Analyze the algorithm you described in Part1.b. It's sufficient to give a good upper bound on the worst-case running time.

Part 1.d: Implement your greedy algorithm. Your implementation should take the input file name as a command line argument, and its output should consist solely of the route given as a single string. Your implementation will compete against the algorithms of other groups. The group with the best performing program will be rewarded.

## Problem 2: An Algorithm for the Value of an Optimum Route

Your greedy algorithm ought to be fast, even for large inputs. However, it's not guaraunteed to give optimum routes. Of course it's hard to know how often the greedy algorithm fails to find an optimum route, so it would be nice to know the value of the optimum route so we could see how far off the mark the greedy result really is.

Part 2.a: Give a (not necessarily efficient) algorithm to compute the value of the optimum route. Note, I'm not asking you to exhibit an optimum route, just tell me how many targets an optimum route would hit.

Part 2.b: Implement your algorithm from Part 2.a. It should be able to tell me optimum route values for inputs of modest size - e.g. $N_r = 7, N_c = 16, N = 12$.

## Problem 3: An Algorithm That Finds Optimum Routes

Now you have to provide an exact algorithm that produces optimum routes. Moreover, now I do care about efficiency!

Part 3.a: Give an algorithm that produces routes that are guaranteed to be optimum. The algorithm should be efficient! The larger the grid size it can handle the better!

Part 3.b: Analyze your algorithm from Part 3.a. It's sufficient to give a good upper bound on the worst-case running time.

Part 3.c: Implement your algorithm from Part 3.a. Once again, the larger the grid size it can handle the better! Your program will compete against the programs of other groups. The group with the best performing program will be rewarded.

## Submission and Presentation Instructions

Your presentation (and code demo) must be completed by 12 April. Presentation slots will be available on 10, 11 and 12 April. Code must be submitted via the submit system prior to your presentation.

All files necesary to build and run your programs must be submitted. This must include a Makefile with all the targets you see in my sample Makefile. I will run your programs like this:

~/$make build g++ -O6 -o gog solG.cpp g++ -O6 -o gov solA.cpp g++ -O6 -o goo solB.cpp ~/$ java -jar ../createInput.jar 11 16 30 > tmp
~/(make comm-greedy) tmp
USUSDSDDSDSSUSU
~/(make comm-optval) tmp
9
~/(make comm-opt) tmp
DDSDDDUSUUSSSUU
~/\$ make users
wcbrown

So you need to make sure that what you produce works when I run it this way! Test your makefile! In fact, keep it up to date and use it as you develop things!

~/bin/submit -c=si335 -p=proj02 file1 file2 ... filek