Deck 13: Searching and Sorting

Question 1

Expressions
For each expression at left, indicate its value in the right column. List a value of appropriate type and capitalization.
e.g., 7 for an int, 7.0 for a double, "hello" for a String, true or false for a boolean.
$\begin{array}{l}\underline{ \text { Expression } }& \underline{ \text { Value }} \\12 / 3+5+3 *-2 & \underline{ \text { }} \underline{ \text { }} \underline{ \text { }} \underline{ \text { }} \underline{ \text { }} \underline{ \text { }} \\1+1+"(1+1) "+1+1 & \underline{ \text { }} \underline{ \text { }} \underline{ \text { }} \underline{ \text { }} \underline{ \text { }} \underline{ \text { }}\\13 / 2-38 / 5 / 2.0+(15 / 10.0) & \underline{ \text { }} \underline{ \text { }} \underline{ \text { }} \underline{ \text { }} \underline{ \text { }} \underline{ \text { }}\\11<3+411 !(5 / 2==2) & \underline{ \text { }} \underline{ \text { }} \underline{ \text { }} \underline{ \text { }} \underline{ \text { }} \underline{ \text { }} \\20 \div 6+6 \div 20+6 \% 6 & \underline{ \text { }} \underline{ \text { }} \underline{ \text { }} \underline{ \text { }} \underline{ \text { }} \underline{ \text { }} \end{array}$

Answer 1

$\begin{array}{lc|}\underline{ \text { Expression } }& & \underline{ \text { Value }} \\12 / 3+5+3 *-2 && \text { } 3 \\1+1+"(1+1) "+1+1 & & "2(1+1)11" \\13 / 2-38 / 5 / 2.0+(15 / 10.0) & & 4.0 \\11<3+411 !(5 / 2==2) & & false \\20 \div 6+6 \div 20+6 \% 6 & &8\end{array}$

Question 2

Programming
Write a static method named xo that accepts an integer size as a parameter and prints a square of size by size characters, where all characters are "o" except that an "x" pattern of "x" characters has been drawn from the corners of the square. In other words, on the first line, the first and last characters are "x"; on the second line, the second and second-from-last characters are "x"; and so on. If 0 or less is passed for the size, no output should be produced.
The following table lists some calls to your method and their expected output:

Answer 2

There are many ways to solve any programming problem. Here are some common correct solutions we saw:
public static void xo(int size) {
for (int i = 1; i <= size; i++) {
for (int j = 1; j <= size; j++) {
if (j == i || j == size - (i - 1)) { // note the (i - 1), not i
System.out.print("x");
} else {
System.out.print("o");
}
}
System.out.println();
}
}
public static void xo(int size) {
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
if (j == i || j == size - 1 - i) {
System.out.print("x");
} else {
System.out.print("o");
}
}
System.out.println();
}
}
public static void xo(int size) {
int x1 = 1;
int x2 = size;
for (int i = 1; i <= size; i++) {
for (int j = 1; j <= size; j++) {
if (x1 == j || x2 == j) {
System.out.print("x");
} else {
System.out.print("o");
}
}
System.out.println();
x1++;
x2--;
}
}
public static void xo(int size) {
for (int i = 0; i < size / 2; i++) { // top half
repeat("o", i);
repeat("x", 1);
repeat("o", size - 2*i - 2);
repeat("x", 1);
repeat("o", i);
System.out.println();
}
if (size % 2 != 0) { // middle line (when odd size)
repeat("o", size / 2);
repeat("x", 1);
repeat("o", size / 2);
System.out.println();
}
for (int i = size / 2 - 1; i >= 0; i--) { // bottom half
repeat("o", i);
repeat("x", 1);
repeat("o", size - 2*i - 2);
repeat("x", 1);
repeat("o", i);
System.out.println();
}
}
public static void repeat(String s, int n) {
for (int i = 0; i < n; i++) {
System.out.print(s);
}
}

Question 3

If/Else Simulation
For each call below to the following method, write the output that is produced, as it would appear on the console:
public static void ifElseMystery(int x, int y) {
if (x == y) {
x = x + 11;
} else if (x > 2 * y) {
x = 0;
}
if (x == 0 || y > x) {
x = x + 2;
y = y + 2;
}
System.out.println(x + " " + y);
}
$\begin{array}{l}\underline{ \text { Method Call } }& \underline{ \text { Output }} \\\text { iftlsemystery }(5,5) \text {; } & \underline{ \text { }} \underline{ \text { }} \underline{ \text { }} \underline{ \text { }} \underline{ \text { }} \underline{ \text { }} \\\text { iftlsemystery }(18,4) \text {; } & \underline{ \text { }} \underline{ \text { }} \underline{ \text { }} \underline{ \text { }} \underline{ \text { }} \underline{ \text { }}\\\text { ifElsemystery }(3,6)\text {; } & \underline{ \text { }} \underline{ \text { }} \underline{ \text { }} \underline{ \text { }} \underline{ \text { }} \underline{ \text { }}\end{array}$

Answer 3

