University of Washington, CSE 142

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

lab document created by Marty Stepp, Stuart Reges, Whitaker Brand and Hélène Martin

Basic lab instructions

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.
Complete as many problems as you can within the allotted time. You don't need to keep working on these exercises after you leave the lab.
Feel free to complete problems in any order.
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

Method name	Description
`charAt(index)`	character at given index
`indexOf(str)`	index where the start of the given `String` appears in this string (-1 if not found)
`length()`	number of characters in this `String`
`replace(str1, str2)`	a new string with all occurrences of `str1` changed to `str2`
`substring(index1, index2)` or `substring(index1)`	the characters in this string from `index1` (inclusive) to `index2` (exclusive); if `index2` is omitted, grabs till end of string
`toLowerCase()`	a new string with all lowercase letters
`toUpperCase()`	a new string with all uppercase letters

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";

`str1.length()`		13
`str1.charAt(7)`		'a'
`str2.charAt(0)`		'G'
`str1.indexOf("o")`		2
`str2.toUpperCase()`		"GANDALF THE GRAY"
`str1.toLowerCase().indexOf("B")`		-1
`str1.substring(4)`		"o Baggins"
`str2.substring(3, 14)`		"dalf the GR"
`str2.replace("a", "oo")`		"Goondoolf the GRAY"
`str2.replace("gray", "white")`		"Gandalf the GRAY"
`"str1".replace("r", "range")`		"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 : 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.

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 : 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.print(", " + x);
}

How many times does the code in the `while` loop execute?	7
What output is produced by the overall code?	1, 2, 4, 8, 16, 32, 64, 128

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);
}

`mystery(1);`		1 0
`mystery(6);`		4 2
`mystery(19);`		16 4
`mystery(39);`		32 5
`mystery(74);`		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);
}

`mystery2(25, 2);`		12, 1
`mystery2(32, 4);`		0
`mystery2(10345, 10);`		1034, 103, 10, 3
`mystery2(63, 2);`		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.

The `boolean` type

The boolean type represents logical values of true or false. Combine boolean expressions with logical operators && (and), || (or), and ! (not).

Example:

boolean test1 = 7 < 10;            // true
boolean test2 = (1 == 2);          // false
if ((test1 || test2) && 2 + 2 != 5) {
    System.out.print("hello");     // output: hello
}

`String` methods with `boolean` results

Method name	Description
`string.equals(string)`	whether the two strings are identical
`string.equalsIgnoreCase(string)`	whether the two strings are identical, ignoring capitalization
`string.startsWith(string)`	whether this string begins with the characters of the given string
`string.endsWith(string)`	whether this string ends with the characters of the given string
`string.contains(string)`	whether the characters of the given string occur within this string

String name = "Professor Smith";
if (name.startsWith("Prof")) {
    System.out.println("When are your office hours?");
}

Exercise : Boolean Expressions

Write the result of each expression as either true or false, given the following variables.

int x = 12;
int y = 7;
int z = 28;
String s = "mid term";

`x < 14`		true
`!(x % 2 < 1)`		false
`x < y \|\| x < z`		true
`z / x < x / y * x`		true
`s.length() == y`		false
`s.toUpperCase().equals("MID TERM")`		true
`!s.equals("mid term") \|\| x * y != z`		true
`s.substring(z / x).length() > y`		false

Midterm exam review

The CSE 142 midterm exam is usually very similar to the format of the practice exams. The following kinds of problems are often found on the exam:

expressions (given an expression, write the value it produces)
parameter mystery (read code with parameters and write its output)
if/else mystery (read code with if/else statements and write its output)
while loop mystery (read code with while loops and write its output)
assertions (given a piece of code, what can we say is always / sometimes / never true?)
programming problems (write code to implement a method with specific behavior)

To solve each problem, you will need to use various concepts and syntax taught throughout the course so far, such as System.out.println, expressions, variables, parameters, return, if/else, for/while loops, Scanner, and Random. Part of the challenge is in figuring out which tools to use and how to use them together to solve the problem at hand.

Exercise : lastDigit

Write a method named lastDigit that returns the last digit of an integer. For example, lastDigit(3572) should return 2. It should work for negative numbers as well. For example, lastDigit(-947) should return 7.
Try solving this problem in Practice-It! using the link above.
(Hint: This is a short method.)

Exercise : firstDigit

Write a method named firstDigit that returns the first digit of an integer. For example, firstDigit(3572) should return 3. It should work for negative numbers as well. For example, firstDigit(-947) should return 9.
Try solving this problem in Practice-It! using the link above.
(Hint: This problem requires a loop.)

Exercise : season

Write a method named season that takes two integers as parameters representing a month and day and that returns a String indicating the season for that month and day. Assume that months are specified as an integer between 1 and 12 (1 for January, 2 for February, and so on) and that the day of the month is a number between 1 and 31.
If the date falls between 12/16 and 3/15, you should return "Winter". If the date falls between 3/16 and 6/15, you should return "Spring". If the date falls between 6/16 and 9/15, you should return "Summer". And if the date falls between 9/16 and 12/15, you should return "Fall".
Try solving this problem in Practice-It! using the link above.

