CSE131 Module 3: Iteration
Goals
By the end of this lab, you should...
 know how to use loops to design and implement iterative methods,
 be able to use iteration to manipulate the pixels of an image raster, and
 (optionally) how to use loop invariants to reason about iterative computations.
Expect exercises like these on the quiz.
There will be a help session covering these exercises on Wednesday at 10:00am in the
Steinberg 105
lecture hall.
You will benefit most by doing the exercises before you
look at the solutions or attend
the Wednesday help session when they will be discussed.
Directions:
In Lab 2, you wrote recursive procedures to implement several
arithmetic functions. In these practice problems, you will implement
similar functions using iteration (loops).
Provide an iterative implementation for each of the following specifications.
If you are planning to complete the optional extension on loop invariants for
this module, you should prepare by additionally:
 stating the loop invariant(s) for the computation, and
 showing (informally) that the termination condition and the loop
invariant imply that the correct result will be produced.
 Write an iterative procedure
expt
with the following specification. Use repeated multiplication.
Do not use the builtin exponentiation method.
PARAMETERS: integers n and k, with k >= 0
RETURN VALUE: the value of n to the power k
EXAMPLES: expt(3,2) is 9
expt(5,0) is 1
expt(2,5) is 32
 Write an iterative procedure
harmonicSum
with the following specification.
PARAMETERS: a positive integer, n
RETURN VALUE: the sum 1 + 1/2 + 1/3 + ... + 1/(n1) + 1/n
 Write an iterative procedure called
geometricSum
with the following specification.
PARAMETERS: a nonnegative integer, k
RETURN VALUE: the sum 1 + 1/2 + 1/4 + 1/8 + ... + 1/(2^k)
 Write an iterative procedure
mult
with the following specification. Use repeated addition.
Do not use the multiplication operator.
PARAMETERS: integers j and k
RETURN VALUE: the product j*k
 Write an iterative procedure
sumDownBy2
with the following specification.
PARAMETERS: a positive integer n
RETURN VALUE: the sum of the positive integers n + (n2) + (n4) + ...
EXAMPLES: sumDownBy2(7) is 7+5+3+1 = 16
sumDownBy2(8) is 8+6+4+2 = 20
 Write an iterative procedure
sumOdd1toN
with the following specification.
PARAMETERS: a positive integer n
RETURN VALUE: the sum of all the odd integers between 1 and n, inclusive
EXAMPLES: sumOdd1toN(7) is 1+3+5+7 = 16
sumOdd1toN(8) is 1+3+5+7 = 16
sumOdd1toN(1) is 1