$\begin{array}{l}\underline{ \text { Method Call } }& \underline{ \text { Output }} \\\text { iftlsemystery }(5,5) \text {; } & 16\text { } \text { } 5 \\\text { iftlsemystery }(18,4) \text {; } & 2\text { } \text { } 6 \\\text { ifElsemystery }(3,6)\text {; } & 5\text { } \text { } 8 \end{array}$

Question 4

While Loop Simulation
For each call below to the following method, write the output that is produced, as it would appear on the console:
public static void whileMystery(int x, int y) {
while (x > 0 && y > 0) {
x = x - y;
y--;
System.out.print(x + " ");
}
System.out.println(y);
}
$\begin{array}{l}\underline{ \text { Method Call } }& \underline{ \text { Output }} \\\text { whilemystery }(7,5) \text {; } & \underline{ \text { }} \underline{ \text { }} \underline{ \text { }} \underline{ \text { }} \underline{ \text { }} \underline{ \text { }} \\\text { whilemystery }(20,4) \text {; } & \underline{ \text { }} \underline{ \text { }} \underline{ \text { }} \underline{ \text { }} \underline{ \text { }} \underline{ \text { }}\\\text { whilemystery }(40,10)\text {; } & \underline{ \text { }} \underline{ \text { }} \underline{ \text { }} \underline{ \text { }} \underline{ \text { }} \underline{ \text { }}\end{array}$

Question 5

Parameter Mystery
At the bottom of the page, write the output produced by the following program, as it would appear on the console.
public class ParameterMystery {
public static void main(String[] args) {
int a = 5;
int b = 1;
int c = 3;
int three = a;
int one = b + 1;
axiom(a, b, c);
axiom(c, three, 10);
axiom(b + c, one + three, a + one);
a++;
b = 0;
axiom(three, 2, one);
}
public static void axiom(int c, int b, int a) {
System.out.println(a + " + " + c + " = " + b);
}
}

Question 6

Programming
Write a static method named anglePairs that accepts three angles (integers), measured in degrees, as parameters and returns whether or not there exists both complementary and supplementary angles amongst the three angles passed. Two angles are complementary if their sum is exactly 90 degrees; two angles are supplementary if their sum is exactly 180 degrees. Therefore, the method should return true if any two of the three angles add up to 90 degrees and also any two of the three angles add up to 180 degrees; otherwise the method should return false. You may assume that each angle passed is non-negative.
Here are some example calls to the method and their resulting return values.
$\begin{array}{l|l}\text { Call } & \text { Value Returned } \\\hline \text { anglePairs }(0,90,180) & \text { true } \\\text { anglePairs }(45,45,45) & \text { true } \\\text { anglePairs }(177,87,3) & \text { true } \\\text { anglePairs }(120,60,30) & \text { true } \\\text { anglePairs }(35,60,30) & \text { false } \\\text { anglePairs }(120,60,45) & \text { false } \\\text { anglePairs }(45,90,45) & \text { false } \\\text { anglePairs }(180,45,45) & \text { false }\end{array}$

Question 7

Programming
Write a static method named baseball that takes a Scanner representing the console as a parameter and plays an interactive baseball scoring game with the user, returning an integer representing which team won the game.
Baseball is a sport where teams play a series of innings against each other. Each team scores a certain number of runs (points) in each inning. A baseball game ends when one of the following conditions is met:
-After 9 innings are finished, if one team has more total runs than the other, the team with more runs wins.
-After 9 innings are finished, if the teams are tied (if they have the same number of total runs), we keep playing one more full inning at a time until the teams are not tied any more.
-After any inning, if one team is ahead by 10 or more runs, the game is called and the team with more runs wins.
Your method should repeatedly prompt the user, once per inning, to enter the number of runs that each team scored during each inning. The user will type in the first team's runs for that inning, followed by the second team's runs for that inning, separated by whitespace. Your method should stop prompting once one or more of the above bulleted conditions are met, causing the game to end. At the end of the game, you should print the final score. You should also return an integer for which team won: return 1 if the first team won, and 2 if the second team won.
You may assume that the user enters valid non-negative integers whenever prompted, and you may assume that the game will eventually end (it won't go on forever).
Here are some example calls to the method and their resulting output and return values:
Scanner console = new Scanner(System.in);
(More writing space can be found on the next page.)

Question 8

Assertions
For each of the five points labeled by comments, identify each of the assertions in the table below as either being always true, never true, or sometimes true / sometimes false. (You may abbreviate them as A, N, or S.)
public static int stuff(Random r, int m) {
int c = 0;
int t = 0;
int d = r.nextInt(m);
// Point A
while (c <= 3) {
// Point B
d = r.nextInt(6) + 1;
if (d <= m) {
c++;
// Point C
} else {
c = 0;
// Point D
}
t++;
}
// Point E
return t;
}
$\begin{array}{l|l|l|l} & c>3 & d<=m & c==0 \\\hline \text { Point A } & & & \\\hline \text { Point B } & & & \\\hline \text { Point C } & & & \\\hline \text { Point D } & & & \\\hline \text { Point E } & & & \\\hline\end{array}$