BC1014 Midterm Review

Please read: I made this site myself as a TA, based on the lectures, in-class code, and homework. I don't know what will be on the exam. This is my best guess at what's worth practicing, not an official study guide. If something here disagrees with the lectures or with Professor Li, go with the lectures and Professor Li.

It doesn't cover everything. Study all the lectures and homework too.
The code boxes run in a simplified Java simulator in your browser. It handles the Java used in this course, but it isn't real Java and won't catch every compile error.
The flowchart builder is a practice tool. On the exam, use the flowchart notation from class.
The exam is on paper, so practice working through problems by hand, not just running them here.

The exam is closed book, pen and paper, with no cheat sheet. It covers all lectures and homework up to the midterm.

Flowcharts: reading, tracing, and writing them
The structure of a Java file
Types: int, double, boolean, String
Integer arithmetic: /, %, and order of operations
if, else if, else
while, for, do-while, break, continue, return
Why a loop is correct and why it stops
Searching and sorting from Homework 1

The structure of a Java file

The file X.java contains one public class X. The names must match exactly, including capital letters.
Class names are CamelCase. Method names are lowerCamelCase.
Every method starts with public static.
The program starts running at public static void main(String[] args).
Compile with javac X.java, then run with java X.

Question: This program has three problems. Find all of them.

Answer

Line 3 is missing a semicolon, so the program does not compile.
The method is named Main, not main. Java is case sensitive, so there is nothing to run.
Once it runs, it prints Average: 8, not 8.33. total / 3 is 25 / 3, and dividing two ints drops the decimal part.

Fixed version. Dividing by 3.0 makes it a double division:

Flowcharts

Ovals are input and output. Rectangles are instructions. Diamonds are yes/no questions.
Every diamond has two arrows out, one labeled YES and one labeled NO.
Lists start at index 1: list[1], list[2], …, list[length].
When you trace, write down the value of every variable each time you reach a diamond.

Warm-up

Question: Trace this chart for n = 20. Then try n = 1 and n = 32. What problem does it solve?

Answer

p	p * 2	p * 2 > 20?
1	2	NO
2	4	NO
4	8	NO
8	16	NO
16	32	YES, output 16

For n = 1 it outputs 1. For n = 32 it outputs 32.

It finds the largest power of 2 that is less than or equal to n.

A chart with a list

Question: Trace this chart on list = [4, 9, 2, 11], n = 5. Then trace list = [3, 1, 4], n = 4. What problem does it solve?

Answer

[4, 9, 2, 11], n = 5
i	i > length?	list[i] > 5?
1	NO	4 > 5? NO
2	NO	9 > 5? YES, output 2

[3, 1, 4], n = 4
i	i > length?	list[i] > 4?
1	NO	3 > 4? NO
2	NO	1 > 4? NO
3	NO	4 > 4? NO
4	YES, output 0

It outputs the position of the first element that is greater than n, or 0 if there is none.

It checks i > length before it reads list[i], so it never reads past the end of the list.

From a flowchart to a Java method

This chart finds the distance between two numbers using only zero tests and subtracting 1.

The loop keeps going while i is not 0 and j is not 0. In Java, that is while (i != 0 && j != 0). When the loop ends, at least one of them is 0.

Question: Before running, what do distance(3, 8) and distance(4, 4) return? What about distance(-2, 3)?

Answer

distance(3, 8): after 3 passes, i is 0 and j is 5, so it returns 5.

distance(4, 4): both reach 0 together. i == 0 is true, so it returns j, which is 0.

distance(-2, 3) returns −5, which is wrong. Subtracting 1 from −2 moves it away from 0, so j reaches 0 first and the method returns i, which is −5. The chart only works when both inputs are at least 0. distanceAlt works for any two ints.

Types

Type	Holds	Example
`int`	whole numbers from about −2.1 billion to 2.1 billion	`42`
`double`	decimal numbers	`3.8`
`boolean`	`true` or `false`	`5 > 3`
`String`	text	`"hello"`