The least common multiple (LCM) of two numbers is the smallest number that
is a multiple of both.
Write an iterative procedure
lcm
with the following specification.
PARAMETERS: positive integers j and k
RETURN VALUE: the least common multiple (LCM) of j and k
EXAMPLES: lcm(3,5) is 15
lcm(6,8) is 24
Download lab3.zip and import it into your CSE131 project in Eclipse.
Note that this zip file contains an updated version of yops (and an image of Brookings again just in case you
don't already have it). When you do the import, click "yes to all" to overwrite the old files.
Directions: In the provided file RasterTool.java, implement the
following methods. Your methods will use iteration (either while loops or forloops) to operate on the pixels of an image raster.
Unless otherwise noted, all of the methods take two parameters of
type Image and all have a void return type.
Each method should read pixel values from the first image and write pixels
of the second image. (In general, these methods will end up
writing all of the pixels of the second image.)
Before writing these methods, review the YOPS documentation for tools that
operate on images, and also look at the Image class documentation for methods
that read and write pixels, as well as methods for getting the width and height of an image.
 Write a method that flips the image horizontally. (That is, after your method runs, the second image should be the lefttoright mirror image of the first image.)
 Write a method that flips the image vertically. (That is, after your method runs, the second image should be the toptobottom mirror image of the first image.)
 Write a method that flips the left half of the image horizontally. (That is, after your method runs, the left half of the second image should be same as the first, but the right half of the second image should be the mirror of the left half.)
 Write a method that flips the bottom half of the image vertically. (That is, after your method runs, the bottom half of the second image should be same as the first, but the top half of the second image should be the mirror of the bottom half.)
 This method takes a single image as a parameter. It should create a color gradient in the image by replacing every color, where the amount of red in each pixel increases gradually from 0 at the left edge of the image, to 255 at the right edge of the image. Similarly, the amount of green in each pixel increases gradually from 0 at the top edge of the image, to 255 at the bottom edge of the image. Finally, the amount of blue in every pixel should be 128. So, each pixel will have a different color depending on its position. For example, the pixel at the top left will have red=0, green=0, and blue=128. The pixel about 1/4 of the way down on the right edge will have red=255, green=64, and blue=128. Start by writing expressions for the amount of red and green in each pixel, given the x and y position of that pixel and the width and height of the image.
 An edge in an image is a place where neighboring pixels are of a significantly different color.
Write a method that finds edges in an image using a simple algorithm that checks the neighboring pixels. For each pixel, consider its color in comparison to the four pixels above, below, left, and right.
If any of those four are significantly different from the pixel you are considering, then color the corresponding pixel in the second image black. Otherwise, color the pixel in the second image white. That way, the resulting image will have outlines for the edges.
Do not process the outermost pixels of the image, since you won't have pixels to compare on all sides.
As a starting point,
consider pixels to be significantly different if they differ in each of the color components by at least 50, but feel free to
fiddle with this criterion to get better edge detection.
It is strongly recommended that you break up your implementation into two or more methods. For example, one method might be responsible for deciding if a given pixel is an edge pixel (by comparing it to its neighbors).
Do not expect the output to be exact, but you should see the general shape of the building and the people, etc. There will be a lot of stray pixels, though. There are much more sophisticated algorithms that do a better job of detecting edges. You can try to improve on this basic algorithm if you want.
The loop invariants optional extension is quizbased. See the directions for the practice problems to know how to prepare.
A two dimensional digital filter is a square array of filter
coefficients. It is used to compute a new value for each pixel of an
image by taking into account the values of the neighboring pixels,
using a weighted average. Applying a filter to an image can acheive a
smoothing effect, softening the overall image by blurring the pixels
together. In the provided file, there is an array of filter
coefficients for a 3x3 filter. Your job is to write a method that
takes in two Image objects as parameters, applies the filter to every
pixel in the first image (except the pixels along the outer border of
the image) and puts the result in the second image. Conceptually, to
compute the pixel color for the resulting image, think about centering
the 3x3 filter over a pixel (x,y) of the first image. In other words,
the 3x3 filter will be (conceptually) laying on top of a region of 9
pixels, with (x,y) at its center. You will multiply each filter
coefficient by the corresponding pixel in the image, and sum these
results to produce the weighted average of the center pixel and its
neighbors. You'll put the result in the pixel in the second
image. Then, you'll "slide" the filter over to be centered on the next
pixel. This pdf
file illustrates an example of computing the value one pixel. Of
course, you won't write out all the terms, but instead will write
nested loops to do the computation.
Because each pixel really has three components, you'll actually need
to do this for each color component (red, green, and blue) and then
call the Color constructor to create the new color for the resulting
image. If the sum exceeds 255, just make that component be 255.
(Recommendation: Split up the work into several methods using topdown
design.)
Test your filter in YOPS. The resulting image should be less "sharp"
that the original. To apply the filter again, you can select
"reverse" from the YOPS menu, and then select your method again to
operate on the right panel to produce a new image on the left. Then,
you can turn off "reverse" and go left to right again. By going back
and forth like this, you can see the effect of applying the filter
repeatedly to the same image. The image should be recognizable, but
get blurrier each time.
What To Turn In:
Follow these submission instructions
to turn in the following files and demonstrate your running program
for a TA.
 coverpage.txt  Be sure to fill in all information.
 RasterTool.java  Remember to complete the header information at the top.
Kenneth J. Goldman