## Navigation

## A. Preliminaries

**Due Wednesday, September 18**
You can get the skeleton files from the shared repository as usual.

## B. Lists of Lists

We've provided a new class `IntListList`

(in package `lists`

), which consists of a reference
to an `IntList`

and a reference to an `IntListList`

.
Using this class, we can form lists of lists. Very meta...

Complete the following Java function so that it performs as
indicated in its comment. The files `IntList.java`

and `IntListList.java`

in
the template contain the declarations of the classes `IntList`

and
`IntListList`

. Put your answers in a file called `Lists.java`

, for which
we've also provided a template.

```
/** Return the list of lists formed by breaking up L into "natural runs":
* that is, maximal strictly ascending sublists, in the same order as
* the original. For example, if L is (1, 3, 7, 5, 4, 6, 9, 10, 10, 11),
* then result is the four-item list ((1, 3, 7), (5), (4, 6, 9, 10),
* (10, 11)).
* Destructive: creates no new IntList items, and may modify the
* original list pointed to by L. */
static IntListList naturalRuns(IntList L) {
/* *Replace this body with the solution. */
return null;
}
```

For test-writing purposes, you may find good uses for the `IntListList`

constructor, which takes as input two-dimensional arrays.

Also don't go overboard on tests. One "normal" input and a couple of corner cases is likely enough for 61B HW purposes! Only write more tests if you think you'll either save time or learn something by writing them. If you DO want to go overboard, the Utils class provides some handy methods for doing so. You are not required to use the Utils class in any way.

## C. Array Warm-up

Complete the following Java functions (in package `arrays`

)
so that they perform as
indicated in their comments. Remember that some arrays can have zero
elements. Put your answers to this problem (all parts) in a file named
`Arrays.java`

, for which we've provided a template.

You may find `System.arraycopy`

useful for these problems, but
you are not required to use it. We've again provided a `Utils`

class,
but again you can get along just fine without using it.

```
/* 2a. */
/** Returns a new array consisting of the elements of A followed by the
* the elements of B. */
static int[] catenate(int[] A, int[] B) {
/* *Replace this body with the solution. */
return null;
}
/* 2b. */
/** Returns the array formed by removing LEN items from A,
* beginning with item #START. */
static int[] remove(int[] A, int start, int len) {
/* *Replace this body with the solution. */
return null;
}
```

## D. Seam Carving

Set aside some time before you start this. There's a solid 15-minute read ahead of you before you're ready to get started on this problem. The ideas aren't too complicated, but I've erred on the side of caution and written a really verbose step-by-step description.

Suppose you have an image and want rescale it in a way that doesn't preserve the aspect ratio, e.g. you have a widescreen movie that you'd like to view on a square screen. Two obvious choices are rescaling and cropping. However, rescaling makes everything look weird, and cropping means you lose the edge of the image.

There is an image resizing technique known as seam carving that avoids these problems. In this HW problem you'll implement the tricky part of this algorithm.

Before proceeding, watch the first 2 minutes and 30 seconds of this video so you can get a feeling for what the technique can achieve.

In this problem, you'll be completing an implementation of a partially
completed `MatrixUtils`

class that supports the rescaling of images. We've provided
code that does all the messy stuff like reading in image files and so
forth. You'll be writing the code that does the actual smart part of
the program.

Seam carving works as follows. First we start with a *W* x *H*
color image, which is really just a two-dimensional array of `Color`

objects, where each `Color`

object contains a red, green, and blue
value. The `image.Rescaler`

class calculates the "energy" of each pixel
and returns the energy of the overall image as a matrix with
*R=H* rows and *W=C* columns. The energy of a pixel
represents the importance of a pixel. Pixels with low energy (e.g.
black in a sea of other black pixels) will be considered unimportant,
whereas pixels with high energy (e.g. a white dot in a sea of black
pixels) will be worth saving.

As an example, consider the silly 4 pixel wide by 6 pixel tall image, shown below (zoomed in):