Exercise : allDigitsOdd

Write a method named allDigitsOdd that returns whether every digit of a positive integer is odd. Your method should return true if the number consists entirely of odd digits and false if any of its digits are even. 0, 2, 4, 6, and 8 are even digits, and 1, 3, 5, 7, 9 are odd digits.

For example, allDigitsOdd(135319) returns true but allDigitsOdd(9145293) returns false.

Hint: You can pull apart a number into its digits using / 10 and % 10.

Exercise : hopscotch

Write a method named hopscotch that accepts an integer parameter for a number of "hops" and prints a hopscotch board of that many hops.

For example, the call hopscotch(3); would produce the following output:

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

Exercise : hasMidpoint

Write a method hasMidpoint that accepts three integers as parameters, and returns true if one of the numbers is the midpoint of the other two and returns false otherwise.

For example, the call hasMidpoint(3, 7, 5) would return true because one of the parameters (5) is the midpoint of the other two (3 and 7).

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

Exercise : Syntax errors

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

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

line 5: nextString should be next
line 9: string should be String
line 9: name should not be in quotes
line 10: Whitaker should be in quotes
line 10: cannot compare strings with ==; must use .equals
line 13: cannot call replace without specifying a string object (name)
line 14: toUppercase should be toUpperCase
line 14: name. should come before toUpperCase, not passed as a parameter to it
line 14: must say name = to store the result of toUpperCase
line 15: must say name = to store the result of substring
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");
    }
}

Exercise : before

Write a method before that takes as parameters two month/day combinations and that returns whether or not the first date comes before the second date (true if the first month/day comes before the second month/day, false if it does not). The method will take four integers as parameters that represent the two month/day combinations.

The first integer in each pair represents the month and will be a value between 1 and 12 (1 for January, 2 for February, etc, up to 12 for December). The second integer in each pair represents the day of the month (a value between 1 and 31). One date is considered to come before another if it comes earlier in the year.

Solve this problem in Practice-It by clicking on the check-mark above.

Exercise : sameDashes

Write a method sameDashes that takes two strings as parameters and that returns whether or not they have dashes in the same places (returning true if they do and returning false otherwise). For example, below are four pairs of strings of equal length that have the same pattern of dashes. Notice that the last pair has no dashes at all.

string 1:    "hi--there-you."    "-15-389"    "criminal-plan"    "abc"
string 2:    "12--(134)-7539"    "-xy-zzy"    "(206)555-1384"    "9.8"

To be considered a match, the strings must have exactly the same number of dashes in exactly the same positions. The Strings might be of different length.

Solve this problem in Practice-It by clicking on the check-mark above.

Exercise : "Boolean Zen"

This attempted solution to Self-Check 5.15 (isVowel) has several problems:

// Returns whether the given string represents a vowel:
// a, e, i, o, or u, case insensitively.
public static boolean isVowel(String s) {
    if (s == "a") {
        return true;
    } else if (s == "e") {
        return true;
    } else if (s == "i") {
        return true;
    } else if (s == "o") {
        return true;
    } else if (s == "u") {
        return true;
    } else {
        return false;
    }
}

Open Practice-It from the link above, copy/paste this code into it, then see the next slide.

Exercise - things to fix

Fix the following aspects of the code:

It has a bug related to how strings are compared.
It isn't case sensitive; it fails for uppercase vowels.
It has too many unnecessary if/else statements.
(advanced) It does not use "Boolean Zen" as described in textbook section 5.3.

Exercise - answer

public static boolean isVowel(String s) {
    s = s.toLowerCase();
    if (s.equals("a") || s.equals("e") || s.equals("i")
            || s.equals("o") || s.equals("u")) {
        return true;
    } else {
        return false;
    }
}

The above can be improved. "Boolean Zen" version:

public static boolean isVowel(String s) {
    s = s.toLowerCase();
    return s.equals("a") || s.equals("e") || s.equals("i")
           || s.equals("o") || s.equals("u");
}

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!

University of Washington, CSE 142

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

University of Washington, CSE 142

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

Basic lab instructions

Today's lab

String methods

Exercise : String expressions

Exercise : ProcessName

Exercise - code to add

Cumulative algorithms

Exercise : repl

Exercise : swapPairs

Fencepost Loops

Exercise : printFactors

while Loops

Exercise : while loop basics

Exercise : while loop mystery

Exercise : while loop mystery

Exercise : digitSum

Exercise : ProcessName2

The boolean type

String methods with boolean results

Exercise : Boolean Expressions

Midterm exam review

Exercise : lastDigit

Exercise : firstDigit

Exercise : season

Exercise : allDigitsOdd

Exercise : hopscotch

Exercise : hasMidpoint

Exercise : Syntax errors

Exercise - answer

Exercise - Corrected version

Exercise : before

Exercise : sameDashes

Exercise : "Boolean Zen"

Exercise - things to fix

Exercise - answer

If you finish them all...

`String` methods

`while` Loops

Exercise : `while` loop basics

Exercise : `while` loop mystery

Exercise : `while` loop mystery

The `boolean` type

`String` methods with `boolean` results