Computer Science 15-100 (Lecture 18), Spring 2009
Homework 3
Due: Thu 5-Feb-2009 at 11:59pm (email copy) and at Friday's
class/recitation
(identical physical copy)
(no late submissions accepted).
Read the instructions from hw2 first (changing
"hw3" for "hw2" where appropriate). Then note these changes:
- Restrictions:
- Basically, you can use what we have covered so far this semester and you
cannot use what we have not yet covered.
- To be more specific, though...
- You may use Math methods, conditionals, and loops.
- You may not use String methods except charAt and length (which you may
use). For example, you may not use the equals or compareTo methods
from the String class (though you may write your own versions using just
charAt and length).
- You may not use arrays nor any other packages or classes not explicitly
mentioned in this hw. For example, you may not use Integer.parseInt
(which would defeat the point of one of the problems assigned this week).
-
For your non-graphical solutions, start with this file:
Hw3.java
- Short Answers
- Tracing
- Mystery Code
- Non-Graphical
Programming Problems
- factorial
- gcd
- lcm
- indexOf
- lastIndexOf
- isSubstring
- parseInt
- Painting Flags
-
Bonus/Optional:
wordsearchContains
- Short Answers
In the written portion of your submission, answer each of the following
questions. Be very brief, but show your work where appropriate.
Assume that "x" and "y" are possibly-negative integer values,
and "a", "b", and "c" are boolean values, and ignore any
errors (such as dividing by zero):
- The following code does not loop forever because of ____________.
int i=0;
while (i
<= 0)
i--;
- If ((Math.pow(x,2) < 15) &&
(Math.abs(x) > x)) is true, then x must be between ____________
and ___________ (inclusive).
- Fill
in the blank with one of “always”, “sometimes”, or “never”.
Be sure to show your work, using a truth table to
prove your answer:
((a || b) ? (!a && b) : (a || !b))
________________ equals (!a)
- Write a conditional expression (not a statement, so you may not use
"if") that evaluates to true exactly when at least two (and perhaps all
three) of a, b, and c are true.
Note: for this problem, you may not use more than 4 operators (&&, ||,
!, ==, !=, etc).
- One of DeMorgan's Laws states that !(a
&& b && c) is equivalent to (!a ||
!b || !c). Prove this using a truth table.
Hint: because you are using 3 variables, your truth table will have 23,
or 8 rows, one for each unique combination of truth values for a, b, and c.
- Tracing
In the written portion of your
submission, indicate what each of the following will print or (if it is
graphical) draw. Do not run these programs. Figure this out by
hand. Remember to show your work.
Hint: No loop runs for more than 6 iterations (so if your answer is
doing so, stop and check your work!).
- Mystery Code
In the written portion of your submission, state what the following program
does
in general, and in just a few words of plain English.
Hint: while you should definitely trace the code in this problem by hand to
make some sense out of it, you may also wish to actually test the code in a
compiler with samples of your choosing, at least to verify that it works as
you think it does!// Mystery code
import java.util.Scanner;
class MyCode {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.print("Enter a non-negative integer: ");
// You may assume the user enters a number in the desired range.
int x = scanner.nextInt();
boolean b = false;
while (x > 0) {
if (x % 10 == 3)
b = !b;
x = x/10;
}
System.out.println(b);
}
}
- Non-Graphical
Programming Problems
Do the following problems as defined by their comments in the file
Hw3.java. Read the comments and review the test
cases carefully!
- factorial
- gcd
- lcm
- indexOf
- lastIndexOf
- isSubstring
- parseInt
- Painting Flags
Paint the United
States flag using loops for the stripes and the stars (which
will be painted as ovals). You should use custom colors, matching
the colors in the flags as closely as possible. Also, your flags may not be
fixed-sized, but rather they must entirely fill the window, even when the
window is resized. While the window's size may change, you may assume the
window will be roughly "flag-shaped" -- you will not be graded on how your
flags appear in, say, a tall thin window (which is not at all
"flag-shaped").
Note: All these flag images are from the very informational
CIA
World Factbook, which includes a
flags-of-the-world page.
Note: As we are limited to just rectangles and ovals this week, you
should replace any stars in flags with ovals (of the same size, location,
and color).
Note: This week, you must deal with the
"thin white stripe" that occurs between stripes when the screen size is not
an even multiple of the stripe size.
a. United States
(file: Hw3FlagOfUnitedStates.java)
(larger
image with details)
-
Bonus/Optional:
wordsearchContains
Write the following method:
public static
boolean wordsearchContains(String wordsearch, String word)
This method takes a two strings, the first representing a wordsearch
(stored in a single string!), and returns true if the second string occurs
in that wordsearch and false otherwise.
To represent a wordsearch as a string, we simply store each row concatenated
to the next where we separate the rows with a | (that is, a vertical bar, or
a pipe). So, consider this wordsearch:
t a c w
n o o c
d o g x
The rows are: "tacw", "nooc",
and "dogx", so we represent the entire
wordsearch as: "tacw|nooc|dogx".
Note that this wordsearch contains:
cat
cod
coon
dog
ox
You are guaranteed the wordsearch contains only lowercase letters, and that
the rows are all the same positive length (you do not need to handle other
cases in any way).
Here is a test method for you: public static void testWordsearchContains() {
System.out.print("Testing wordsearchContains... ");
// These tests cover this wordsearch:
// t a c w
// n o o c
// d o g x
assert(wordsearchContains("tacw|nooc|dogx", "cat"));
assert(wordsearchContains("tacw|nooc|dogx", "cod"));
assert(wordsearchContains("tacw|nooc|dogx", "coon"));
assert(wordsearchContains("tacw|nooc|dogx", "dog"));
assert(wordsearchContains("tacw|nooc|dogx", "ox"));
assert(!wordsearchContains("tacw|nooc|dogx", "caw"));
assert(!wordsearchContains("tacw|nooc|dogx", "cow"));
assert(!wordsearchContains("tacw|nooc|dogx", "con"));
assert(!wordsearchContains("tacw|nooc|dogx", "dogs"));
assert(!wordsearchContains("tacw|nooc|dogx", "ax"));
System.out.println("Passed all tests!");
}
Note: This approach of representing a 2-dimensional board in a
1-dimensional string is not a very good idea. Soon, we will learn about
other ways we can more naturally represent this data, such as in a
2-dimensional array.
Carpe diem!