Other number types from class: byte, short, long (whole numbers of different sizes), float (a less precise decimal, written 3.3F), and char (one character).

Converting between types

double d = 3; is allowed. The int becomes 3.0.

int x = 3.8; does not compile. You can't put a double into an int without a cast.

A cast drops the decimal part: (int) 3.8 is 3, and (int) -3.8 is −3.

Order of operations

*, /, and % happen before + and -.

Operators at the same level go left to right. Parentheses go first.

A condition in an if or while must be a boolean. if (1) does not compile.

Integer math

int / int gives an int. The decimal part is dropped, so the result rounds toward zero: 7 / 2 is 3 and -7 / 2 is −3.
a % b is the remainder after dividing a by b. Its sign matches a: -7 % 2 is −1.
+ with a String on either side joins text instead of adding.

Question: Predict all eleven lines before running.

Answer

3 + 6 * 2 = 3 + 12 = 15
20 - 6 % 4 = 20 - 2 = 18
(20 - 6) % 4 = 14 % 4 = 2
17 / 4 = 4, and 17 % 4 = 1, because 17 = 4 × 4 + 1
4 % 17 = 4, because 17 goes into 4 zero times with 4 left over
-23 / 4 = −5. The exact answer is −5.75, and dropping the decimal gives −5, not −6.
-23 % 4 = −3, because −5 × 4 = −20, and −23 − (−20) = −3
4 + 5 + "6": left to right, 4 + 5 is 9, then 9 + "6" is "96"
"4" + 5 + 6: "4" + 5 is "45", then "45" + 6 is "456"
"4" + (5 + 6): the parentheses go first, so it is "4" + 11 = "411"

doubles and overflow

Question: Predict each line. Which ones are surprising?

Answer

A double can't store 0.1 or 0.2 exactly, so small errors show up: 0.30000000000000004 and 0.09999999999999998.
7 / 2 is 3 because both sides are ints. 7 / 2.0 is 3.5 because one side is a double.
double half = 7 / 2; prints 3.0. The division happens first, as ints, and gives 3. Only then is 3 turned into a double.
Integer.MAX_VALUE is the largest int. Adding 1 to it wraps around to the most negative int, −2147483648. This is called overflow.

`&&` and `||`

a && b is true only if both are true. If a is false, Java skips b.
a || b is true if at least one is true. If a is true, Java skips b.
!a flips true and false.

Question: check prints a line every time it is called. What is the full output?

Answer

true
check 2
false
false
check 4
true

5 > 3 || check(1): the left side is true, so check(1) never runs.
5 < 3 || check(2): the left side is false, so check(2) runs. It prints check 2 and returns 2 > 2, which is false.
5 < 3 && check(3): the left side is false, so check(3) never runs.
5 > 3 && check(4): the left side is true, so check(4) runs and returns true.

`if` and `else`

if (condition) {
    // runs if condition is true
}

if (condition) {
    // runs if true
} else {
    // runs if false
}

In an if / else if / else chain, Java runs only the first branch whose condition is true and skips the rest.
Separate if statements are each checked on their own, so more than one can run.
An else belongs to the if right before it.

Letter grades

Given a score, print A for 90 and up, B for 80–89, C for 70–79, and F otherwise.

Question: This version uses separate if statements. What does it print for 95? For 85? For 50? Change the input and run it.

Answer

For 95, it prints A, B, and C. All three conditions are true, and each if is checked separately.

For 85, it prints B and C. For 50, it prints F. The else only belongs to the last if.

The fix is an else if chain, so only one branch runs:

The order of the chain matters. If you checked score >= 70 first, a 95 would get a C.

Using `return` instead of `else`

Question: This version also uses separate if statements. Why does it work?

Answer

return leaves the method immediately. Once a grade is returned, the if statements below it never run.

Every path must return

public static int sign(int n) {
    if (n > 0) {
        return 1;
    }
    if (n < 0) {
        return -1;
    }
    if (n == 0) {
        return 0;
    }
}

Question: Every int is positive, negative, or zero, so this always returns something. Why doesn't it compile?

