CSE131 Module 3: Iteration

Goals

By the end of this lab, you should...


Practice Problems

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:

  1. Write an iterative procedure expt with the following specification. Use repeated multiplication. Do not use the built-in 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
    

  2. Write an iterative procedure harmonicSum with the following specification.
    PARAMETERS:   a positive integer, n
    RETURN VALUE: the sum 1 + 1/2 + 1/3 + ... + 1/(n-1) + 1/n
    

  3. Write an iterative procedure called geometricSum with the following specification.
    PARAMETERS:   a non-negative integer, k
    RETURN VALUE: the sum 1 + 1/2 + 1/4 + 1/8 + ... + 1/(2^k)
    

  4. 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
    

  5. Write an iterative procedure sumDownBy2 with the following specification.
    PARAMETERS:   a positive integer n
    RETURN VALUE: the sum of the positive integers n + (n-2) + (n-4) + ...
    EXAMPLES:     sumDownBy2(7) is 7+5+3+1 = 16
                  sumDownBy2(8) is 8+6+4+2 = 20
    

  6. 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
    

  7. 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
    


Downloads

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.


Project: Manipulating an Image Raster

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.

  1. Write a method that flips the image horizontally. (That is, after your method runs, the second image should be the left-to-right mirror image of the first image.)

  2. Write a method that flips the image vertically. (That is, after your method runs, the second image should be the top-to-bottom mirror image of the first image.)

  3. 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.)

  4. 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.)

  5. 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.

  6. 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.


Optional Extension 1: Loop Invariants

The loop invariants optional extension is quiz-based. See the directions for the practice problems to know how to prepare.


Optional Extension 2: Digital filtering of images

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 top-down 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.
  1. cover-page.txt -- Be sure to fill in all information.
  2. RasterTool.java -- Remember to complete the header information at the top.

Kenneth J. Goldman