Frequently Asked Questions (General)

How do I manipulate images in Java? Use our Picture data type (which is part of algs4.jar) and Java’s java.awt.Color data type. and are example clients.

I noticed that the Picture API has a method to change the origin (0, 0) from the upper left to the lower left. Can I assume (0, 0) is the upper left pixel? Yes (and you should not call this method).

Frequently Asked Questions (SeamCarver)

Must the arguments to removeHorizontalSeam() and removeVerticalSeam() be minimum energy seams? No. Each method should work for any valid seam (and throw an exception for any invalid one).

The SeamCarver data type is mutable. Must I still defensively copy of the Picture objects? A data type should not have side effects (unless they are specified in the API). It should behave properly as prescribed even if the client mutates the Picture object passed to the constructor or returned from the picture() method. As a result, you might need to make defensive copies of any Picture objects that you either take as input or return as output.

Can I use dynamic programming? Yes, though, in this context, dynamic programming is equivalent to the topological sort algorithm for finding shortest paths in DAGs.

My program is using recursion to find the shortest energy path. Is this okay? You should not need recursion. Note that the underlying DAG has such special structure that you don’t need to compute its topological order explicitly.

My program seems to be really slow. Any advice? We recommend that you implement the first four of these optimizations, but you can improve performance further my implementing some of the later ones.

How much memory can my SeamCarver object use as a function of W and H? A Picture objects uses ~ 4W H bytes of memory—a single 32-bit int per pixel. Unless you are optimizing your program by updating only the energy values that change after removing a seam, you should not need to maintain the energy values in an instance variable. Similarly, the distTo[][] and edgeTo[][] arrays should be local variables, not instance variables. For reference, a Color object consumes 48 bytes of memory.


Clients.  You may use the following client programs to test and debug your code.

Sample input files.   The zip file contains the client programs above along with some sample image files. You can also use your own image files for testing and entertainment.

Possible Progress Steps

These are purely suggestions for how you might make progress. You do not have to follow these steps.

  1. Start by writing the constructor as well as picture(), width() and height(). These should be very easy.

  2. From there, write energy(). Calculating Δx2 and Δy2 are very similar. Using two private methods will keep your code simple. To test that your code works, use the client PrintEnergy described in the testing section above.

  3. To write findVerticalSeam(), you will want to first make sure you understand the topologial sort algorithm for computing a shortest path in a DAG. Do not create an EdgeWeightedDigraph. Instead construct a 2d energy array using the energy() method that you have already written. Your algorithm can traverse this matrix treating some select entries as reachable from (x, y) to calculate where the seam is located. To test that your code works, use the client PrintSeams described in the testing section above.

  4. To write findHorizontalSeam(), transpose the image, call findVerticalSeam(), and transpose it back.

  5. Now implement removeVerticalSeam(). Typically, this method will be called with the output of findVerticalSeam(), but be sure that they work for any seam. To test that your code words, use the client ResizeDemo described in the testing section above.

  6. To write removeHorizontalSeam(), transpose the image, call removeVerticalSeam(), and transpose it back.