Answer

The compiler doesn't reason about what n could be. It sees three separate if statements that might all be false, and then the method reaches the end without a return. Replacing the last if with else, or with a plain return 0;, fixes it.

`while` loops

while (condition) {
    // body
}

The condition is checked before each pass. If it is false at the start, the body runs zero times.
Something in the body must change a variable in the condition, or the loop never ends.
break leaves the loop. continue skips the rest of the body and goes back to the condition. return leaves the whole method.

Question: Which numbers are printed?

Answer

1, 2, 4, 5, 7. At 3 and 6, continue skips the print. At 8, break ends the loop, so 8 is not printed and 9 through 12 are never reached.

Sum of digits

For n >= 0: n % 10 is the last digit, and n / 10 removes the last digit.

Question: Trace sumDigits(1904). Write n and sum after each pass.

Answer

n before	digit added	sum after	n after
1904	4	4	190
190	0	4	19
19	9	13	1
1	1	14	0

n is now 0, so the loop stops and returns 14. The loop always ends because n / 10 is smaller than n whenever n > 0.

Greatest common divisor by subtraction

For a, b >= 1: subtracting the smaller number from the larger one doesn't change the gcd. Keep doing it until the two numbers are equal.

Question: Trace gcd(12, 18) and gcd(21, 6). Then edit the last line to gcd(5, 0) and run it. What happens, and why?

Answer

gcd(12, 18): (12, 18) → (12, 6) → (6, 6). Output 6.

gcd(21, 6): (21, 6) → (15, 6) → (9, 6) → (3, 6) → (3, 3). Output 3.

gcd(5, 0) never ends. a > b every time, and a = 5 - 0 leaves a at 5, so nothing changes.

When both inputs are at least 1, each pass subtracts at least 1 from a + b, so a + b keeps shrinking and the loop has to stop. With a 0, that is no longer true.

Reading until −1

Read numbers one at a time until you read −1. The −1 is a stop signal, not part of the data. Count how many times a number is bigger than the one before it.

Question: What is the output for 3 5 2 8 9 -1? Then try 4 4 4 -1 and 1 -1 in the input box.

Answer

3 5 2 8 9 -1 outputs 3: 3 → 5 is bigger, 5 → 2 is not, 2 → 8 is bigger, and 8 → 9 is bigger.

4 4 4 -1 outputs 0. Equal is not bigger.

1 -1 outputs 0. cur is −1 right away, so the loop body never runs.

Question: Edit the program so it also prints the largest number it read, not counting the −1.

Answer

Add int max = prev; before the loop. Inside the loop, add if (cur > max) { max = cur; }. After the loop, add System.out.println(max);. For 3 5 2 8 9 -1, it prints 9.

`for` loops

for (initialization; condition; update) {
    // body
}

The initialization runs once. Then the loop repeats three steps: check the condition, run the body, run the update. It stops when the condition is false.

Any for loop can be written as a while loop:

for (int i = 0; i < 3; i++) {
    System.out.println(i);
}

int i = 0;
while (i < 3) {
    System.out.println(i);
    i++;
}

A variable declared in the for initialization only exists inside the loop.

Odd numbers counting down

Goal: print every odd number from the input down to −5. Both programs below do the same thing.

Question: What should these print for input 4? What do they actually print? Find the bug.

Answer

They should print 3, 1, −1, −3, −5, but they only print 3 and 1.

For a negative odd number, % 2 gives −1, not 1. So -3 % 2 == 1 is false. The fix is i % 2 != 0. Edit the code and run it again.

With input −2, the buggy versions print nothing at all.

Question: In the for version, add System.out.println(i); after the loop. What happens?

Answer

It does not compile. i was declared in the for initialization, so it doesn't exist after the loop.

Stepping by 2

Instead of checking every number, start at the first odd number and subtract 2 each time. The initialization is empty because j is set before the loop. The semicolons are still required.

The same start can be written with the ? : operator: condition ? valueIfTrue : valueIfFalse.

`do-while`

do {
    // body
} while (condition);

