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:

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!

ELECTRONIC SUBMISSION: Submit your final version of all your programs, your Makefile and any other files required to run your program as: 
~/bin/submit -c=si335 -p=proj02 file1 file2 ... filek
You need to have your Makefile be among that list. The submit system will test whether you have the Makefile with all of the required targets. So look at the system's evaluation to ensure the submission is valid. It won't test whether your programs get correct results. That's up to you!

Guidelines on Working Together on Programs

The algorithm design and implementation effort is expected to be shared amongst the whole group. You all need to be in on the whole thing and conversant with the whole thing. You are not splitting up the work, you are all doing it together with the advantages of having many eyes and many ideas.
  1. It is expected that your whole group works together and is intimately familiar with all of your submitted code. I will choose team members at random to explain code to me, just as I choose team members at random to present solutions to non-propgramming problems. Do your coding together, at least in pairs if not the whole group, rather than working on tasks separately.
  2. Your group is responsible for ensuring that your programs function correctly! If your greedy implementation doesn't produce the exact, correct greedy route, you'll lose major points. If your optimum implementation doesn't produce optimum routes, you'll lose major points. So test, test, test!
  3. In line with the previous point, I strongly suggest that you have a group-member go off early on and write a program that verifies answers, i.e. that takes an input file and string defining a route and verifies that the route makes it all the way to the last column without leaving the grid, and counts how many targets get picked up along the way.
  4. Also in line with the earlier points on testing, I strongly suggest that you work out some examples by hand so that you have something with known correct answers to test with.