Our code converts the image into its "energy", which depends on the differences between the neighboring pixels. Suppose that a pixel at position $(c, r)$ has an RGB color value $V(c, r)$—a 3-vector of red, green, and blue intensities. Then we'll take its energy to be $$||V(c+1, r) - V(c-1,r)||^2 + ||V(c, r+1) - V(c,r-1)||^2.$$ On the boundaries (where it lacks one or more neighbors), we'll use a color value of $10^6$, and a value of $\infty$ for pixels that are off the image. (We've already written this code, so this is just FYI). The basic idea is that the more similar a pixel is to its neighbors, the lower its energy). For this image, we get:

```
1000000 1000000 1000000 1000000
1000000 75990 30003 1000000
1000000 30002 103046 1000000
1000000 29515 38273 1000000
1000000 73403 35399 1000000
1000000 1000000 1000000 1000000
```

Here, pixels with high values are ones we want to keep, and things that have low energy (like the one with energy 29,515) are relatively expendable.

Suppose we want to resize this image by making it one row shorter. To do this, we'd find the lowest energy horizontal path from any pixel in the left column to any pixel in the right column—contraining ourselves to only walking between contiguous pixels (see below for a more precise definition). As an example, the minimum energy path for the energy shown is:

1000000 1000000 1000000 *1000000* *1000000* 75990 *30003* 1000000 1000000 *30002* 103046 1000000 1000000 29515 38273 1000000 1000000 73403 35399 1000000 1000000 1000000 1000000 1000000

We'd then remove all the marked pixels, and we'd have a rescaled image that is only 5x4. It is not obvious, but the resulting rescaling algorithm does a really good job with certain types of images (which you'll be able to experiment with once you're done).

We can also use this algorithm to remove columns of images. Walking top to bottom, one minimum energy path would be:

1000000 1000000 1000000 *1000000* 1000000 75990 *30003* 1000000 1000000 *30002* 103046 1000000 1000000 *29515* 38273 1000000 1000000 73403 *35399* 1000000 1000000 1000000 1000000 *1000000*

Let's be a bit more explicit in what it means to find a contiguous path. For a vertical path, imagine that we're walking from the top to the bottom across the image, starting at any point in the top row, with the constraint that we can only walk:

- Directly down.
- Diagonally down and to the left one space.
- Diagonally down and to the right one space.

The total energy of the marked path is 1000000 for this first step, then 30003 for the next step, then 30002 for the third step, then 29515, 35399, and finally 1000000 for the final three steps. The total energy of these is six positions is 1000000+30003+30002+29515+35399+1000000=2124919 units of energy. By inspection, you should be able to convince yourself that the path we walked is the minimum among all paths that obey our constraints above.

We now define the useful term *vertical seam*: The vertical seam
is the minimum energy contiguous path from any pixel in the top row to
any pixel in the bottom row. The seam does not need to be unique.
Observe above that since the edge pixels are all energy 1000000, we
could have picked any of them.

If the example above is not satisfying to you and you insist on a
precise definition, we can define it as follows: Given an energy
matrix `int[][] e`

, then `int[] verticalSeam`

is an
array of length H such that:

`abs(verticalSeam[i] - verticalSeam[i+1]) <= 1`

`sum`

is minimized, where`sum`

is defined as: for (int r = 0; r < R; r += 1) {`int lowestTotalEnergyColumn = verticalSeam[r]; sum += e[r][lowestTotalEnergyColumn];`

}

Don't feel obligated to fully digest this definition. If you can follow the coming example, you're in great shape.

Finding such a path seems like it might involve a bunch of trial-and-error,
but we can avoid this by *accumulating* the energy
matrix. For example, if we accumulate the energy matrix
*vertically* (up to this point we were discussing horizontal
seams, we are now discussing vertical seams), we get:

1000000 1000000 1000000 1000000 2000000 1075990 1030003 2000000 2075990 1060005 1133049 2030003 2060005 1089520 1098278 2133049 2089520 1162923 1124919 2098278 2162923 2124919 2124919 2124919

If `double[][] e`

is the energy matrix, and `double[][] am`

is
the vertically accumulated energy matrix, `am[i][j]`

is defined
as the minimum total energy needed to reach i, j from any starting
position in the top row.

Let's work through how we could calculate the accumulated energy matrix. It's a pretty straightforward idea once you get it, but sorry for the moment for the wall of text needed to understand this.

First off, the accumulation of the energy matrix is 1000000 for the entire top row, because the cost to reach any top pixel from itself is 1000000.

This means that the top row of `am` is the trivial:

1000000 1000000 1000000 1000000 ??????? ??????? ??????? ??????? ??????? ??????? ??????? ??????? ??????? ??????? ??????? ??????? ??????? ??????? ??????? ??????? ??????? ??????? ??????? ???????

Let's next consider position `[1][1]`

. You'll see from the filled
in copy of `int[][] am`

that `am[1][1]`

(marked in blue)
has value 1075990. To understand where this value came from, consider
that there are three ways that you can get to `[1][1]`

, namely:

- Moving down and to the right from
`[0][0]`

, which has accumulated energy 1000000. - Moving directly down from
`[0][1]`

, which has accumulated energy 1000000. - Moving down and to the left from
`[0][2]`

, which has accumulated energy 1000000.

All of these starting locations are equally bad at a whopping 1000000
units of energy, so the total cost to reach `[1][1]`

is given by 1000000 +
75990 (the cost of including the pixel at `[1][1]`

itself).

The rest of the second row will be the same story, and we'll end up with the following top two rows:

1000000 1000000 1000000 1000000 2000000 1075990 1030003 2000000 ??????? ??????? ??????? ??????? ??????? ??????? ??????? ??????? ??????? ??????? ??????? ??????? ??????? ??????? ??????? ???????

The first entry that is really interesting is `[2][0]`

. There are two ways to get to `[2][0]`

, either:

- Moving directly down from
`[1][0]`

, which has accumulated energy 2000000. - Moving down and to the left from our old friend
`[1][1]`

, which has accumulated energy 1075990.

Obviously it'd be better to have come from `[1][1]`

, so we know that the minimum cost to
reach `[2][0]`

must be 1075990 + 1000000 (the cost of `[2][0]`

itself). And in fact, by an inductive
argument, we know that this is not just the lowest cost to reach `[2][0]`

from its two neighbors, but also from any
pixel in the top row (if you are unsatisfied or bored, try to prove
that this same way works for all pixels).

Try to figure out what `[2][1]`

should be, and then check your answer
by highlighting the following blank area after the colon with the mouse: 1060005. If you
didn't get this, then the answer is as follows. There are three
possible paths:

- Down and to the right from [1][0], which has accumulated energy 2000000.
- Down from [1][1], which has accumulated energy 1075990.
- Down and to the left from [1][2], which has accumulated energy 1030003.

Our best choice is to come from [1][2], for a total of 1030003 + 30002 = 1060005.

Following this same process, we finally arrive at the accumulated energy matrix:

1000000 1000000 1000000 1000000 2000000 1075990 1030003 2000000 2075990 1060005 1133049 2030003 2060005 1089520 1098278 2133049 2089520 1162923 1124919 2098278 2162923 2124919 2124919 2124919

Once we have the accumulated energy matrix, finding a minimum energy
path is trivial (by eye, but trickier in code)! We start by picking
the lowest energy position in the bottom row, in this case
`am[5][1]`

, `am[5][2]`

, or `am[5][3]`

are all
equally good with cumulative energies of 2124919. We then walk back up
the array, taking note of the smallest entry along the way, leading us
from 2124919 to 1124919 to 1089520 to 1060005 to 1030003 to 1000000.

This technique is an example of *dynamic programming*, which we'll be
revisiting later. It has applications from determining the degree of
difference between two texts to performing error correction on a noisy
communication line.

For this problem, you'll be required to add two methods to the `MatrixUtils`

class:

`accumulateVertical`

: Does exactly the operation described on this page.`accumulate`

: Takes a parameter that determines if we should accumulate vertically or horizontally. See the skeleton file for details.

If you want to complete the image resizing program, you'll also add two more **optional** methods: `findVerticalSeam`

and `findSeam`

.

If you complete all four methods, you'll be able to use the
`image.Rescaler`

class. Try it out on images with big empty spaces (e.g.
the provided `HJoceanSmall.jpg`

). Also try it on faces — it's super
creepy and weird. To do this, just run the program as follows:

`java -ea image.Rescaler [image filename] [num columns to remove] [num rows to remove]`

or within IntelliJ.

## E. Natural Runs in Arrays

Here's an array problem whose most natural solution involves recursion. For this problem, go back to Arrays.java and complete the final method:

```
/* 4. */
/** Returns the array of arrays formed by breaking up A into
* maximal ascending lists, without reordering.
* For example, if A is {1, 3, 7, 5, 4, 6, 9, 10}, then
* return the three-element array
* { {1, 3, 7}, {5}, {4, 6, 9, 10} }. */
static int[][] naturalRuns(int[] A) {
...
}
```

You may find the subarray command in the `Utils`

class useful.
You are not required to use the `Utils`

class in your solution.

## F. Submission

You should have completed Lists.java, ListsTest.java, Arrays.java, ArraysTest.java, MatrixUtils.java, MatrixUtilsTest.java. Submit as usual by committing, tagging, and pushing.