The body runs first, and then the condition is checked. So the body always runs at least once.

Question: What does this print?

Answer

do-while:
10
while:
done

The do-while prints 10 before it checks 15 < 10. The while loop checks 10 < 10 first, which is false, so its body never runs.

Why a loop is correct, and why it stops

An algorithm is correct if, for every input, it stops and gives the right output. For a loop you show two things:

Loop invariant: something that is true before the loop starts and stays true after every pass.
Termination measure: a positive quantity that gets smaller on every pass. Since it can't shrink forever, the loop must stop.

Question: Trace power(3, 4). What is the loop invariant? What is the termination measure?

Answer

i	result	k − i
0	1	4
1	3	3
2	9	2
3	27	1
4	81	0, and `i < k` is false

Invariant: result equals base to the power i, and i <= k. When the loop ends, i == k, so result is base to the power k.

Termination measure: k - i. It is positive whenever the body runs, and it drops by 1 each pass.

Question: Give an invariant and a termination measure for the earlier loops: sum of digits, gcd, and reading until −1.

Answer

Sum of digits: sum is the sum of the digits already removed from n. The measure is n.
gcd: the gcd of a and b equals the gcd of the original inputs. The measure is a + b.
Reading until −1: count is the number of increases among the numbers read so far. There is no variable that works as a measure. The loop stops only because the input eventually contains −1.

Practice problems

Write each one on paper first, then open the answer.

1. Celsius to Fahrenheit

Write public static int c2f(int c) that converts Celsius to Fahrenheit, rounded toward zero, using only int. The formula is F = C × 9/5 + 32.

Question: Does c * 9 / 5 + 32 work? Try c = -17, where the exact answer is 1.4. And what is 37 * (9 / 5) + 32?

Answer

c * 9 / 5 + 32 gives 2 for −17. -153 / 5 is −30.6, which rounds toward zero to −30, and then adding 32 gives 2. The correct answer is 1.

The fix is to do the division last: (c * 9 + 160) / 5. Since 32 × 5 = 160, this is the same formula, but the rounding happens on the final answer.

37 * (9 / 5) + 32 is 69, because 9 / 5 is 1.

2. Seconds to hours, minutes, and seconds

Write three methods, hours(s), minutes(s), and seconds(s), for a number of seconds s >= 0. For example, 3725 seconds is 1 hour, 2 minutes, and 5 seconds.

Answer

An hour is 3600 seconds. s / 3600 is the hours. s % 3600 is what's left after removing the hours, and dividing that by 60 gives the minutes. s % 60 is the seconds.

3. Leap years

A year is a leap year if it is divisible by 4, except years divisible by 100 are not, except years divisible by 400 are. Write public static boolean isLeap(int y) in one return statement. Check 2024, 2023, 1900, and 2000.

Answer

2024 and 2000 are leap years. 2023 and 1900 are not.

4. Reverse the digits

For n >= 0, return the number with its digits reversed. What happens to 1200?

Answer

Each pass moves the last digit of n onto the end of rev: rev = rev * 10 + n % 10, then n = n / 10.

1200 becomes 21, because an int can't start with zeros. 405 becomes 504, so a 0 in the middle is kept.

5. Divisible by 3 or 5, but not both

For n >= 0, count the numbers from 1 to n that are divisible by 3 or by 5, but not by both. Use one loop and &&, ||, !. Find count(15), count(10), and count(1).

Answer

count(15) is 6: 3, 5, 6, 9, 10, 12. 15 is divisible by both, so it doesn't count.

count(10) is 5. count(1) is 0.

6. Prime numbers

Write public static boolean isPrime(int n). A prime is a number of at least 2 whose only divisors are 1 and itself. Why is it enough to test divisors d while d * d <= n?

Answer

If n = d × e, the smaller of d and e is at most √n. So if n has any divisor besides 1 and itself, one of them is small enough that d * d <= n.

Searching and sorting

Binary search

Binary search finds a number n in a sorted list:

