University of Washington, CSE 142

Lab 5: Strings, cumulative algorithms, while loops, fencepost loops

Except where otherwise noted, the contents of this document are Copyright 2013 Stuart Reges and Marty Stepp.

lab document created by Marty Stepp, Stuart Reges and Whitaker Brand

Basic lab instructions

• Mouse over highlighted words if you're not sure what they mean!
• Talk to your classmates for help.
• You may want to bring your textbook to future labs to look up syntax and examples.
• Stuck? Confused? Have a question? Ask a TA for help, or look at the book or past lecture slides.
• Complete as much of the lab as you can within the allotted time. You don't need to keep working on these exercises after you leave.
• Feel free to complete problems in any order.
• Make sure you've signed in on the sign-in sheet before you leave!

Today's lab

Goals for today:

• use Strings to represent and manipulate text data
• practice cumulative algorithms for complex computations
• use while loops for indefinite repetition
• exposure to fencepost and sentinel loop patterns
• Where you see this icon, you can click it to check the problem in Practice-It!

Cumulative algorithms

A cumulative algorithm involves incrementally accumulating a value by repeatedly adding, multiplying, dividing, etc., while storing the result in a variable.

Key aspects of a cumulative algorithm: A loop, and a variable declared outside the loop whose value is modified inside the loop.

int sum = 0;                // safe default value, 0 doesn't affect a sum
for (int i = 1; i <= 100; i++) {
    sum = sum + i;
}
System.out.println(sum);    // 5050

Exercise : repl

Write a method named repl that accepts a String and a number of repetitions as parameters and returns the String concatenated that many times. For example, the call

repl("hello", 3)

"hellohellohello"

Exercise : longestName

Write a method named longestName that reads names typed by the user and prints the longest name (the name that contains the most characters) in the format shown below. Your method should accept a console Scanner and an integer n as parameters and should then prompt for n names.

A sample execution of the call longestName(console, 4) might look like the following:

name #1? roy
name #2? DANE
name #3? sTeFaNiE
name #4? Erik
Stefanie's name is longest

Try to solve this problem in Practice-It: click on the check-mark above!

Exercise : Getting textbook code files

In this exercise we will download a program from the textbook for a debugging exercise.

1. Go to the course web page and click the Textbook sidebar link.
2. Find the section labeled Code Files and click the "code files" link. It's kind of hard to see, but in the sentence "You can access a full set of..." you'll see the text "code files" and you'll want to click on that.
3. Click on the 4ed link. This will bring you to a listing of all chapters. Click the link for ch04.
4. Download and save Hailstone.java. Right-click the file name and choose the option to Save the Link in the folder you have been using for lab work.
5. Compile and run Hailstone.java in jGRASP.

Exercise : jGRASP Debugger

We are going to practice using the jGRASP debugger with Hailstone.java. This program computes a sequence of integers called a hailstone sequence. (This is related to an unsolved problem in mathematics known as the Collatz Conjecture.)

• Recall: To Set a breakpoint, move your cursor to the beginning of the desired line until you see a stop-sign icon and click.
• Recall: To run a program in debug mode, click the debug icon (looks like a ladybug).
• Recall: To resume a stopped program, press the top-left play or step buttons.

continued on the next slide...

Exercise - Values of value

• For this exercise you will trace the first call: printHailstoneMaxMin(7, 10);
• Set a breakpoint that will allow you to determine the first several distinct values of the variable value as the loop executes.

11

34

17

52

continued on the next slide...

Exercise - Values of min

• Now you will trace the second call: printHailstoneMaxMin(7, 20);
• Clear your previous breakpoint by clicking on it a second time, then set a new breakpoint for the second method call, and resume execution.
• Use your new breakpoint to determine the first several distinct values of min during the second call. You may have to step through several iterations until you get to a distinct value of min.

5

4

2

1

Fencepost Loops

A fencepost loop is a common algorithmic pattern where you want to perform N tasks with N-1 things between them. It's like a fence with N posts with N-1 wires between the posts.

To achieve this, place one "post" outside your loop, then alternate between "wires" and "posts" inside the loop.

Example:

System.out.print(1);                 // |==|==|==|==| fence
for (int i = 2; i <= 5; i++) {
    System.out.print(".." + i);      // 1..2..3..4..5
}

Exercise : printLetters

R-a-b-b-i-t

Exercise : printFactors

Write a method called printFactors that accepts an integer as its parameter and that prints the factors of that number, separated by the word "and". Recall that a factor is a number that goes evenly into another number. For example, the call printFactors(24) should print the following output:

1 and 2 and 3 and 4 and 6 and 8 and 12 and 24

You may assume that the parameter value passed is greater than 0.

while Loops

for loops are fantastic for when we know how many times we want to repeat something. But sometimes we won't know how many times we'll want to repeat something in advance! while loops repeat indefinitely while a given condition is true.

while (test) {
    statement(s);
}

Example:

int num = 1;
while (num < 5) {
    System.out.print(num + " ");     // output: 1 2 3 4
    num++;
}

Exercise : while loop basics

Consider the following loop.

int x = 1;
System.out.print(x);
while (x < 100) {
    x = x + x;
    System.out.print(", " + x);
}

Exercise : while loop mystery

Fill in the boxes at right with the output produced by each method call.

public static void mystery(int x) {
    int y = 1;
    int z = 0;
    while (2 * y <= x) {
        y = y * 2;
        z++;
    }
    System.out.println(y + " " + z);
}

1 0

4 2

16 4

32 5

64 6

Exercise : while loop mystery

Fill in the boxes at right with the output produced by each method call.

public static void mystery2(int x, int y) {
    int z = 0;
    while (x % y != 0) {
        x = x / y;
        z++;
        System.out.print(x + ", ");
    }

    System.out.println(z);
}

12, 1

0

1034, 103, 10, 3

31, 15, 7, 3, 1, 0, 6

Exercise : digitSum

Write a method named digitSum that accepts an integer as a parameter and returns the sum of the digits of that number. For example, the call digitSum(29107) returns 2+9+1+0+7 or 19. For negative numbers, return the same value that would result if the number were positive. For example, digitSum(-456) returns 4+5+6 or 15. The call digitSum(0) returns 0.

(Hint: This is a cumulative algorithm. To extract a digit from a number, use / 10 and % 10 operations.)

If you finish them all...

If you finish all the exercises, try out our Practice-It web tool. It lets you solve Java problems from our Building Java Programs textbook.

You can view an exercise, type a solution, and submit it to see if you have solved it correctly.

Choose some problems from the book and try to solve them!