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!
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$.
~/$ 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
file: tmp1 | command: echo USSSDDS | java -jar rplot.jar tmp1 |
5 8 3 6 1 1 1 4 |
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.
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$.
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.
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 wcbrownSo 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
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!