Set lo = 1 and hi = length.
If lo > hi, output false.
Set mid = (lo + hi) / 2, rounded down.
If list[mid] = n, output true.
If list[mid] > n, set hi = mid - 1. Otherwise set lo = mid + 1. Go back to step 2.

Question: Trace binary search on [3, 7, 10, 14, 21, 28, 35, 42] for n = 28, then for n = 12.

Answer

n = 28
lo	hi	mid	list[mid]	next step
1	8	4	14	14 < 28, so lo = 5
5	8	6	28	equal, output true

n = 12
lo	hi	mid	list[mid]	next step
1	8	4	14	14 > 12, so hi = 3
1	3	2	7	7 < 12, so lo = 3
3	3	3	10	10 < 12, so lo = 4
4	3			lo > hi, output false

Question: What goes wrong on an unsorted list? Can it say true when the number isn't there? Can it say false when the number is there?

Answer

It can say false when the number is there. On [9, 2, 5] searching for 9: mid = 2, and 2 < 9, so lo = 3. Then mid = 3, and 5 < 9, so lo = 4. Now lo > hi, so it outputs false, even though 9 is in the list.

It can never say true when the number isn't there, because it only outputs true after finding list[mid] = n.

Selection sort

For position 1, then 2, then 3, and so on: find the smallest number in the rest of the list and swap it into that position.

Question: Sort [6, 2, 9, 4, 1]. Write the list after each swap.

Answer

Position 1: the smallest is 1. Swap 6 and 1 to get [1, 2, 9, 4, 6].
Position 2: the smallest of the rest is 2, which is already there. The list stays [1, 2, 9, 4, 6].
Position 3: the smallest of the rest is 4. Swap 9 and 4 to get [1, 2, 4, 9, 6].
Position 4: the smallest of the rest is 6. Swap 9 and 6 to get [1, 2, 4, 6, 9].

The last position doesn't need its own step. Once the first four are in place, the last number must be the largest.

Changing a flowchart

Go back to the list chart that outputs the position of the first element greater than n.

Question: What does each change do? Give an input where the output is different from the original.

Replace list[i] > n? with list[i] >= n?
Replace Output: i with Output: list[i]
Swap the two diamonds, so list[i] > n? is asked before i > length?

Answer

It finds the first element greater than or equal to n. On [3, 1, 4], n = 4, it outputs 3 instead of 0.
It outputs the element itself instead of its position. On [4, 9, 2, 11], n = 5, it outputs 9 instead of 2. When nothing is found it still outputs 0, which is confusing if 0 could be in the list.
When nothing is found, it reads list[length + 1], which doesn't exist. On [3, 1, 4], n = 4, it would read list[4].

Build a flowchart

Drag shapes onto the canvas, connect them with arrows, and fill in each step. Then run the chart, or step through it one shape at a time and watch the variables change.

Question: Build a chart for one of these, then test it on a few inputs.

Count how many elements of a list are even.
Selection sort, using minIndex and swap.
Read numbers with getNext until −1, and output the largest one.
Binary search, using floor for mid.

Run the chart

With Step, the highlighted shape is the one that runs next.

Output

Flashcards

Click the card to flip it. The arrow keys move between cards.

BC1014 Midterm Review

The structure of a Java file

Flowcharts

Warm-up

A chart with a list

From a flowchart to a Java method

Types

Converting between types

Order of operations

Integer math

doubles and overflow

&& and ||

if and else

Letter grades

Using return instead of else

Every path must return

while loops

Sum of digits

Greatest common divisor by subtraction

Reading until −1

for loops

Odd numbers counting down

Stepping by 2

do-while

Why a loop is correct, and why it stops

Practice problems

1. Celsius to Fahrenheit

2. Seconds to hours, minutes, and seconds

3. Leap years

4. Reverse the digits

5. Divisible by 3 or 5, but not both

6. Prime numbers

Searching and sorting

Binary search

Selection sort

Changing a flowchart

Build a flowchart

Run the chart

Flashcards

`&&` and `||`

`if` and `else`

Using `return` instead of `else`

`while` loops

`for` loops

`do-while`