University of Washington, CSE 142

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

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

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

Basic lab instructions

• We encourage you to talk to your classmates for help. You can even work on the lab with a partner if you like.
• 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.
• You probably won't finish all of the exercises. Just do as much as you can within the allotted time. You don't need to keep working on these exercises after you leave the lab.
• Before you leave today, make sure to check in with one of the TAs in the lab to get credit for your work.

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!

String methods

Exercise : String expressions

Write the results of each expression with Strings in "quotes" and characters in single quotes ('a')

//       index 0123456789012345
String str1 = "Frodo Baggins";
String str2 = "Gandalf the GRAY";

13

'a'

'G'

2

"GANDALF THE GRAY"

-1

"o Baggins"

"dalf the GR"

"Goondoolf the GRAY"

"Gandalf the GRAY"

"strange1"

Exercise : ProcessName

Copy/paste and save ProcessName.java in jGRASP, then go to the next slide.

import java.util.*;  // for Scanner

public class ProcessName {
    public static void main(String[] args) {
        Scanner console = new Scanner(System.in);
        System.out.print("Type your name: ");
        
        // your code goes here
        
        System.out.println("Your name is: " + name);
    }
}

continued on the next slide ...

Exercise - code to add

• Add code to the program so that it reads the user's first and last name (read an entire line as a single string), then prints the last name followed by a comma and the first initial. (Assume that the user types a valid name.) Example:

  Type your name: Jessica Miller
  Your name is: Miller, J.
  

• Notice that the program reads an entire line of user input, not just one word.
• Try solving this problem in Practice-It! using the link above.

Cumulative algorithms

• A cumulative algorithm is one where you incrementally accumulate a larger value by repeatedly adding, multiplying, etc., and storing the result into a variable over and over.
• Key aspect of a cumulative algorithm: A loop, and a variable declared outside the loop whose value is modified inside the loop.
• Example: Cumulative algorithm to sum the numbers 1-100:

  int sum = 0;
  for (int i = 1; i <= 100; i++) {
      sum = sum + i;
  }
  System.out.println(sum);    // 5050
  

• Some of the following problems ask you to write cumulative algorithms.

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) returns "hellohellohello". If the number of repetitions is 0 or less, an empty string is returned.
• Try solving this problem in Practice-It! using the link above.
• (Hint: This is best solved with a cumulative algorithm. Start with an empty string and build it up piece by piece.)

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 : swapPairs

• Write a method named swapPairs that accepts a String as a parameter and returns that String with each pair of adjacent letters reversed. If the String has an odd number of letters, the last letter is unchanged. For example, the call swapPairs("forget") should return "ofgrte" and the call swapPairs("hello there") should return "ehll ohtree".
• Try solving this problem in Practice-It! using the link 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.
3. 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.

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

• Write a method named printLetters that takes a String as its parameter and that prints the letters of the String, separated by commas. For example, the call of printLetters("Rabbit") should print:

  R, a, b, b, i, t
  

• (Hint: This is a fencepost problem. Remember that each String object has a length method that tells you how many characters are in the String and a charAt method that gets you individual characters of the String.)
• Try solving this problem in Practice-It! using the link above.

Exercise : printFactors

• Write a method named printFactors that accepts an integer as its parameter and uses a fencepost loop to print the factors of that number, separated by the word "and". 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.
• (Hint: This is an example of a fencepost problem.)
• Try solving this problem in Practice-It! using the link above.

while Loops

A while loop repeats indefinitely until a given condition is met.

while (test) {
    statement(s);
}

Example:

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

Exercise : while loop basics

Consider the following loop.

int x = 1;
System.out.print(x);
while (x < 100) {
    x = x + x;
    System.out.println(", " + 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.)
• Try solving this problem in Practice-It! using the link above.

Exercise : ProcessName2

Modify your previous ProcessName program so that it re-prompts until the user types a name that is at least 5 letters total in length and has at least one space in it. Example:

Type your name: Joe
Error, must be at least 5 chars with a space.
Type your name: O K!
Error, must be at least 5 chars with a space.
Type your name: what
Error, must be at least 5 chars with a space.
Type your name: Tyler Durden
Your name is: Durden, T.

• Try solving this problem in Practice-It! using the link above.

Exercise : while loop mystery

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

public static void mystery3(int x) {
    int y = 0;
    while (x % 2 == 0) {
        y++;
        x = x / 2;
    }
    System.out.println(x + " " + y);
}

19 0

21 1

3 4

5 3

1 6

Exercise : while loop mystery

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

public static void mystery4(int n) {
    int x = 1;
    int y = 2;
    while (y < n) {
        if (n % y == 0) {
            n = n / y;
            x++;
        } else {
            y++;
        }
    }
    System.out.println(x + " " + n);
}

1 2

1 5

4 3

3 7

Exercise : Syntax errors

• The following Java program has 11 errors. Can you find them all?

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

  public class StringOops { public static void main(String[] args) { Scanner console = new Scanner(System.in); System.out.print("Type your name: "); String name = console.nextString(); process(name); } public static void process(string "name") { if (name == Whitaker) { System.out.println("You must be really awesome."); } replace("a", "e"); toUppercase(name); name.substring(0, 3); System.out.println(name + " has " + name.length + " letters"); } }

• Copy and paste the code into jGrasp and see if you can fix the errors.

Exercise - answer

1. line 5: nextString should be next
2. line 9: string should be String
3. line 9: name should not be in quotes
4. line 10: Whitaker should be in quotes
5. line 10: cannot compare strings with ==; must use .equals
6. line 13: cannot call replace without specifying a string object (name)
7. line 14: toUppercase should be toUpperCase
8. line 14: name. should come before toUpperCase, not passed as a parameter to it
9. line 14: must say name = to store the result of toUpperCase
10. line 15: must say name = to store the result of substring
11. line 16: must use parentheses () when calling length

Exercise - Corrected version

public class StringOops {
    public static void main(String[] args) {
        Scanner console = new Scanner(System.in);
        System.out.print("Type your name: ");
        String name = console.next();
        process(name);
    }

    public static void process(String "name") {
        if (name.equals("Whitaker")) {
            System.out.println("You must be really awesome.");
        }
        name = name.replace("a", "e");
        name = name.toUpperCase();
        name = name.substring(0, 3);
        System.out.println(name + " has " + name.length() + " letters");
    }
}

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!