A well-designed computer program is easy to use without any special knowledge. For example, most people can learn to navigate webpages with only a few minutes of practice. On the other hand, programming a computer requires special knowledge about what the computer can fundamentally do and how you would communicate with it through a programming language.
Typically program code is stored on a hard disk, CD/DVD disc, or in some other central location across a network. User data is often more likely to be stored on a local hard disk, although it can also be stored on a network or even a CD/DVD for backup storage.
The monitor, speakers, and printer serve as the primary devices to give information to the user. The keyboard and mouse are the primary devices that take user input.
It's very likely your cell phone is a programmable computer. If you can take pictures, send email/text messages, and/or surf the web with your phone, it is a programmable computer. If your cell phone can only send and receive phone calls, it is probably a single-function device.
One advantage of Java over machine code is that Java statements are independent of the machine (computer) they are being executed on; machine code statements differ from one type of machine to the next. Another advantage of Java is that it is much more readable and understandable (by humans) than machine code.
a)Solutions here will vary based on user and IDE preference. On a UNIX-based system using the Eclipse IDE you may see a path like
/home/nancy/JFE/src
While on a Microsoft Windows machine you might find a directory like:
C:\Users\nancy\Documents\JFE\src
b)Again, solutions can vary. On Unix using Eclipse you might see:
/home/nancy/JFE/bin
A Microsoft Windows machine might be:
C:\Users\nancy\Documents\JFE\bin
c)The answer to this question is dependent on the type of operating system and version of Java. On a Unix based system using Java 1.6 you might find rt.jar
here:
/usr/lib/jvm/java-6-sun-1.6.0.13/jre/lib/rt.jar
While on a Microsoft Windows platform you might find it here:
C:\Program Files\Java\jdk1.6.0_10\jre
The program prints the following:
39 + 3 42
Java interprets the statement "
39 + 3
"
as a string and thus prints out the literal characters 39 + 3
. Java interprets the second statement 39 + 3
as an operation between two numbers, so it first calculates the value 39 + 3 = 42
then prints out the result 42
.
HelloWorld
Because there are no spaces after the System.out.print("Hello");
the next line prints World
directly after Hello
is printed.
Java interprets the comma in the println
method to mean that two strings are passed to println
. It’s likely the programmer meant to do this:
System.out.print("Hello, World!");
Compile-time errors:
public class HelloPrinter { public static void main(String[] args) { System.outprint("Hello, World"); /* ^^ missing '.' */ } } public class HelloPrinter { public static void main(String[] args) { System.out.print("Hello, World); /* ^^ missing '"' */ } } public class HelloPrinter { public static void main(String[] args) { System.out.print("Hello, World") /* ^^ missing ";" */ } }
Run-time error:
public class HelloPrinter { public static void main(String[] args) { System.out.print("Hello, Wrold"); }
Syntax errors are discovered by compiling your Java program; the Java compiler will report them directly. Logic errors are discovered by testing your program by running it and verifying the correct output; if the output is incorrect, you have a logic error.
Start with the customer knowing how often they visit the cafeteria and the average price they pay for a meal. Ask the cafeteria for cost of the discount card, the number of meals to be eaten to achieve the free meal, and the period of time in which all meals must be consumed. If cost of the card is greater than the average cost of a customer meal Deal is set to “no good” Else If qty of meals to be eaten is greater than qty of customers meals in the time period then Deal is set to “no good” Else Deal is set to “good”
Start with a year of value 0, a month of value 0, and a balance of $10,000 Repeat the following while the balance is greater than 0 Multiply the balance by 1.005. Subtract 500 from the balance. Add one to month. If the month is 12 Set month to 0. Add one to year. Year has the answer.
If the starting balance is large enough and the interest rate large enough such that the first month's calculation of interest exceeds the monthly expenses, then you will never deplete your account and the algorithm will never terminate. Modified algorithm: Ask the user for balance, interest rate, and monthly expenses. If balance x interest is greater than monthly expenses Tell the user you're in good financial shape and quit. Otherwise, start with a year of value 0, a month of value 0 and a balance of $10,000 Repeat the following while the balance is greater than 0 Multiply the balance by (1 + (interest rate times .01 divided by 12)). Subtract monthly expenses from the balance. Add one to month If the month is 12 Set month to 0. Add one to year. Year has the answer.
Calculate the overall surface area of the house without windows and doors. surfaceArea = (2 x width x height) + (2 x length x height) - (number of windows x windowWidth x windowHeight) - (number of doors x doorWidth x doorHeight)
The computer cannot accurately predict what the price of gas will be on a daily basis (or know what day you will go to the gas station) and how many actual miles you will drive each year.
Every day at 5 P.M. please do the following:
1)Insert the USB memory stick into the computer.
2)Create a new directory on the USB memory stick entitled "BACKUP-DATE" where "DATE" is replaced with the current date.
3)Copy the files from the "My Documents" folder on the computer to the folder you just created on the USB stick.
4)Double check to make sure the new directory contains the files you copied. If the folder is empty, something is wrong. It's possible you backed up to the wrong directory. Try it again and be careful which directory you copy into.
5)Once you verified the copy is complete, remove the USB stick and store it someplace safe.
6)Thank you!
Get the orange juice from the refrigerator Get the eggs from the refrigerator Get the bacon from the refrigerator Make the pancake batter For each person eating breakfast: Crack an egg on the griddle Pour two pancakes on the griddle Place two slices of bacon on the griddle Pour a glass of orange juice Dish up a plate of cooked food Call the family to breakfast
close enough = 0.001 a = value from user to be square rooted first guess = a / 2 second guess = (first guess + (a / first guess)) / 2 repeat first guess = second guess second guess = (first guess + (a / first guess)) / 2 until (first guess - second guess) <= close enough second guess holds the square root of a
An object is an instance (an entity) that defined by a class. A class provides a definition which includes characteristics (data) and behavior (methods).
Examples of String objects:
"Hello World"
"Schrödinger is the name of my cat."
"I LOVE programming"
Example of PrintStream object:
System.out
Sample Methods in the String class that are not in PrintStream class:
length()
toUpperCase()
Sample Method in the PrintStream class that is not in String class:
println()
The public interface consists of all the methods we can apply to any of its objects. Essentially, it is the set of methods to interact with the class. The implementation is how the methods accomplish their tasks. The public interface is accessible to all; the implementation should be private.
double price = 5.50; String description = “Dress Socks”;
The value of mystery
is equal to 0 after the statements are executed. In the first statement (line 1), mystery
is initialized to a value of 1. In the assignment statement on line 2, mystery
is set to -1. Finally, mystery
is set to 0 in line 3.
The variable mystery
is being declared twice, first in line 1 and then again in line 2. A variable can only be initialized once. (If you remove the reserved word int
on line 3, the statements will work just fine, and will set mystery
to -3.)
In the Java programming language, the = operator denotes an action, to replace the value of a variable. This usage differs from the traditional use of the = symbol as a statement about equality.
title = ”Big Java”; char letter = title.chatAt(0); // letter would be ’B’ int titleLength = title.length(); // titleLength would be 8
String message = "Hello"; message = message.toUpperCase();
String message = "Hello"; message = message.replace("H", "h");
String message = "Hello, World!"; message = message.replace(",", ""); message = message.replace("!", "");
An object contains state information. An object variable contains an object reference, that is, the location of an object.
new Rectangle(5, 10, 20, 30); // Object Rectangle box; // Object variable
new Rectangle(75, 75, 50, 50) "Hello, Dave!"
Rectangle square = new Rectangle(75, 75, 50, 50); String greeting = "Hello, Dave!";
Rectangle square = new Rectangle(10, 20, 40, 40); square = new Rectangle(10, 20, 40, 40);
Rectangle square1 = new Rectangle(20, 20, 40, 40); Rectangle square2 = square1; // the same object
a. new
Rectangle
is missing
b. Rectangle(5, 10, 15, 20)
does not refer to an object. The corrected version should be:
double width = (new Rectangle(5, 10, 15, 20)).getWidth();
c. r
has not been initialized; it does not refer to any object.
d. The method translate
takes two integer arguments, not a string argument.
Possible answers are:
Accessor: getWidth()
, getHeight()
Mutator: translate(int, int)
, add(int, int)
Class |
Return type |
Method name |
Types of arguments |
String |
String |
concat |
String |
String |
String |
trim |
none |
Rectangle |
String |
toString |
none |
Rectangle |
Rectangle |
union |
Rectangle |
Random |
float |
nextFloat |
none |
An object contains state information. An object reference is the location of that object in memory.
Console applications provide text-only interfaces and cannot display any drawings/figures (except ASCII art). Graphical applications are more user friendly and can display drawings inside frames (windows).
The Swing toolkit calls the paintComponent
method whenever the component needs to be repainted. For example, it is called when the window is shown for the first time, when it is resized, or when it is shown again after it was hidden.
The designers of Java did not want to inconvenience those programmers who had produced programs that used simple graphics from the Graphics
class after they developed the newer, more powerful Graphics2D
class, so they did not change the parameter of the paintComponent
method to Graphics2D
.
The purpose of a graphics context is to store the programmer choices for colors, fonts, and so on, and to draw and fill shapes.
The paintCompoment
method of the component class produces a drawing, while the main
method of the viewer class constructs a frame and a component, adds the component to the frame, and makes the frame visible.
You specify a text color simply by calling the setColor
method of the graphics context before calling the drawString
method.
The public interface of the Counter in Section 3.1 consists of the click, getValue, and reset methods. The public interface specifies the functionality supported by the class but does not disclose any details of how the functionality is implemented. In contrast, the implementation of a class is the code that accomplishes the tasks to support the class’s functionality.
Encapsulation is the process of hiding implementation details while publishing an interface for programmers to use. If you hide the implementation details, you can diagnose errors and make changes and improvements to the implementation of a class without disrupting the work of programmers who use the class.
The private
reserved word prevents a programmer using the class from manipulating instance variables except through the methods of that class. A programmer must use the public interface—the public methods that access or modify the instance variables—to change them. As such, the instance variables are hidden from methods outside of the class.
private String grade;
or a numeric value that corresponds to the letter grade to simplify gpa calculations
private double grade;
Represent the time as one entire string value, example “8:35 a.m.”
private String value;
or as individual components
private int hour; private int minute; private String meridian;
The programmers using the Time
class do not have to do anything. The code that uses the Time class is written based on the public interface and, as such, it need not change unless the public interface changes. That is the purpose of encapsulation and using a public interface.
No, there should not be a setValue method. The Counter class, as the original example indicates, models a device that can be used to count people. The tally increases by one for each person counted. The required functionality does not dictate the need to begin a tally at a value other than zero.
If there is a need to begin a count at a value other than zero, then a constructor should be added to support such functionality. A mutator such as setValue should only be added if there is a need to support functionality to reset an existing counter to a value other than zero.
(a) If BankAccount(double initialBalance)
did not exist, we could use the default constructor to create a BankAccount
and then use the deposit
method to increase the balance.
BankAccount account = new BankAccount(); account.deposit(1500);
is equivalent to
BankAccount account = new BankAccount(1500);
(b) (The previously provided answer does not address the question asked.)
If the BankAccount() constructor is removed from the BankAccount class, then creating an object of the BankAccount class would require using the BankAccount(double initialBalance) constructor. This constructor allows the specification of an initialBalance which can be 0.
BankAccount account = new BankAccount(0);
is equivalent to (with the no-argument constructor available)
BankAccount account = new BankAccount();
A reset
method effectively empties the account without any accountability. It would be best to create a new object if you want to delete an account and start with a new one. Otherwise, use the withdraw
method to reduce the balance down to zero, which is how a real bank account should work.
The account will have a negative balance. There are no checks to detect or stop this from happening.
The this
reference is used to refer to the implicit parameter of a method. It can be used to clarify the code, to explicitly access instance variables and methods in the object referenced by the implicit parameter, and to call another constructor of the same class.
Mutator Methods
recordPurchase
receivePayment
Accessor Method
giveChange
The method transfers an amount from the account passed as the implicit parameter to the account that is given as an explicit parameter.
Here is a sample call:
BankAccount harrysChecking = new BankAccount(); BankAccount momsSavings = new BankAccount(10000); momsSavings.mystery(harrysChecking, 1000);
public class TimeDepositAccount { private double balance; private double interestRate; // Constructor public TimeDepositAccount( double initialBalance, double interestRate) { this.balance = initialBalance; this.interestRate = interestRate; } // Methods public void withdrawAll() { balance = 0.0; } public double getBalance() { return balance; } public void addInterest() { balance = balance + balance * interestRate; } }
Instance variables are initialized when the object is created. In this case, area
would be initialized to zero and wouldn't get calculated with the correct value until getArea
is called. If another method were added to this class that used area
, it would incorrectly use the value zero if getArea
had not been called first to calculate the correct value. As is, area
is used in only a single method, getArea
, and does not hold a value that must exist across method calls. This suggests that area
is a candidate for being turned into a variable local to getArea
public class Square { private int sideLength; public Square(int length) { sideLength = length; } public int getArea () { int area; // local variable area = sideLength * sideLength; return area; } }
If the method grow
is called, the value of the instance variable area will no longer be correct. You should make area
a local variable in the getArea
method and remove the calculation from the constructor.
public class Square { private int sideLength; public Square(int length) { sideLength = length; } public int getArea () { int area; // local variable area = sideLength * sideLength; return area; } public void grow () { sideLength = 2 * sideLength; } }
/** A class to test the Counter class. */ public class CounterTester { /** Tests the methods of the Counter class. @param args not used */ public static void main(String[] args) { Counter tally = new Counter(); int result = tally.getValue(); System.out.println(result); System.out.println("Expected 0"); tally.count(); tally.count(); tally.count(); result = tally.getValue(); System.out.println(result); System.out.println("Expected 3"); tally.reset(); result = tally.getValue(); System.out.println(result); System.out.println("Expected 0"); } }
/** A class to test the Car class. */ public class CarTester { /** Tests the methods of the Car class. @param args not used */ public static void main(String[] args) { Car myHybrid = new Car(50); // 50 miles per gallon myHybrid.addGas(20); // Fill tank with 20 gallons myHybrid.drive(100); // Drive 100 miles, use 2 gallons myHybrid.addGas(10); // Add 10 gallons to tank myHybrid.drive(200); // Drive 200 miles, use 4 gallons double gasLeft = myHybrid.getGasInTank();// Gas remaining in tank System.out.println(gasLeft); System.out.println("Expected 24"); } }
Card Front:
BankAccount harrysChecking BankAccount BankAccount(initialBalance) deposit(amount) withdraw(amount) getBalance
Card Back:
balance020001500
Card Front:
CashRegister register CashRegister recordPurchase(amount) receivePayment(amount) giveChange
Card Back:
purchase | payment |
0 | 0 |
Card Front:
Menu mainMenu addOption(option) display
Card Back:
optionCount menuText0“”1“1) Open new account\n”2“1) Open new account\n2) Log into existing account\n”3“1) Open new account\n2) Log into existing account\n3) Help\n”4 “1) Open new account\n2) Log into existing account\n3) Help\n4) Quit\n”
First, we need to add a new instance variable to keep track of the number of transactions each month. We will add the following instance variable to the class:
int numTransactions;
This variable should be incremented by one inside the withdraw
and deposit
methods. The following line of code could be added to the end of these methods:
numTransactions++;
And, of course, we should initialize this variable to zero inside both constructors.
Finally, we need to add a new instance method that will calculate and deduct the fee ($1 for each transaction over 5) and reset the numTransactions
variable to zero (to start the new month).
public void calculateTransFee() { if (numTransactions > 5) { balance = balance – (numTransactions – 5); } numTransactions = 0; }
And for the new object trace, let’s assume the following method calls are made over two months
BankAccount harrysAccount(1000); harrysAccount.deposit(50); harrysAccount.deposit(500); harrysAccount.deposit(250); harrysAccount.withdraw(100); harrysAccount.deposit(70); harrysAccount.deposit(80); harrysAccount.calculateTransFee(); harrysAccount.deposit(150); harrysAccount.deposit(500); harrysAccount.deposit(250); harrysAccount.withdraw(100); harrysAccount.deposit(70); harrysAccount.deposit(90); harrysAccount.deposit(190); harrysAccount.calculateTransFee );
Here are the updated object cards showing the results of these method calls:
You can see that thenumTransactions
variable resets whenever the fee is calculated, and then a fee is subtracted from the balance (one dollar for every transaction over 5).
You need four classes: House
, Car
, SceneComponent
, and SceneViewer
.
The methods have the same implicit parameter as the paintComponent
method. We could have written the calls as this.getHeight()
and this.getWidth()
. They are accessor methods so they don't need an explicit parameter; the instance variables of the object are all they need to do their work.
Add width
and height
fields to the Car
class, initialize them in the Car
constructor, and use them in the draw
method to determine the dimensions of the body, tires, and windshield
This is somewhat ambiguous. Are the variables local variables, or class variables? I assume class variables:
public static final int DAYS_IN_WEEK = 7; public int daysToSemesterEnd; public static final double CENTIMETERS_IN_INCH = 2.54; public double tallestHeight;
The value of mystery
is equal to 0 after the statements are executed. In the first statement (line 1), mystery
is initialized to a value of 1. In the assignment statement on line 2, mystery
is set to -1. Finally, mystery
is set to 0 in line 3.
The variable mystery
is being declared twice, first in line 1 and then again in line 2. A variable can only be initialized once. (If you remove the reserved word int
on line 3, the statements will work just fine, and will set mystery
to -3.)
a) dm = m ((√(1 + v)/c) / (√(1 – v)/c)) – 1
b) volume = π r2h
c) volume = (4 π r3h)/ 3
d) z = √(x2 + y2)
a) double s = s0 +(v0 * t) + (.5 * g * Math.pow(t,2));
b) double g = 4 * Math.PI * Math.PI* (Math.pow(a,3)/(p * p * (m1 + m2)));
c) double fv = pv * Math.pow((1 + (intRate / 100)), yrs);
d) double c = Math.sqrt((a * a) + (b * b) - (2.0 * a * b * Math.cos(gamma)));
a |
b |
Math.pow(a, b) |
Math.max(a, b) |
a/b |
a%b |
Math.floorMod(a, b) |
2 | 3 | 8 | 3 | 0 | 2 | 2 |
3 | 2 | 9 | 3 | 1 | 1 | 1 |
2 | -3 | 0.125 | 2 | 0 | 2 | -1 |
3 | -2 | 0.111 | 3 | -1 | 1 | -1 |
-3 | 2 | 9 | 2 | -1 | -1 | 1 |
-3 | -2 | 0.111 | -2 | 1 | -1 | -1 |
A wrong result will occur when turning left and the absolute value of the turn is greater than the current direction.
There will be an error when (-1 * turn) > direction
To solve this without using Math.floorMod(), you could implement the following:
if ((-1 * turn) > direction) { direction = 360 + (turn + direction) }
a) 6.25
b) 6
c) 12.5
d) -3
e) 1.4142135623730951
a) 8
b) 1
c) 17
d) 17.5
e) 17
f) 18
a) 10
b) e
c) llo
d) HelloWorld
e) WorldHello
1)There is an extraneous semicolon after main()
.
2) The message in the first print statement is not surrounded by quotation marks like a string should be.
3) The variables x
and y
are not declared.
4) The variable in
is not declared.
5) The method readDouble
doesn’t exist (nextDouble
does).
6) If readDouble
were a method, it should be followed by ()
.
7) In the last line the method println
is incorrectly spelled printline
.
1) The scanner should have been constructed without quotations as Scanner in = new Scanner(System.in);
2) The correct Scanner method for reading integers is nextInt();
3) The second integer should have been read as y = in.nextInt();
(The problem requests 3 answers but there are 4 mistakes)
The given output is printed in a raw format up to the range of a double
data type. Users can use format specifiers (printf
with%
) to format the output as they require.
The type of 2 is int. The type of 2.0
is a double; specifically the Java programming language recognizes it as the real number 2.0. The type of ’2’
is a char. On the other hand, Java treats "
2
"
and "2.0"
as strings.
a)This statement computes the value of y. Given the initial value of x as 2, the result for y is 4.
b)This statement concatenates the strings "2"
together. The result for t is "22".
Read input into a variable called word. Print first character in word followed by a space. Print character at length -1 in word followed by a space. Print substring between 1st and last character (length -1) in word.
Read first name into variable called first. Read middle name into variable called middle. Read last name into variable called last. Print first character in first. Print first character in middle. Print first character in last.
// Input is stored in variable called num exponent = integer part of log10 of num first digit = integer part of num / 10^exponent last digit = num % 10 Print first digit. Print last digit.
change due = 100 x bill value – item price in pennies quarters = change due / 25 (without remainder) change due = change due % 25 dimes = change due / 10 (without remainder) amount due = change due % 10 nickels = change due / 5 (without remainder) // Change is now in quarters, dimes, and nickels
As long as you used the theodolite to sight in the top exactly at the midpoint of a side, then no other information is needed. You may use your right triangle trigonometry to calculate the height on the side of the pyramid. From there you can calculate the surface area of the pyramid.
public class ConeSurfaceArea { public static void main(String[] args) { // set circumference and angle of elevation (in degrees) double circumference = 6.29; double angle = 45; // find radius using C = 2(pi)r double radius = circumference / (2 * Math.PI); // find height using right triangle trig double height = radius * Math.tan(angle); // calculate surface area using SA = (pi)r * (r + sqrt(height^2 + radius^2) double surfaceArea = Math.PI * radius * (radius + Math.sqrt(Math.pow(height,2) + Math.pow(radius,2))); System.out.println(surfaceArea); } }
First, compute the total volume by hand using the formula in Self Check 25. Let’s assume the following values for the three sections:
.Conic Section 1 (top of bottle) has first radius (r11) 0.5 inches, second radius (r21) 0.75 inches, and height (h1) 1.5 inches.
Conic Section 2 (middle) has first radius (r12) 0.75 inches, second radius (r22) 1.5 inches, and height (h2) 0.5 inches.
Conic Section 3 (bottom of bottle) has first radius (r13) 1.5 inches, second radius (r23) 0.75 inches, and height (h3) 6.0 inches.
So, the total volume of the bottle, Vt, will equal the volume of conic section 1 (V1) plus the volume of conic section 2 (V2) plus the volume of the conic section 3 (V3):
Vt = V1 + V2 + V3
We calculate the three volumes to be (rounded to two decimal places):
V1 = 1.87 cubic inches V2 = 2.06 cubic inches V3 = 24.74 cubic inches
So, the total volume for the cocktail shaker in our example is:
Vt = V1 + V2 + V3 = 28.67 cubic inches
The algorithm we use is very similar to the calculation we did above:
volume 1 = π x (r112 + r11 x r21 + r212) x h1 / 3 volume 2 = π x (r122 + r12 x r22 + r222) x h2 / 3 volume 3 = π x (r132 + r13 x r23 + r232) x h3 / 3 total volume = volume 1 + volume 2 + volume 3
Because we are given the diameter of the circle, d, and not the height of the circular sector, h, we need to develop an algorithm to find h based on the value of d.
If you look at the figure on the right, you see that a right triangle can be made bounded by the chord, the diameter of the circle, and the radius of the circle drawn through h.
Because we know the length of the radius (half the diameter), we can set up an equation to find the value of h:
h = 0.5d - x
where x is one side of the right triangle. We can solve for x by using trigonometry on the right triangle, and then use that value to solve for the value of h, which we need to compute the area of the circular sector (the oddly-shaped piece of pie). In the right triangle, the side labeled x is considered to be the “opposite” side. We know that the hypotenuse of the right triangle is half the diameter, or 0.5d, and the “adjacent” side of the right triangle is half the chord length, or 0.5c.
Therefore, we can use the following formulas for a right triangle to determine what we need for the problem:
sin
θ = opposite/hypotenuse
cos
θ = adjacent/hypotenuse
Here is the general algorithm (see figure for definition of the variables):
Ask the user to enter the diameter of the circle, store the value in d. Ask the user to enter the length of the chord, store the value in c.
Compute the angle
θ with formula
θ
= cos
-1
(0.5c / 0.5d).
Compute the length of x with the formula x = sin θ * 0.5d. Determine h using the formula h = 0.5d – x. Calculate the area of the pie piece, A, using the formula. A = 2.0 / 3 * c * h + pow(h, 3) / (2 * c).
We can use this algorithm to solve for the specific example of a pie with diameter 12 inches and a chord length of 10 inches:
We know that d = 12, c = 10.
Therefore, θ = cos-1(0.5c/0.5d) = cos-1(5/6) = 33.56 degrees
x = sin θ * 0.5d = sin 33.56 * 6 = 3.32 inches
h = 0.5d – x = 6 – 3.32 = 2.68 inches
A = 2/3 * c * h + h3/(2*c) = 2/3 * 10 * 2.68 + 2.683 / (2 * 10) = 18.83 square inches
Starting position is 3 x 4 = 12 and length of substring is 3.
SunMonTueWedThuFriSat 0 3 6 9 12 15 18
We can see this will extract the substring Thu
.
Character at position i
(2)
Gateway 0123456
Character at position j
(4)
Gateway 0123456
first:
Gateway 0123456
middle:
Gateway 0123456
last:
Gateway 0123456
Generate a new string: first + character at j + middle + character at i + last
Gawetay 0123456
You can read characters from a string with the charAt
method. For the first character, pass a position of 0 to charAt
. For the last character pass the position that is equal to the length of the string -1 to charAt
.
Strings in Java are immutable, so they cannot be directly changed. Thus, to “remove” the first character from a string, we can take a substring of the original string that contains the entire thing minus the first character. If our string is called s
, then this works: s.substring(1, s.length());
. The last character can be obtained by extracting the substring that contains the entire string minus the last character, like this: s.substring(0, s.length()-1);
.
a) Exact
b) Exact
c) Overflow
d) Overflow
This program:
public class R222 { public static void main(String[] args) { System.out.println(3 * 1000 * 1000 * 1000); System.out.println(3.0 * 1000 * 1000 * 1000); } }
Prints out the following:
-1294967296 3.0E9
The reason the first number is negative is because we have exceeded the limited range of an int
and the number overflowed to a negative value. The second number’s result is correct but displayed in scientific notation because it is a floating-point type from the 3.0
in the calculation.
a) n = 1, k = 2, r = 1
b) n = 1, k = 2, r = 2
c) n = 1, k = 1, r = 2
d) n = 1, k = 6, r = 3
In the first block, the conditions are evaluated sequentially, so s
could be incremented twice. In the second block, the conditional statements are mutually exclusive, so, s
cannot be incremented more than once.
a)There are two errors in this code. First, there are no parentheses around the x > 0
part of the if
statement. Secondly, there is an extraneous then
which is not part of the Java syntax, instead we should wrap the body of the if
statement in curly braces. A correct form would be:
if (x > 0) { System.out.print(x); }
b)In this statement there aren’t enough parentheses to balance the condition (there are only two). The following would be correct:
if (1 + x > Math.pow(x, Math.sqrt(2))) { y = y + x; }
c) In this case there is only a single =
in the if
statement. Likely the programmer wanted to check for equality rather than set x
equal to the value of 1
. A correct form would be:
if (x == 1) { y++; }
d) The problem in this case is that the programmer tried to validate the input after she read it thus defeating the whole purpose of input validation. Instead we should take the line which reads the integer into the body of the if statement, like this:
if (in.hasNextInt()) { x = in.nextInt(); sum = sum + x; } else { System.out.println("Bad input for x"); }
e) The if
statements should be an if/else if/else
sequence. More than one if
statement will be executed for any grade higher than 60 and the letter grade will be wrongly assigned.
a) -1
b) 1
c) 1.0
d) 2.0
if (x > 0.0) { y = x; } else { y = 0.0; }
if (x < 0.0) { y = -x; } else { y = x; }
Floating-point numbers only have limited precision so it’s very likely that any mathematical operation (like addition, multiplication, etc.) will introduce small errors into the result.
To check to see if an integer equals 10:
if (n == 10) { System.out.println("It's 10!"); } else { System.out.println("It's not 10!"); }
To check to see if a floating-point number approximately equals 10:
final double EPSILON = 1E-14; double x = 10.0; if (Math.abs(x - 10) < EPSILON) { System.out.println("It's approximately 10.0!"); } else { System.out.println("It's not 10.0!"); }
a) (x1==x2 && y1==y2)
b) (Math.sqrt(Math.pow(X1-X2, 2) + Math.pow(Y1-Y2, 2)) < 5)
In the first case when comparing if (floor = 13)
you should get the error “Type mismatch: cannot convert from int to boolean".
In the statement count == 0;
you should get the error “Syntax error on token “==”, invalid assignment operator”.
letter number color g 5 “black”
The following test cases cover all four branches.
a) “g5”
b) “h5”
c) “g4”
d) “h4”
Trace of appointment from 10-12 and one from 11-13:
start1 start2 end1 end2 s e 10 11 12 13 11 12
Since s < e the program would report “The appointments overlap.” Which is indeed the case.
Trace of appointment from 10-11 and one from 12-13
start1 start2 end1 end2 s e 10 12 11 13 12 11
Since s > e the program would report “The appointments don’t overlap.” Which is correct.
The flowchart for Exercise R3.11:
The flowchart:
The flowchart:
Test Case Expected Outcome Comment ==================================================== Start1=12 End1=14 No overlap Completely separate Start2=15 End2=16 appointments Start1=12 End1=14 Overlap Overlap by 1 hour Start2=13 End2=15 Start1=12 End1=14 Overlap Appointment 2 starts before Start2=11 End2=15 and ends after Appointment 1 Start1=12 End1=14 No overlap Appointment 2 starts and ends Start2=9 End2=10 before Appointment 1 Start1=12 End1=14 Overlap Exact same appointment Start2=12 End2=14 Start1=12 End1=14 No Overlap Appointment 2 is right after Start2=14 End2=17 Appointment 1, boundary condition
Test Case Expected Outcome Comment ===================================================================== Month=1, Day=10 Season=Winter First season, not divisible by 3 Month=4, Day=10 Season=Spring Second season, not divisible by 3 Month=7, Day=10 Season=Summer Third season, not divisible by 3 Month=10, Day=10 Season=Fall Fourth season, not divisible by 3 Month=3, Day=21 Season=Spring Second season, divisible by 3, boundary condition Month=6, Day=21 Season=Summer Third season, divisible by 3, boundary condition Month=9, Day=21 Season=Fall Fourth season, divisible by 3, boundary condition Month=12, Day=21 Season=Winter First season, divisible by 3, boundary condition Month=3, Day=20 Season=Winter First season, divisible by 3 Month=6, Day=20 Season=Spring Second season, divisible by 3 Month=9, Day=20 Season=Summer Third season, divisible by 3 Month=12, Day=20 Season=Fall Fourth season, divisible by 3
Prompt for and read month from user. Prompt for and read day from user. if month equals “January” if day equals 1 print “New Year’s Day” if month equals “July” if day equals 4 print “Independence Day” if month equals “November” if day equals 11 print “Veterans Day” if month equals “December” if day equals 25 print “Christmas Day”
if score >= 90 assign A else if score >= 80 assign B else if score >= 70 assign C else if score >= 60 assign D else assign F
When comparing strings lexicographically each letter in the two strings are compared from first to last with the following rules:
• Letters of the same case come in dictionary order.
• All uppercase letters come before lowercase letters.
• Space comes before all printable characters.
• Numbers come before letters.
• Punctuation also has order listed in Appendix A.
When one letter is found that comes before another, the string it belongs to is ordered before the other. Thus the sample strings given in the problem have the following order:
"Century 21" < "IBM" < "While-U-Wait" < "wiley.com"
a)"Jerry"
b) "Tom"
c) "Churchill"
d) "car manufacturer"
e) "Harry"
f) "Car"
g) "Tom"
h) "Car"
i) "bar"
In the case of an if/else if/else
sequence, one clause is guaranteed to be executed, while in the case of nested if
statements the internal clause is only true if all the if
statements are true.
As an example one of the following lines of code will be printed:
if (n > 10) { System.out.println("Greater than 10!"); } else if (n >= 0) { System.out.println("Between 0 and 10."); } else { System.out.println("Less than 0.") }
Whereas in this case the print will only execute if n
is both greater than or equal to 0 and less than or equal to 10:
if (n >= 0) { if (n <= 10) { System.out.println("Between 0 and 10."); } }
When comparing exact values the order of if/else if/else
statements does not matter:
if (n == 1) { System.out.println("1."); } else if (n == 2) { System.out.println("2."); } else { System.out.println("Something else."); }
When comparing ranges of values it can:
if (n > 10) { System.out.println("Greater than 10!"); } else if (n >= 0) { System.out.println("Between 0 and 10."); } else { System.out.println("Less than 0."); }
The condition rewritten to use < operators instead of >= operators:
if (richter < 4.5) { cout << "No destruction of buildings"; } else if (richter < 6.0) { cout << "Damage to poorly constructed buildings"; } else if (richter < 7.0) { cout << "Many buildings considerably damaged, some collapse"; } else if (richter < 8.0) { cout << "Many buildings destroyed"; } else { cout << "Most structures fall"; }
Changing the operators to < instead of >= forces the order of the options to be reversed, because of the order in which the comparisons are evaluated.
status income tax ============================== “Single” $1050.00 $105.00 “Single” $20000.00 $2600.00 “Single” $40000.00 $6400.00 “Married” $1050.00 $105.00 “Married” $20000.00 $2200.00 “Married” $70000.00 $10300.00 “Single” $8000.00 $800.00
This is an example of the dangling else problem:
if (gpa >= 1.5) if (gpa < 2) status = "probation"; else status = "failing";
When reading the code it may mistakenly appear that a student fails only when the GPA is less than 1.5, when in reality the code executes like this:
if (gpa >= 1.5) if (gpa < 2) status = "probation"; else status = "failing";
Now we see all students whose GPAs is over 2.0 are also listed as failing. To correct for this, we can add curly braces:
if (gpa >= 1.5) { if (gpa < 2) { status = "probation"; } } else { status = "failing"; }
p q r (p && q) || !r !(p && (q || !r)) false false false true true false false true false true false true false true true false true true false true true false false true false true false true false true true true false true false true true true true false
This is true if both A and B can be evaluated successfully. Otherwise it is not. For example, suppose A is
i < str.length()
and B is
str.substring(i, i + 1).equals("!")
Suppose further that i
is 6 and str
is "Hello!"
.
Then A && B
is false
because A is false
.
But B && A
causes an exception.
Boolean operations in search engines are spelled out in English while in Java they have symbolic replacements. For example OR is equivalent to “||
” in Java while AND NOT would be equivalent to a combination of “&&” and “!=
”.
a) false
b) true
c) true
d) true
e) false
f) false
g) false
h) true
a) b
b)!b
c)!b
d) b
a) b = (n == 0);
b) b = !(n == 0);
c) b = ((n > 1) && (n < 2));
d) b = (n < 1) || (n > 2);
The program attempts to read the integer before it actually tests to see if there’s an integer to read. To correct this problem the int quarters = in.nextInt();
line should be moved inside the body of the if
statement.
a) <blank line> * ** *** **** b) =====
*====
**===
***==
****= c) *****
*****
*****
*****
*****
*****
***** <infinite loop>
a) 0 10
1 9
2 8
3 7
4 6 b) <infinite loop>
a) 55 b) 6 c) 120 d) 64
a)
int i = 0; while (i * i < n) { System.out.println(i * i); i++; }
b)
int i = 10; while (i < n) { System.out.println(i); i = i + 10; }
c)
int i = 1; while (i < n) { System.out.println(i); i = i * 2; }
a)
int sumOfEvenNumbers = 0; for (int n = 2; n <= 100; n = n + 2) { sumOfEvenNumbers = sumOfEvenNumbers + n; } // sumOfEvenNumbers now has the sum of all even numbers from 2 to 100
b)
int sumOfSquares = 0; int currentN = 1; while (Math.pow(currentN, 2) <= 100) { sumOfSquares = sumOfSquares + Math.pow(currentN, 2); currentN++; } // sumOfSquares now has the sum of all squares from 1 to 100
c)
int sumOfOddNumbers = 0; for (int n = a; n <= b; n++) { if (n % 2 == 1) { sumOfOddNumbers = sumOfOddNumbers + n; } } //sumOfOddNumbers now has the value of all odd numbers between a and b
d)
int nLeft = n; int sumOfOddDigits = 0; while (nLeft > 0) { int digit = nLeft % 10; if (digit % 2 == 1) { sumOfOddDigits = sumOfOddDigits + digit; } nLeft = nLeft / 10; } // sumOfOddNumbers now has sum of all odd digits in n
a)
i j n 0 10 0 1 9 1 2 8 2 3 7 3 4 6 4 5 5 5
b)
i j n 0 0 0 1 1 1 2 2 4 3 3 9 4 4 16 5 5 25 6 6 36 7 7 49 8 8 64 9 9 81 10 10 100
c
i j n 10 0 0 9 1 8 8 2 14 7 3 18 6 4 20 5 5 20 4 6 18 3 7 14 2 8 8 1 9 0 0 10 -10
d)
As the trace table shows, i
will never equal j
since they pass each other at the 4-6 to 6-4 mark. The trace table stops right below this point to indicate it is an infinite loop.
i j n 0 10 0 2 8 1 4 6 2 6 4 3 8 2 4 ...
a) 1 2 3 4 5 6 7 8 9
b) 1 3 5 7 9
c) 10 9 8 7 6 5 4 3 2
d) 0 1 2 3 4 5 6 7 8 9
e) 1 2 4 8
f) 2 4 6 8
An infinite loop occurs when the terminating condition in the loop never evaluates to false
. How you stop an infinite loop on your computer depends on your operating system and your IDE. For example, in the Eclipse IDE there is a red “TERMINATE” button that will stop any Java program at any time.
first | value | minimum | output |
true | |||
false | 4 | 4 | |
0 | -5 | -5 |
An off-by-one error occurs when you incorrectly initialize or terminate a loop by one unit. A common example occurs when looping through a Java String
. The programmer may forget that character positions start at 0 rather than 1 and start his loop one character beyond the actual start of the String
.
A sentinel value is a particular value that is used to indicate the end of a sequence. By necessity the sentinel cannot be a valid member in the sequence. For example, an employer may be interested in the average age of her employees. She could write a program that reads a series of ages and terminates when it reads a negative number. Since there are no employees with a negative age it makes an appropriate sentinel value.
Java supports three types of loop statements: for
, do
, and while
. Use a for
loop if you know in advance how many times the loop should be repeated. Use a do
loop if the loop must be executed at least once. Otherwise, use a while
loop.
a) 10 times
b) 10 times
c) 10 times
d) 21 times
e) This is an infinite loop
f) 11 times
g) 7 times
Print out calendar header with days of week: Su M T W Th F Sa // The -2 indicates that the first week doesn’t start until Wednesday current day = -2 last day of month = 31 // Let 0 represent Su and 6 represent Sa weekday = 0 while (current day <= last day of month) if (current day > 0) Print current day followed by a space else Print three spaces Add one to current day Add one to weekday // Check to see if we’ve printed out a week, print a newline if we have if (weekday == 7) Print a newline to go to next week weekday = 0
Print out table header for (celsius = 0; celsius <= 100; celsius = celsius + 10) Print right aligned celsius Print a | character fahrenheit = (9/5) * celsius + 32 Print right aligned Fahrenheit Print newline
// Initialize current name to something other than -1 current name = "" read name from input into current name counter = 0 total score = 0 average score = 0 read next input into current score while (current score != -1) counter = counter + 1 add current score to total score read next input into current score average score = total score / counter print average score print newline
Trace Table:
name | current score | counter | total score | average score |
Harry Morgan | 94 | 1 | 94 | 0 |
71 | 2 | 165 | 0 | |
86 | 3 | 251 | 0 | |
95 | 4 | 346 | 0 | |
-1 | 0 | |||
86.5 |
// Initialize current name to something other than END current name = "" read name from input into current name while (current name != "END") current score = 0 total score = 0 read next input into current score while (current score != -1) add current score to total score read next input into current score print current name and total score print newline
Trace Table
name | current score |
total score |
Harry Morgan | 94 | 94 |
71 | 165 | |
86 | 251 | |
95 | 346 | |
-1 | ||
Sally Lin | 99 | 99 |
98 | 197 | |
100 | 297 | |
95 | 392 | |
90 | 482 | |
-1 |
int s = 0; int i = 1; while (i <= 10) { s = s + i; i++; }
int n = in.nextInt(); double x = 0; double s; s = 1.0 / (1 + n * n); n++; x = x + s; while (s > 0.01) { s = 1.0 / (1 + n * n); n++; x = x + s; }
a)
s | n |
1 | 1 |
2 | 1 |
3 | 1 |
4 | 1 |
5 | 1 |
6 | 1 |
7 | 1 |
8 | 1 |
9 | 1 |
10 | 2 |
b)
s | n |
1 | 1 |
2 | 2 |
4 | 3 |
7 | 4 |
11 |
c)
s | n |
1 | 1 |
2 | 2 |
4 | 3 |
7 | 4 |
11 | 5 |
16 | 6 |
22 | 7 |
29 | 8 |
37 | 9 |
46 | 10 |
56 | 11 |
67 | 12 |
79 | 13 |
92 | 14 |
106 | 15 |
121 | 16 |
137 | 17 |
154 | 18 |
172 | 19 |
191 | 20 |
211 | 21 |
a) 2 4 7 11 16
b) 4 9 16
c) 10 7
a) 10
b) 6
c) 3
d) 0
If a programmer needed to print a list of numbers starting from a
to b
it is easier to read if the for
loop has a
and b
as symmetric bounds, like this:
for (int i = a; i <= b; i++)
If a programmer needed to loop through all the characters in a string, it is easier to read if the loop has asymmetric bounds based on the length of the string, like this:
for (int i = 0; i < myString.length(); i++)
Storyboard for incompatible units.
What unit do you want to convert from? cm What unit do you want to convert to? gal Sorry, cannot convert from one unit to the other. What unit do you want to convert from? cm What unit do you want to convert to? in Enter values, terminated by zero: 10 10 cm = 3.94 in What unit do you want to convert from?
Storyboard showing how valid unit types can be displayed.
What unit do you want to convert from? leagues Sorry, invalid units. Valid unit types are: in, ft, mi, mm, cm, m, km oz, lb, g, kg tsp, tbsp, pint, gal, ltr What unit do you want to convert from? cm What unit do you want to convert to? in Enter values, terminated by zero: 10 10 cm = 3.94 in What unit do you want to convert from?
Storyboards from Section 6.6 with a new menu.
Converting a Sequence of Values What would you like to do? Enter 1 to convert units Enter 2 for program help Enter 3 to quit 1 What unit do you want to convert from? cm What unit do you want to convert to? in Enter values, terminated by zero 30 30 cm = 11.81 in 100 100 cm = 39.37 in 0 What would you like to do? Enter 1 to convert units Enter 2 for program help Enter 3 to quit Handling Unknown Units What would you like to do? Enter 1 to convert units Enter 2 for program help Enter 3 to quit 1 What unit do you want to convert from? cm What unit do you want to convert to? inches Sorry, unknown unit. What would you like to do? Enter 1 to convert units Enter 2 for program help Enter 3 to quit 1 What unit do you want to convert from? cm What unit do you want to convert to? inch Sorry, unknown unit. What would you like to do? Enter 1 to convert units Enter 2 for program help Enter 3 to quit 1 What unit do you want to convert from? cm What unit do you want to convert to? in 3030 cm = 11.81 in 100100 cm = 39.37 in 0 What would you like to do? Enter 1 to convert units Enter 2 for program help Enter 3 to quit Exiting the Program What would you like to do? Enter 1 to convert units Enter 2 for program help Enter 3 to quit 1 What unit do you want to convert from? cm What unit do you want to convert to? in Enter values, terminated by zero 30 30 cm = 11.81 in 100 100 cm = 39.37 in 0 What would you like to do? Enter 1 to convert units Enter 2 for program help Enter 3 to quit 3 (Program exits)
Flowchart for the units conversion program in Section 6.6.
You cannot initialize the largest
and smallest
variables to zero because it is possible that all of the values entered may be either all larger than zero or all smaller than zero.
For example, if we are looking for the maximum and set largest
to zero, and the values entered are -10.2, -8.1, and -7.6, the value of maximum never changes from zero, because none of the values entered is greater than zero. The maximum number of those entered should be -7.6, but the program would think it was 0.
Nested loops are loops contained in other loops. This sort of structure is common when having to process a table. One loop would process the rows while the other would process the columns in each row.
for (int i = 1; i <= width * height; i++) { System.out.print("*"); if (i % width == 0) { System.out.println(); } }
Java has a random number generator (Math.random()
) which generates random numbers from 0 up to 1 (exclusive). To generate a random hour, get a random number between 0 up to 1, multiply it by 12 and cast it to an int
; this gives you a random number between 0 and 11. Next, add 1 to that number to create a number between 1 and 12 which is appropriate for the hour.
The minutes are easier, simply generate a random number between 0 up to 1, multiply it by 60 and cast it to an int
.
This problem is easier to think about if you generate a random number to select which friend to visit. First generate a random number between 1 and 15 (Harry has 15 total friends). Next convert the friend numbers to state numbers. If the number is between 1 and 10, generate a 1 indicating California; if the number is between 11 and 13, generate a 2 indicating Nevada; otherwise generate a 3 indicating Utah.
The procedure depends on the debugger. Most debuggers know about the String
class and display its contents immediately when you ask to inspect or watch a string. However, you can also display the instance variables and inspect the value
instance variable.
This varies according to the debugger used. Typically, you inspect a variable of type Rectangle
and carry out some action (such as clicking on a tree node) to open up the display of the instance variables. The x
, y
, width
, and height
instance variables should then be visible.
This varies according to the debugger used. Typically, you inspect a variable of type BankAccount
and carry out some action (such as clicking on a tree node) to open up the display of the instance variables. The balance
variable should then be visible.
The “divide-and-conquer” strategy involves stepping over the methods in main
to pinpoint the location of the failure. When a failure occurs just after a particular method (say f
), then restart main
, set a breakpoint before f
, step into f
, and now apply the same strategy to f
. Keep going until the error is found.
a) int[] nums = new int[10]; b) nums[0] = 17; c) nums[9] = 29; d) for (int i = 1; i < 9; i++) {nums[i] = -1;} e) for (int i = 0; i < nums.length; i++) {nums[i]++;} f) for (int num : nums) {System.out.println(num);} g) for (int i = 0; i < nums.length; i++) { if (i < nums.length - 1) System.out.print(nums[i] + ","); else System.out.println(nums[i]); }
The index of an array specifies the array position in which the element can be read or set.
Legal index values start at 0 and go to the length of the array minus one.
A bounds error occurs when an array is referenced with an index that is outside the range of legal array index values.
The following is a program that contains a bounds error.
public class R6_12 { public static void main(String[] args) { int[] array = new int[10]; array[10] = 10; } }
When run it outputs the following error:
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 10 at R6_12.main(R6_12.java:6)
Scanner in = new Scanner(System.in); int myArray[10]; for (int i = 0; i < 10; i++) { System.out.println("Enter a number: "); myArray[i] = in.nextInt(); } for (int j = 9; j >= 0; j--) { System.out.print(myArray[j] + " "); }
a)
for (int i = 0; i < 10; i++) { values[i] = i + 1; }
b)
for (int i = 0; i <= 10; i++) { values[i] = i * 2; }
c)
for (int i = 0; i < 10; i++) { values[i] = (i + 1) * (i + 1); }
d)
for (int i = 0; i < 10; i++) { values[i] = 0; }
e)
int[] values = {1, 4, 9, 16, 9, 7, 4, 9, 11};
f)
for (int i = 0; i < 10; i++) { values[i] = i % 2; }
g)
for (int i = 0; i < 10; i++) { values[i] = i % 5; }
a) 25
b) 13
c) 12
d) This loop condition causes an out-of-bounds index error. If the condition were i < 10
, total
would be 22.
e) 11
f) 25
g) 12
h) -1
a) { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }
b) { 1, 1, 2, 3, 4, 5, 4, 3, 2, 1 }
c) { 2, 3, 4, 5, 4, 3, 2, 1, 0, 0 }
d) { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }
e) { 1, 3, 6, 10, 15, 19, 22, 24, 25, 25 }
f) { 1, 0, 3, 0, 5, 0, 3, 0, 1, 0 }
g) { 1, 2, 3, 4, 5, 1, 2, 3, 4, 5 }
h) { 1, 1, 2, 3, 4, 4, 3, 2, 1, 0 }
To generate an array with ten random numbers between 1 and 100:
for (int i = 0; i < 10; i++) { values[i] = (int) (Math.random() * 100 + 1); }
To generate an array with ten different random numbers between 1 and 100:
for (int i = 0; i < 10; i++) { values[i] = (int) (Math.random() * 100 + 1); // Check to see if number has been generated before int count = 0; for (int j = 0; j < i; j++) { if (values[j] == values[i]) { count++; } } if (count > 0) { i--; // if it has, back up and try again } }
Below, data
is an array.
int min = data[0]; int max = data[0]; for (Integer val : data) { if (val > max) { max = val; } if (val < min) { min = val; } }
a) The loop iterates over the values 1 to 10 which in turn are used as array indices. Yet, the length of the array is 10, thus its indices range from 0 to 9.
b) The programmer forgot to initialize the array values. One would expect a statement like int[] values = new int[10]
; or however many elements the programmer desired.
a)
for (Object object : array) { System.out.print(object.toString()); }
b)
int max = array[0]; for (Object object : array) { if (object > max) { max = object; } }
c)
int count = 0; for (Object object : array) { if (object < 0) { count++; } }
a)
for (int i = 0; i < values.length; i++) { total = total + values[i]; }
b)
for (int i = 0; i < values.length; i++) { if (values[i] == target) { return true; } }
c)
for (int i = 0; i < values.length; i++) { values[i] = 2 * values[i]; }
a)
for (double x : values) { total = total + x; }
b)
int pos = 0; for (double x : values) { if (pos >= 1) { total = total + x; } pos++; }
c)
int pos = 0; for (double x : values) { if (x == target) { return pos; } pos++; }
a) ArrayList
can't take a Java primitive as a type, rather it needs a wrapper class, in this case Integer
.
b) In this case the new ArrayList
did not define its generic type. One would expect to see new ArrayList<Integer>();
as the initial value. In Java 7, however, the syntax shown is acceptable.
c) Parentheses () are required after new ArrayList<Integer>
.
d) The initial size of the ArrayList
already is 0 elements, thus the set
method cannot be used to set them.
e) The ArrayList
reference values
is not initialized. The code = new
ArrayList<Integer>();
should be to the right of the declaration.
The headers of the described methods.
a) public void sortDecreasing(int[] arr, int currentSize)
b) public void printWithString(int[] arr, int currentSize, string sep)
c) public int numItemsBelow(int[] arr, int currentSize, int value)
d) public void removeItemsLessThan(int[] arr, int currentSize, int value)
e) public void copyLessThan(int[] source, int firstSize, int[] target, int secondSize, int value)
i output 0 32 1 | 54 2 | 67.5 3 | 29 4 | 35
element | matches |
110 | {110} |
90 | {110} |
100 | {110} |
120 | {110, 120} |
80 | {110, 120} |
pos | found |
0 | false |
1 | false |
2 | false |
3 | true |
pos | found |
0 | false |
1 | false |
2 | false |
3 | false |
4 | false |
5 | true |
current size | i | values |
5 | {110,90,100,120,80} | |
5 | 3 | {110,90,100,120,80} |
5 | 4 | {110,90,100,80,80} |
4 | 5 | {110,90,100,80,80} |
Copy the first element into a variable, x. Loop through the first length – 2 positions of the array using pos as a counter Copy the element at pos + 1 to the element at pos. Copy x into the last position of the array.
pos = 0 while pos < length of array if the element at pos is negative remove the element at pos. else increment pos.
// x is the element to insert pos = 0 inserted = false while pos < length of array and not inserted if the element at pos is less than x insert x at pos. inserted = true. else increment pos. if not inserted insert x at the end of the array.
longestRun = 0 pos = 0 while pos < length of array - 1 if element at pos is equal to element at pos + 1 currentRun = 0 currentElement = element at pos while pos < length of array - 1 and currentElement equals element at pos increment pos increment currentRun if currentRun > longestRun longestRun = currentRun else increment pos print longestRun
The values
variable is a reference to another array. Setting it equal to numbers
causes the values
reference to point to the numbers
array, but it does not change the value of the object originally referred to by values
.
To find the smallest rectangle containing the points defined by the two arrays, compute the max and min of the x-values and the max and min of the y-values. With those four values, you can define the locations of the x- and y-coordinates of the rectangle as follows:
Upper left corner: (min x, max y)
Lower left corner: (min x, min y)
Upper right corner: (max x, max y)
Lower right corner: (max x, min y)
If the array is already sorted, we no longer need to find the position of the lowest quiz score. If the array is sorted from lowest to highest, then the lowest quiz score is in the first position in the array. Technically, we can even compute the sum without actually removing the lowest element, because it is always in the first location. We can find the sum simply by starting the loop at position 1 instead of position 0:
public double sum(double[] values) { double total = 0.0; // Start loop count at 1 to skip lowest score for (int n = 1; n < values.length; n++) { total = total + values[n]; } return total; }
Pseudocode for an algorithm using “removes” and “inserts” instead of swaps.
i = 0 j = size / 2 while (i < size / 2) Remove item at position j. Insert removed item at position i. i++ j++
I will try this algorithm out with four coins, a penny (P), a nickel (N), a dime (D), and a quarter (Q).
Position 0 1 2 3 P N D Q i = 0, j = 2, Remove coin at position j, insert at position 0 Increment i and j. Position 0 1 2 3 D P N Q i = 1, j = 3, Remove coin at position j, insert at position 1 Increment i and j. Position 0 1 2 3 D Q P N i = 2, j = 4.
The reason this is always less efficient that using the swapping algorithm is that our new remove/insert algorithm above requires two method calls (one for the remove, and one for the insert) each time a coin is removed. In the swapping algorithm, one method call (the swap) moves both coins at the same time.
Another way to look at it is that each time you remove a coin and each time you insert one, you have to move elements in the array to new locations. (If you remove an element, all the elements above it must move down one. If you insert, all the elements above it must move up one.) When you do this as a single swap operation, only the two elements affected are moved. The other elements do not have to move during a swap.
When I laid the coins and paper clips out as described in this problem (a series of coins each with a number of paperclips beneath it), I envisioned a two-dimensional array with N rows and 2 columns. The first column held the value of the coin (whether it was a penny, nickel, dime, or quarter) and the second column held a cumulative count corresponding to the number of that type of coin in column 1. For instance, if I had a total of 10 coins consisting of 3 pennies (P), 2 nickels (N), 4 dimes (D), and 1 quarter (Q), my initial two-dimensional array might look like this (with all of the “counts” in the second column set to zero):
D0D0P0Q0P0N0D0N0D0P0
Then my algorithm for counting the coins would use a nested loop like this:
Loop (int i = 0; i < 10; i++) Loop (int j = 0; j < 10; j++) if coins[j][0] equals coins[i][0] Increment the count at location coins[j][i]. End inner loop. End outer loop.
In other words, you look at the coin in the first location (a dime), and then walk through the two-dimensional array in the inner for loop, incrementing the count of any dime you find in the array. Then you look at the second coin (also a dime), and loop through the inner for loop again, incrementing the count for any dimes you find, and so on.
When you have walked through the entire array in this manner, your final two-dimensional array should look like this:
D4D4P3Q1P3N2D4N2D4P3
Then it is a simple matter of looping through the array, using the algorithms given in this chapter, to find the position of the element with the maximum count in the second column.
for (int i = 0; i < ROWS; i++) { for (int j = 0; j < COLUMNS; j++) { values[i][j] = 0; } } for (int i = 0; i < ROWS; i++) { for (int j = 0; j < COLUMNS; j++) { values[i][j] = (i + j) % 2; } } for (int j = 0; j < COLUMNS; j++) { values[0][j] = 0; values[ROWS - 1][j] = 0; } int sum = 0; for (int i = 0; i < ROWS; i++) { for (int j = 0; j < COLUMNS; j++) { sum = sum + values[i][j]; } } for (int i = 0; i < ROWS; i++) { for (int j = 0; j < COLUMNS; j++) { System.out.print(values[i][j] + " "); } System.out.println(); }
Assume the two-dimensional array, data
, has M rows and N columns:
Loop from row=0 to row=M Loop from column=0 to column=N If row is 0 or M Set data[row][column] equal to -1. Else if column is 0 or N Set data[row][column] equal to -1. End inner loop. End loop.
When traversing backward, the indices of the array list have to be decremented (instead of incremented) in the for loop. This process continues while the index i
is greater than zero (0). When an object is removed from the array only the indices of the objects greater than the index removed are effected. The loop is only working with the indices less than the index of the object removed, so there is no issue.
a) True.
b) False.
c) False.
d) False.
e) False.
f) True.
g) True.
a) Verify that the lengths are equal, and then set a Boolean false if any mismatch occurs.
boolean equal = true; if (data1.size() != data2.size()) { equal = false; } for (int i = 0; i < data1.size() && equal; i++) { if (data1.get(i) != data2.get(i)) { equal = false; } }
b) Create a second array list that is empty, then loop over the first:
ArrayList<Integer> data2 = new ArrayList<Integer>(); for (int i = 0; i < data1.size(); i++) { data2.add(data1.get(i)); }
c) Loop over all positions in the array list and set each one to 0:
for (int i = 0; i < data.size(); i++) { data.set(i, 0); }
d) Loop while the array list still has elements in it and remove the element at position 0:
while (data.size() > 0) { data.remove(0); }
More simply, one can call ArrayList
’s clear
method:
data.clear();
a) True
b) True
c) False
d) True
e) False
f) False.
Regression testing is testing done to ensure changes to code haven't broken any previously existing functionality. A test suite is a set of tests for the code that check if existing functionality works.
Debugging cycling is a phenomenon where an issue is resolved that is later seen again after another issue's fix breaks the original fix for the resurfaced issue.
Student answers will vary. The four main classes that would be expected would be:
Student answers will vary. The main expected classes for this system would be:
VendingMachine would be an appropriate name for the class because it a) simulates a vending machine, and b) has functionality that matches vending machine functionality exactly, without more or less functions.
PriceChecker would not be an appropriate name for the class because while it does check the price, it also performs a transaction.
ChangeGiver would not be an appropriate name for the class because while it does give change when too much money is given, it will return the money paid if there is not enough.
a) Invoice would be a good class to use if the goal was to keep track of the invoice as a digital record. The application only takes the information in to print the invoice, so this could be misleading.
b) InvoicePrinter is a good class to use for this application because it describes exactly the functionality of the application.
c) PrintInvoice works as a description of the application, but might not be the best choice because it sounds more like a function or an action than an entire class.
d) InvoiceProgram would be a good class to use if there were more than one action the application could perform. Using the word "program" implies that there are multiple possible functions of the application, whereas one could more easily use the single action provided by the application in its name.
Actor Class - PaycheckComputer
Non-Actor Class - Payroll
The difference between the two classes if the implied functionality. The actor class defines its functional capacity of the class within its name, whereas the non-actor class only provides the general description of the functionality.
The System class is not cohesive because it includes many features that are unrelated, such as console I/O, garbage collection, and the time in milliseconds.
The Integer class depends on the String class.
The class Rectangle depends on the Rectangle2D, Point, Dimension, and String classes.
boolean hasNext() - Accessor
boolean hasNextDouble() - Accessor
boolean hasNextInt() - Accessor
boolean hasNextLine() - Accessor
String next() - Mutator
double nextDouble() - Mutator
int nextInt() - Mutator
String nextLine() - Mutator
Accessor methods: contains createIntersection createUnion equals getBounds getBounds2D getHeight getLocation getSize getWidth getX getY intersection intersects isEmpty outcode toString union Mutator methods: add grow setBounds setLocation setRect setSize translate
The Resistor class in problem P8.8 is immutable because all of its functions are accessors.
Of the three class, Rectangle, String, and Random, only class String is immutable.
Of the three classes PrintStream, Date, and Integer, the Integer class is immutable.
The side effect of the read() method is that it modifies the Scanner parameter that is passed in. A redesign would be to use the Scanner object within a main() method that passes in strings one at a time to the DataSet object.
public void print()
The side effect is modifying System.out to print on the console.
public void print(PrintStream stream)
The side effect is modifying the stream parameter.
public String toString()
There is no side effect.
If no function (including main) has a side effect, then you could not observe the program doing anything. Such a program would be useless. (Note that producing output on the screen is a side effect.)
When you call falseSwap, then a is initialized with 3 and b is initialized with 4. At the end of the falseSwap method, a is 4 and b is 3. Then the method exits and its local variables (including the parameter variables) are forgotten. The contents of x and y are not affected.
public static void swap(Point2D.Double p) { p.setLocation(p.getY(), p.getX()); } public static void main(String[] args) { double x = 3; double y = 4; Point2D.Double p = new Point2D.Double(x, y); swap(p); x = p.getX(); y = p.getY(); System.out.println(x + " " + y); }
TODO
TODO
We get the error message "non-static method print(int) cannot be referenced from a static context" because the print method is not declared as static. If you change the header of the method to public static void print(int x), then the program will work. The reason the method needs to be declared as static is because we are calling it without an object reference (implicit parameter), but only static methods can be called like that.
decode getInteger highestOneBit lowestOneBit numberOfLeadingZeros numberOfTrailingZeros parseInt reverse reverseBytes rotateLeft rotateRight signum toBinaryString toHexString toOctalString toString // all of the toString variations, except toString() valueOf
They are static methods because these methods do not need an implicit parameter.
All of the valueOf methods in the String class are static methods. Like the methods in the Integer class, these methods are static because these methods do not operate on an object and have only explicit parameters. They create a new String instead of modifying an existing String (implicit parameter, which these methods do not need). The format methods are also static, for the same reason.
Student answers will vary. The primary objective is to break down the large task into sub-tasks. For example:
It is not a good design because using public static variables is not a good idea; they can accidentally get overwritten in large programs. A better way to do this is to have static methods System.getIn()
and System.getOut()
that return these streams.
To write a Java program without import statements, the user needs to specify the path names of the classes that are used in the program.
/** A component that draws two rectangles. */ public class RectangleComponent extends javax.swing.JComponent { public void paintComponent(java.awt.Graphics g) { // Recover Graphics2D java.awt.Graphics2D g2 = (java.awt.Graphics2D) g; // Construct a rectangle and draw it java.awt.Rectangle box = new java.awt.Rectangle(5, 10, 20, 30); g2.draw(box); // Move rectangle 15 units to the right and 25 units down box.translate(15, 25); // Draw moved rectangle g2.draw(box); } }
The default package is the package that contains the classes with no package specifier. All classes that we have programmed up to this point were in the default package.
The exception is reported, and the remaining methods continue to be executed. This is an advantage over a simple tester class whose main method would terminate when an exception occurs, skipping all remaining tests.
a) HourlyEmployee, SalariedEmployee
b) SalariedEmployee
c) super class: Employee, sub class: Manager
d) HourlyEmployee, SalariedEmployee
e) none
f) name, hourlyWage
a) Superclass: Employee
Subclass: Manager
b) Superclass: Student
Subclass: GraduateStudent
c) Superclass: Person
Subclass: Student
d) Superclass: Employee
Subclass: Professor
e) Superclass: BankAccount
Subclass: CheckingAccount
f) Superclass: Vehicle
Subclass: Car
g) Superclass: Vehicle
Subclass: Minivan
h) Superclass: Car
Subclass: Minivan
i) Superclass: Vehicle
Subclass: Truck
It's not useful because in terms of inventory, toasters, car vacuums, and travel irons all behave the same. There are a certain number of them, and they cost a certain amount.
ChoiceQuestion
inherits the following methods from its superclass:
setText setAnswer checkAnswer
It overrides the following method:
display
And it adds the following methods:
addChoice
SavingsAccount
inherits the following methods from its superclass:
deposit getBalance
It overrides the following methods:
withdraw monthEnd
It adds the following method:
setInterestRate
CheckingAccount
has a single instance variable:
private int withdrawals;
a)legal
b) not legal
c) not legal
d) legal
Answers may vary depending on one's definition of a pickup truck (is it a car or truck?) and motorcycle (is it a bicycle with an engine?).
Answers may vary depending on one's definition of a seminar speaker.
The (BankAccount) x
cast is casting the variable type of the object without changing its value whereas the (int) x
cast can actually change the underlying primitive value.
a)true
b) true
c) false
d) true
e) false
f) false
a) a-b = -294967296 b) b-a = 294967296 c) Integer.compare(a, b) = 1 d) Integer.compare(b, a) = -1
a) a-b = 0.3 b) b-a = -0.3 c) Double.compare(a, b) = 1 d) Double.compare(b, a) = -1
The following require a cast:
c = i; // c = (C) i; i = j; // i = (I) j;
None of them will throw an exception.
The following are legal:
a. e = sub;
c. sub = (Sandwich) e;
The following statement will compile but throw an exception at run time.
f. e = (Edible) cerealBox;
a. Rectangle a = r;
b. Shape b = r;
f. Serializable f = r;
g. Object g = r;
The call Rectangle r = s.getBounds();
is an example of polymorphism because the Shape
interface declares the method, and each class that implements the interface (Rectangle2D.Double
, Ellipse2D.Double
, Line2D.Double
, etc.) provides its own implementation of the method. The correct implementation is picked at run time.
The Employee class must
1) implement Measurable and
2) include a method public double getMeasure()
To use the second solution in 10.4, you
1) create an interface Measurer that defines a callback method (measure) and
2) you create a small helper class with the method that tells the average method how to measure the objects public double measure(Object anObject)
The callback method decouples your class with other classes. It is a more generic and flexible solution . It is no more difficult to implement than a pure interface solution.
You will get a compiler error. The String class does not implement the Measurable interface.
A callback is objtained by implementing the Measurer interface. Provide a class StringMeasurer that implements Measurer.
public class StringMeasurer implements Measurer { public double measure(Object anObject) { string aString = (String) anObject; double length = aString.length(); return length; } }
Now you need to construct an object of the StringMeasurer class and pass it to the average method.
Measurer stringMeas = new StringMeasurer(); String[] strings = { . . . }; double averageLength = Data.average(strings, stringMeas);
You will get an error. When the callback method is used, a String
object will be passed to a method that id designed for calculating the area of a Rectangle
object. String
objects do not have getWidth()
and getHeight()
methods.
The f
method can access the variables b
, t
, and x
.
The compiler gives an error saying that the local variable is accessed from within inner class and needs to be declared final
:
local variable a is accessed from within inner class; needs to be declared final
If we change the variable so that it is declared as final
, then the inner class can access it, provided it does not try to assign a new value.
We would need to put each class (InvestmentViewer1
and AddInterestListener
) in its own file. With this change, the class AddInterestListener
is no longer able to access the account
variable. Thus, we need to add a "private BankAccount account"
variable to the class AddInterestListener
, and have it receive the bank account in the constructor.
An event is an external activity to which a program may want to react. For example, "user clicked on button X" is an event.
An event source is the user-interface component that generates a particular event. Event sources report on events. When an event occurs, the event source notifies all event listeners.
An event listener belongs to a class that is provided by the application programmer. Its methods describe the actions to be taken when an event occurs.
With a console application, the programmer is in control and it can ask the user for input, in the order that is most convenient for the program.
With a graphical user interface application, the programmer lays out the various elements for user input. Then the user is in control. The user can click and type into the components in any order, and the programmer must be able to cope with that variety.
An ActionEvent
is generated when the user-interface library has detected a particular user intent, such as clicking on a button or hitting ENTER
in a text field.
A MouseEvent
is generated whenever the user moves or clicks the mouse.
An ActionListener
is only interested in one notification: when the action happens.
A MouseListener
has multiple methods because there are several potentially interesting mouse events, such as pressing, releasing, or clicking the mouse button.
Yes; a class can be the event source for multiple event types. For example, a JButton
is the event source for both mouse events and action events.
You can listen to the mouse events of a button, simply by installing a mouse listener:
button.addMouseListener(mouseListener);
You might want to do that for example to make the button glow in a different color whenever the mouse hovers over it.
Every event carries the source object. You can retrieve it with the getSource
method.
A mouse event has the following additional information:
a) the x- and y- component of the mouse position and b) the click count
An action event has the following additional information:
a) the command string associated with the action and b) the modifier keys held down during the action event
Hint: This information can be found in the API documentation.
Event listeners often need to access instance variables from another class. An inner class can access the instance variables of the outer class object that created it. Thus, it is convenient to use inner classes when implementing event listeners.
If Java had no inner classes, we could pass the values of instance variables needed to be accessed to the event listener constructor, so that local references/copies can be stored in the event listener object.
The paintComponent
method is called by the GUI mechanism whenever it feels that a component needs to be repainted. That might happen, for example, because the user just closed another window that obscured the component.
A programmer calls the repaint
method when the programmer feels that the component needs to be repainted (for example, if the state of the object has changed). That call is a request to the GUI mechanism to call paintComponent
at an appropriate moment.
A frame is a window to which you can add a component to be displayed on the screen. A frame can be displayed on its own, even if it is empty. However, we cannot simply add multiple components directly to a frame-they would be placed on top of each other. A panel is a container to group multiple user-interface components together. A panel needs to be added to a frame to be displayed.
If you open a file for reading that doesn't exist, Java will throw a FileNotFoundException
.
If you open a file for writing that doesn't exist, Java will create a new empty file.
Java will throw a FileNotFoundException
whose error message says "(Access is denied)".
When the program ends any unwritten data in the buffer will not be written to the file. Closing the PrintWriter flushes the buffer to the file before closing the file.
You need to use an escape character (an extra backslash) before the backslash, like this:
String filename = "c:\\temp\\output.dat";
args[0]: -Dname=piglet args[1]: -I\eeyore args[2]: -v args[3]: heff.txt args[4]: a.txt args[5]: lump.txt
(The original answer is misleading. First, throwing an exception does not create a new exception. The new expression is still the means to create the exception. Second, the method does not halt unless the exception is not caught within the method.)
An exception is thrown to report an error. When an exception is thrown, control continues at the nearest enclosing exception handler that is capable of handling the specified exception type. If no such handler exists, then the program terminates.
Catching an exception is the means by which to handle the reported error. An exception is caught and handled (processed), ideally, at a point in the program where the error can be addressed.
A checked exception indicates something beyond your control has gone wrong. Methods that throw these types of exceptions must specify that they do so by using the throws
reserved word. An example is FileNotFoundException
.
An unchecked exception indicates an error in the code and does not need to be explicitly handled with a try-catch block. An example is IndexOutOfBoundsException
.
Because IndexOutOfBoundsException
is an unchecked exception, and by definition unchecked exceptions do not need to be declared by the throws
reserved word. (These exceptions are caused by errors in code that a programmer should have detected during testing.)
The next line of code processed after a throw
statement is the first line in the first catch
block hierarchy that processes that type of exception.
If an exception does not have a matching catch
clause, the current method terminates and throws the exception to the next higher level. If there is no matching catch
clause at any higher level, then the program terminates with an error.
Your program can do anything with the exception object that it chooses to. It can print it to System.out
, ignore it, or anything else that is legal to program into the catch
block.
Not always. It's possible that the type of the exception handled in the catch
block is an "ancestor" of the exception type that is actually passed into it. This is legal in Java since a variable of superclass type can always reference a subclass object.
When using the try-with-resources statement, the close method is called on the variable when the try-block is completed. If an exception occurs, the close method is called before it is passed to the handler.
try (PrintWriter out = new PrintWriter(filename)) { writeData(out); } //out.close() is always called
It depends on the exception type being caught by the catch clause. The close method of the Closeable interface throws exceptions of type IOException while the close method of the AutoCloseable interface throws exceptions of type Exception.
next
can throw a NoSuchElementException
if no more tokens are available or an IllegalStateException
if the scanner is closed.
nextInt
can throw everything that next
can plus an InputMismatchException
if the next token does not match the Integer regular expression, or is out of range.
These are all unchecked exceptions.
Because the first line of the file is a 1, readData
constructs an array to hold one value and, after the next line is read from the file, the program throws an IOException
because it expected to reach the end of the file. The error report could be improved by printing the number of elements that the program expected to read. Then it becomes obvious that the input file does not indicate the correct number.
As the program is set up, no. But readFile
can throw a NullPointerException
if it is passed a null
value for the String
filename argument. However, the program prevents this from occurring because the filename is initialized from in
, which always returns a non-null value.
If the PrintWriter
construction is left outside the try
block, the compiler complains because the FileNotFoundException
must be caught. The compiler also complains that the IOException
is never thrown in the body of the corresponding try
statements.
If we move the construction to inside the try
block, then the FileNotFoundException
exception would be caught by the IOException
catch
block. The modified code does not work correctly if the close
method throws an exception, because it would not be caught by the catch
block.
This book recommends the following object-oriented development process:
1. Gather program requirements.
2. Discover classes.
3. Determine the responsibilities of each class and identify collaborating classes.
4. Determine the relationships between the classes.
5. Document the behavior of classes using javadoc comments.
6. Implement classes.
Classes correspond to nouns in the task description.
Methods correspond to verbs in the task description.
After discovering a method, it is important to identify the responsible object because it may need more than one method to carry out the task, and it may need to collaborate with other classes.
University-Student
: aggregation; a university has students
Student-TeachingAssistant
: inheritance; a teaching assistant is a student
Student-Freshman
: inheritance: a freshman is a student
Student-Professor
: neither
Car-Door
: aggregation; a car has doors
Truck-Vehicle
: inheritance; a truck is a vehicle
Traffic-TrafficSign
: no relationship
TrafficSign-Color
; no relationship. (Color
is an attribute)
The class BMW
can inherit from the class Vehicle
-every BMW is a vehicle. However, the BMW company (which is different from the class of all BMWs) is an object of the class VehicleManufacturer
. Inheritance is not appropriate for describing the relationship between an instance of a class (an object) and a class.
The Circle.setLocation
method needs to move the center of the circle; the radius is not affected. That is exactly what Point.setLocation
does, so the method can be inherited.
However, a circle isn't-a point, so it doesn't make conceptual sense to use inheritance.
The other way around, it makes some conceptual sense. A point is a circle with radius 0. But then it becomes difficult to construct a circle using a point and a radius, since a point is defined only in terms of a circle. It makes more sense to define a class Point
and a separate class Circle
.
Coinget value get name CashRegisterrecord purchaseCoinenter payment give change
Quizadd question Questionpresent questions Questionset question textStringset answer check answer display
Countryget area get density get name get population CountryReaderread file get largest areaCountryget largest density get largest population
Country.html
CountryReader.html
Student.htmlCourse.htmlReportCard.htmlGrade.html
One would expect a VendingMachine
, Product
class and Coin
class.
Answers can vary, but a possible design could use an Employee
class to keep track of hourly rates and hours worked as well as a Paycheck
class that would use an Employee
class to generate a paycheck.
Recursion solves a problem by using the solution to the same problem with simpler values.
Iteration uses some form of a loop (for
loop, while
loop) to solve a problem.
Infinite recursion occurs when the recursion never stops. A method calls itself over and over again and never reaches an end.
A recursive helper method is a recursive method that is called by another, usually non-recursive, method.
If the array only has one element, return that element.
Otherwise, recursively find the smallest element of the array that is obtained by removing the last element. Then return the smaller of the last element and the value returned by that recursive call.
(Similar to Quicksort)
Choose a random pivot element.
Partition the array into [sub-array1], [pivot], [sub-array2] where sub-array1 has elements less than pivot and sub-array2 has elements greater than pivot.
Check size of sub-array1.
If it is greater than k, then recurse with only sub-array1. If it is equal to k-1, then the pivot is the kth element. If it is less than k , then recurse with only sub-array2.
If the array has no elements or only one element, you are done.
Otherwise, first find the smallest element in the array. After obtaining the smallest number, swap that number with the first element in the array and recursively sort the remaining numbers in the array.
If the array only has one element, return that element.
Otherwise, recursively find the subarray that is obtained by removing the first element. Then return the mergesort of the first element and the value returned by that recursive call.
x0 = 1
xn = x * xn-1
x0 = 1
x2n + 1 = x * x2n, (odd case)
x2n = (xn)2, (even case)
The approach is significantly faster because it reduces the calls to "pow" to as little as 2 + log2n, when n is a power of 2.
For example:
Using the first method:
x1023 took 1024 calls
x1024 took 1025 calls
Using the second method:
x1023 took 20 calls
x1024 took 12 calls
0! = 1 n! = n * (n - 1)!
When computing fib(n)
, the function is called 2 * fib(n) - 1
times, as fibCount indicates.
import java.util.Scanner; /** This program computes Fibonacci numbers using a recursive method. */ public class FibTester { private static int fibCount; public static void main(String[] args) { Scanner in = new Scanner(System.in); System.out.print("Enter n: "); int n = in.nextInt(); for (int i = 1; i <= n; i++) { fibCount = 0; long f = fib(i); System.out.println("fib(" + i + ") = " + f); System.out.println("number of times fib(n) is called = " + fibCount); } } /** Computes a Fibonacci number. @param n an integer @return the nth Fibonacci number */ public static long fib(int n) { fibCount++; if (n <= 2) { return 1; } else { return fib(n - 1) + fib(n - 2); } } }
moves(1) = 2n - 1
To guess this formula, compute:
moves(2) = 2 * moves(1) + 1 = 3
moves(3) = 2 * moves(2) + 1 = 7
moves(4) = 2 * moves(3) + 1 = 15
moves(5) = 2 * moves(4) + 1 = 31
The formula can then be verified by induction.
moves(1) = 1 = 21 - 1
moves(n) = 2 * moves(n -1) + 1 = 2 * (2n -1-1) + 1 = 2n-1
If n is 1, return a collection containing the empty set and the set { 1 }.
Otherwise, first find all subsets of the set { 1 ... n-1 }. For each subset S in that collection, add two sets to the answer, namely S and S union {n}.
This algorithm begins with the numbers from 0 to n - 1 in ascending order. It then progresses until the numbers are in descending order at which point 'hasMorePermutations' returns false. At each step a new permutation is made such that the new sequence is lexicographically greater than the previous (e.g., 132 is lexicographically greater than 123; for this specific sequence of numbers one can think more directly of the step as creating a new permutation that is greater than the previous).
A new permutation is generated by finding in the previous permutation the rightmost pair of ascending values (i.e., the pair of ascending values that is nearest to the end of the sequence). If such a pair does not exist, then the final permutation has already been discovered (that in which the sequence is descending). If such a pair is found, then the rightmost value that is greater than the first of the pair is found. This is either the second value of the pair or a value to the right of the pair.
If the value found is the second of the pair, then the remainder of the sequence is descending. In this case, the two values of the pair are swapped and the remainder of the sequence is reversed (so that it is now ascending). This remaining portion will then be permuted to continue the lexicographical orderings.
If the value found is not the second of the pair, then it is the largest of the descending "tail" of the sequence and, thus, the next lexicographic option for the position of the first element of the pair. The tail is reversed to continue the lexicographic orderings.
3-4+5
(Previous answer assumed ()s around 3 - 4.)
getExpressionValue
calls getTermValue
getTermValue
calls getFactorValue
getFactorValue
returns 3
getTermValue
returns 3
getExpressionValue
consumes
-
getExpressionValue
calls getTermValue
getTermValue
calls getFactorValue
getFactorValue
returns 4
getTermValue
returns 4
getExpressionValue
consumes
+
getExpressionValue
calls getTermValue
getTermValue
calls getFactorValue
getFactorValue
returns 5
getTermValue
returns 5
getExpressionValue
returns 4 (-1 + 5)
3-(4+5)
getExpressionValue
calls getTermValue
getTermValue
calls getFactorValue
getFactorValue
returns 3
getTermValue
returns 3
getExpressionValue
consumes -
getExpressionValue
calls getTermValue
getTermValue
calls getFactorValue
getFactorValue
consumes the ( input
getFactorValue
calls getExpressionValue
getExpressionValue
calls getTermValue
getTermValue
calls getFactorValue
getFactorValue
returns 4
getTermValue
returns 4
getExpressionValue
consumes
+
getExpressionValue
calls getTermValue
getTermValue
calls getFactorValue
getFactorValue
returns 5
getTermValue
returns 5
getExpressionValue
returns 9
getFactorValue
consumes the ) input
getFactorValue
returns 9
getTermValue
returns 9
getExpressionValue
returns -6 (3 - 9)
(3-4)*5
getExpressionValue
calls getTermValue
getTermValue
calls getFactorValue
getFactorValue
consumes the ( input
getFactorValue
calls getExpressionValue
getExpressionValue
calls getTermValue
getTermValue
calls getFactorValue
getFactorValue
returns 3
getTermValue
returns 3
getExpressionValue
consumes
-
getExpressionValue
calls getTermValue
getTermValue
calls getFactorValue
getFactorValue
returns 4
getTermValue
returns 4
getExpressionValue
returns -1
getFactorValue
consumes the ) input
getFactorValue
returns -1
getTermValue
consumes
*
getTermValue
calls getFactorValue
getFactorValue
returns 5
getTermValue
returns -5 (-1 * 5)
getExpressionValue
returns -5
3 * 4 + 5 * 6
getExpressionValue
calls getTermValue
getTermValue
calls getFactorValue
getFactorValue
returns 3
getTermValue
consumes
*
getTermValue
calls getFactorValue
getFactorValue
returns 4
getTermValue
returns 12 (3 * 4)
getExpressionValue
consumes +
getExpressionValue
calls getTermValue
getTermValue
calls getFactorValue
getFactorValue
returns 5
getTermValue
consumes
*
getTermValue
calls getFactorValue
getFactorValue
returns 6
getTermValue
returns 30 (5 * 6)
getExpressionValue
returns 42 (12 + 30)
Searching means to find an element in a collection of elements. Sorting means to arrange a collection of elements in a particular order.
Array length 0 or 1: i < a.length - 1
is not true when i
equals 0, the for
loop in the sort
method never executes and the array is unchanged. That is ok.
Array length 2: The for
loop in sort
executes once, with i
= 0. minimumPosition(a, 0)
is called. The for
loop in that method executes with from = i
and going from 1 to less than 2; i.e., that loop also executes once. minPos
is initially 0. If a[1]
is less than a[0]
, then minPos
is set to 1. When the method returns, the two values are swapped, which causes the array to be sorted.
Array length 3: There are six possible variations of the array. Using 1, 2, 3 for the three elements, they are:
1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1
Here is a walk-through for the last scenario. The others are similar.
sort minimumPosition a[0] a[1] a[2] i from minPos i 3 2 1 0 0 0 1 3 2 1 0 0 1 2 3 2 1 0 0 2 1 2 3 1 1 1 2 1 2 3 1
n^2+2n+1 | O(n^2) | n^3-1000n^2+10^9 | O(n^3) |
n^10+9n^9+20n^8+145n^7 | O(n^10) | n + log(n) | O(n) |
(n+1)^4 | O(n^4) | n^2+nlog(n) | O(n^2) |
(n^2+n)^2 | O(n^4) | 2^n+n^2 | O(2^n) |
n+0.001n^3 | O(n^3) | (n^3+2n)/(n^2+0.75) | O(n) |
T(2000)/T(1000) | 2004997/502497=3.99 | f(2000)/f(1000) | 4 |
T(4000)/T(1000) | 8009997/502497=15.94 | f(4000)/f(1000) | 16 |
T(10000)/T(1000) | 50024997/502497=99.55 | f(10000)/f(1000) | 1000 |
For a set of 2000 records, it will take 10 seconds.
For a set of 10,000 records, it will take 50 seconds.
O(n) | O(n^2) | O(n^3) | O(n log(n)) | O(2^n) | |
1000 | 5 | 5 | 5 | 5 | 5 |
2000 | 10 | 20 | 40 | 11 | can't compute |
3000 | 15 | 45 | 135 | 17 | . . . |
10000 | 50 | 500 | 5000 | 67 | . . . |
In the last column, the values get large too quickly. The following may be more helpful:
O(2^n) | |
1000 | 5 |
1001 | 10 |
1002 | 20 |
1003 | 40 |
O(log(n))
O(sqrt(n))
O(n)
O(n log(n))
O(n sqrt(n))
O(n^2 log (n))
O(n^3)
O(n log(n))
O(2^n)
O(n^n)
The array needs to be traversed once to find the minimum, so the time complexity is O(n), where n is the length of the array. Finding both the minimum and the maximum is no worse than 2O(n) = O(n)
The complexity of the given method is O(n).
If the list has a single value then return 1.
Otherwise initialize a value for longest run to zero. Iterate over the list of values counting lengths of runs by counting duplicate values (i.e. difference is zero) When the difference between consecutive values is not zero compare the current run to longest run. If current run is longer then set longest run to current run. Reset current run to zero and continue to end of the list.
a) Sorting takes the most time. Using the Quicksort the complexity would be O(n log(n)).
b) Counting the duplicate elements takes the most time. The complexity would be O(n^2).
c) Counting the frequency of each element takes the most time. The complexity again would be O(n^2).
a) 4 7 11 4 9 5 11 7 3 5
Run 1: 3 7 11 4 9 5 11 7 4 5
Run 2: 3 4 11 7 9 5 11 7 4 5
Run 3: 3 4 4 7 9 5 11 7 11 5
Run 4: 3 4 4 5 9 7 11 7 11 5
Run 5: 3 4 4 5 5 7 11 7 11 9
Run 6: 3 4 4 5 5 7 7 11 11 9
Run 7: 3 4 4 5 5 7 7 9 11 11
Run 8: 3 4 4 5 5 7 7 9 11 11
b) -7 6 8 7 5 9 0 11 10 5 8
Run 1: -7 6 8 7 5 9 0 11 10 5 8
Run 2: -7 0 8 7 5 9 6 11 10 5 8
Run 3: -7 0 5 7 8 9 6 11 10 5 8
Run 4: -7 0 5 5 8 9 6 11 10 7 8
Run 5: -7 0 5 5 6 9 8 11 10 7 8
Run 6: -7 0 5 5 6 7 8 11 10 9 8
Run 7: -7 0 5 5 6 7 8 8 10 9 11
Run 8: -7 0 5 5 6 7 8 8 9 10 11
Run 9: -7 0 5 5 6 7 8 8 9 10 11
a) 5 11 7 3 5 4 7 11 4 9
split: 5 11 7 3 5_4 7 11 4 9
split: 5 11_7 3 5_4 7_11 4 9
split: 5_11_7_3 5_4_7_11_4 9
split: 5_11_7_3_5_4_7_11_4_9
merge: 5_11_7_3 5_4_7_11_4 9
merge: 5 11_3 5 7_4 7_4 9 11
merge: 3 5 5 7 11_4 4 7 9 11
merge: 3 4 4 5 5 7 7 9 11 11
b) 9 0 11 10 5 8 -7 6 8 7 5
split: 9 0 11 10 5_8 -7 6 8 7 5
split: 9 0_11 10 5_8 -7 6_8 7 5
split: 9_0_11_10 5_8_-7 6_8_7 5
split: 9_0_11_10_5_8_-7_6_8_7_5
merge: 9_0_11_5 10_8_-7 6_8_7 5
merge: 0 9_5 10 11_-7 6 8_5 7 8
merge: 0 5 9 10 11_-7 5 6 7 8 8
merge: -7 0 5 5 6 7 8 8 9 10 11
a)
Iteration 1: Check element at index 0. -7 is not 7.
Iteration 2: Check element at index 1. 1 is not 7.
Iteration 3: Check element at index 2. 3 is not 7.
Iteration 4: Check element at index 3. 3 is not 7.
Iteration 5: Check element at index 4. 4 is not 7.
Iteration 6: Check element at index 5. 7 is found. Done.
b)
Step 1: Check element at index 4 ((0 + 8) / 2). 4 < 8, look in larger half (7 8 11 13).
Step 2: Check element at index 6 ((5 + 8) / 2). 8 == 8. Done.
c)
Step 1: Check element at index 3 ((0 + 7) / 2). 3 < 8, look in larger half (5 7 10 13).
Step 2: Check element at index 5 ((4 + 7) / 2). 7 < 8, look in larger half (10, 13).
Step 3: Check element at index 6 ((6 + 7) / 2). 10 > 8, look in smaller half, but smaller half is empty. Value is not found.
To look at each a[i]
in turn requires n steps, where n is the length of the array. Each of these steps requires n - 1 element visits for the counting, and on average n / 2 steps for the element removal. Therefore, this is an
O(n(n-1 + n/2)) = O(n2) algorithm.
In the merging step, the items from both lists have to be compared as we remove them from the lists to create the sorted array. If the item being removed is the same as the last item added, we have to throw it way (it is a duplicate). This extra step takes O(n). Overall the new merge sort algorithm takes O(n log(n)) to complete.
Sorting takes O(n log(n)) time. After the array is sorted, we traverse it.
If we detect adjacent duplicates, we must move the remainder of the array down, which takes on average n/2 steps. So in the worst case this might be an O(n log n + n(n/2)) = O(n2) algorithm.
However, you can easily do better. Sort the array O(n log(n)). Traverse the array, and whenever the next element is strictly larger, append it into a second array (O(n)). Then copy the second array back into the first (O(n)). The result is an O(n log(n)) algorithm. (You can even avoid the second array by moving the elements to the head of the original array.)
The trouble is that we can't sort the array since that would disturb the original order. However, we can sort a copy to have a fast lookup for duplicates. Here is the algorithm.
Make a copy (O(n)) and sort it (O(n log(n))). Make a companion boolean
array to the sorted array and set all values in that array to false
. Traverse the array and do the following n times:
For each element, use binary search in the copy (O(log (n))) and then look at the neighbors to determine whether the element is a duplicate. If so, check if the corresponding value in the companion array is false
, indicating that this element has never been used previously. If the element is not a duplicate or it has never been used, then append it to a second array, and mark the corresponding boolean
as true
. Since this needs to be done for each element, we have O(n log(n)) for this phase. The total time complexity is therefore O(n log(n)).
Selection sort has O(n2), even when the array is already sorted. Selection sort works by building a sorted prefix of the array. It does this by searching for the smallest value in the (suffix) portion of the array to find the next value to add to the known sorted prefix. The algorithm has no mechanism to determine that the assumed unsorted portion is actually sorted. As such, the entirety of the assumed unsorted portion will be searched on each iteration.
On the other hand, insertion sort assumes the array is already sorted, and when it is, it iterates only once through the array. Iteration sort realizes this assumption as it iterates by attempting to insert the next value in the array (as the elements are traversed) into the known sorted prefix. With the array already sorted, inserting the next value will take constant time (the time to compare to the last value in the known sorted portion). Thus, in the case that the array is already sorted, insertion sort has O(n).
No, it does not. The insertion sort algorithm finds the position where the element needs to be inserted at the same time that it moves the elements that need to be moved to make space for the new element. Thus, it does not actually take any extra iterations to find the position. Using a binary search will find the insertion position in O(log (n)) but will not improve the O(n2) order of the algorithm because the elements will still need to be moved to allow insertion of the element which takes O(n).
Because there are two nested loops, the running time is O(n2). More specifically, the inner loop must compare each pair of adjacent elements which is a O(n) operation. The outer loop continues as long as the array is not sorted, but determining if an array is sorted is also a O(n) operation. Thus, the algorithm is O(n2).
The running time of radix sort on n numbers with d digits is O(n * d). It is preferable to merge sort when the number of digits, d, is less than log(n) and when the array is not too large because of the memory required for the auxiliary arrays.
Selection sort is not stable because the order of occurrence of the same key is hard to maintain after swap. Specifically, swapping the next value in the array with the smallest in the remaining portion of the array may place a duplicate (the next value) later in the array than another element of the same value.
Because multiple keys with the same value are placed in the sorted array in the same order that they appear in the input array, insertion sort is stable. In particular, insertion sort shifts values into the sorted portion of the array from the right. A value will only shift to the left if it is less than the value to its left. As such, when a value meets a duplicate, it remains after the duplicate as it was in the original array.
Create an array of 256 counters initially set to 0. Iterate through the array of n bytes. For each element, increment the counter at the corresponding index in the counter array (i.e., element i of the byte array is used as an index into the counter array (map the bytes to the range 0 to 255)). This step takes O(n) to analyze each element in the byte array. Iterate through the counter array and for each counter add an equal number of entries in the byte array with value corresponding to the counter position (i.e., the counter at index 0 with value 7 will result in 7 entries in the byte array with value -128). This step also takes O(n) to update each of the entries in the byte array. The algorithm is O(n).
Let's first make a single array of pairs (word, page). If there are n words (in all arrays together), that takes O(n) time. Then sort the pairs by word, breaking ties by page. That takes O(n log(n)) time. Finally, rewrite into an array of pairs (word, page set). This can again be done in O(n) time. (Note that duplicates can be removed in constant time since the pages are already sorted.) This gives a total of O(n log(n)) time.
Sort the second array, which takes O(n log(n)) time. For each element of the first array, try binary search across the other array. If you find it, report that there exists a match. Since there are n elements and each binary search takes O(log(n)) time, the running time will at most be O(n log(n)).
(The previous solution used an additional array, which is unnecessary unless the original array must remain unchanged.)
Sort the array, which takes O(n log(n)) time. For each element x in the array, perform a binary search to find v - x in the array. If found, then x and v - x are both in the array. This step takes n binary searches, each of which takes O(log(n)), for a total of O(n log(n)).
Sort the second array, which takes O(n log(n)) time. For each element of the first array, try binary search across the other array. Collect each match. Since there are n elements and each binary search takes O(log(n)) time, the total running time will be O(n log(n)).
For a sorted array, the running time will be linear O(n log(n)). The fact that the array is sorted does give a perfect partitioning at each step (meaning there will be log(n) levels of recursion), but each step must still examine every element of the subarray during the partitioning phase (though no values will be swapped).
If the pivot is in the middle, the running time would be O(n2) for an array in which the successive pivot values are in sorted order. For instance, the array 2 6 4 1 3 5 7 will use the value 1 as the first pivot (the solution in Special Topic 14.3 can be used mostly as is by swapping the element at the pivot with the first element before partitioning). This results in a partitioning with one subarray holding all remaining values 6 4 2 3 5 7. Again, the pivot selected leaves one subarray holding all remaining values 4 6 3 5 7. The split on pivot 3 gives 6 4 5 7; split on pivot 4 gives 6 5 7; the split on 5 gives 6 7; and splitting on 6 gives 7. As illustrated, the length of the partition is one less than the previous partition. This results in O(n) levels of recursion with O(n) steps in the partitioning process at each level.
A list is a good choice here. A list will allow duplicate items to be listed, a likely possibility on an invoice, and implies an order which also may be important for an invoice.
A list is also a good choice here. A useful appointment calendar application will allow the user to browse appointments; although this is possible with stack or queue implementation, it would be awkward.
One could create a map to a list of event objects. Then each key (date object) would return a list of all the appointments on that date.
You can use the methods addAll removeAll containsAll retainAll from the Collection interface to accomplish the following set operations:
1) union: Call the addAll method from one set sending in the other set as the argument.
2) intersection: Call the retainAll method from one set sending in the other set as the argument.
3) difference: Call the removeAll method from one set sending in the found intersection from part 2.
4) subset: Call the containsAll method from one set sending in a collection which represents a subset to be tested.
The code prints:
Tom Diana Harry
The best description to see what is going on is to examine the state of the linked list at each step. In the notation below the list is enclosed by [
and ].
1.
staff.addFirst("Harry"); staff = ["Harry"]
2.
staff.addFirst("Diana"); staff = ["Diana", "Harry"]
3.
staff.addFirst("Tom"); staff = ["Tom", "Diana", "Harry"]
4.
System.out.println(staff.removeFirst());
Prints Tom.
staff = ["Diana", "Harry"]
5.
System.out.println(staff.removeFirst());
Prints Diana.
staff = ["Harry"]
6.
System.out.println(staff.removeFirst());
Prints Harry.
staff = []
The code prints:
Harry Tom Diana
The best description to see what is going on is to examine the state of the linked list at each step. In the notation below the list is enclosed by [
and ].
1. staff.addFirst("Harry"); staff = ["Harry"] 2. staff.addFirst("Diana"); staff = ["Diana", "Harry"] 3. staff.addFirst("Tom"); staff = ["Tom", "Diana", "Harry"] 4.
System.out.println(staff.removeLast());
Prints Harry.
staff = ["Tom", "Diana"] 5.
System.out.println(staff.removeFirst());
Prints Tom.
staff = ["Diana"] 6.
System.out.println(staff.removeLast());
Prints Diana.
staff = []
This code prints out:
Diana Tom Harry
The best description to see what is going on is to examine the state of the linked list at each step. In the notation below the list is enclosed by [
and ].
1.
staff.addFirst("Harry"); staff = ["Harry"]
2.
staff.addLast("Diana"); staff = ["Harry", "Diana"]
3.
staff.addFirst("Tom"); staff = ["Tom", "Harry", "Diana"]
4.
System.out.println(staff.removeLast());
Prints Diana.
staff = ["Tom", "Harry"]
5.
System.out.println(staff.removeFirst());
Prints Tom.
staff = ["Harry"]
6.
System.out.println(staff.removeLast());
Prints Harry.
staff = []
This code prints the following:
Diana Harry
The iterator builds up a list (Tom
, Diana
, Harry
), then removes the first Tom
while the loop removes the rest. Here is the state of the linked list at each step. In the notation below the list is enclosed by [
and ]
, and the iterator is indicated by a |.
1.
iterator.add("Tom"); staff = ["Tom"|]
2.
iterator.add("Diana"); staff = ["Tom", "Diana"|]
3.
iterator.add("Harry"); staff = ["Tom", "Diana", "Harry"|]
4.
iterator = staff.listIterator(); staff = [|"Tom", "Diana", "Harry"]
5.
if (iterator.next().equals("Tom")) staff = ["Tom", |"Diana", "Harry"]
6.
iterator.remove(); staff = [|"Diana", "Harry"]
7.
while (iterator.hasNext()) System.out.println(iterator.next());
Iteration 1 prints Diana
:
staff = ["Diana", |"Harry"]
Iteration 2 prints Harry
:
staff = ["Diana", "Harry"|]
The following code prints:
Diana Romeo Harry Juliet
It is best explained by examining the state of the linked list. In the notation below the list is enclosed by [
and ]
, and the iterator is indicated by a |.
1.
iterator.add("Tom"); staff = ["Tom"|]
2.
iterator.add("Diana"); staff = ["Tom", "Diana"|]
3.
iterator.add("Harry"); staff = ["Tom", "Diana", "Harry"|]
4.
iterator = staff.listIterator(); staff = [|"Tom", "Diana", "Harry"]
5.
iterator.next(); staff = ["Tom", |"Diana", "Harry"]
6.
iterator.next(); staff = ["Tom", "Diana", |"Harry"]
7.
iterator.add("Romeo"); staff = ["Tom", "Diana", "Romeo", |"Harry"]
8.
iterator.next(); staff = ["Tom", "Diana", "Romeo", "Harry"|]
9.
iterator.add("Juliet"); staff = ["Tom", "Diana", "Romeo", "Harry", "Juliet"|]
10.
iterator = staff.listIterator(); staff = [|"Tom", "Diana", "Romeo", "Harry", "Juliet"]
11.
iterator.next(); staff = ["Tom", |"Diana", "Romeo", "Harry", "Juliet"]
12.
iterator.remove(); staff = [|"Diana", "Romeo", "Harry", "Juliet"]
13.
while (iterator.hasNext()) System.out.println(iterator.next());
Iteration 1 prints Diana
:
staff = ["Diana", |"Romeo", "Harry", "Juliet"]
Iteration 2 prints Romeo
:
staff = ["Diana", "Romeo", |"Harry", "Juliet"]
Iteration 3 prints Harry
:
staff = ["Diana", "Romeo", "Harry", |"Juliet"]
Iteration 4 prints Juliet
:
staff = ["Diana", "Romeo", "Harry", "Juliet"|]
// remove all strings of length <= 3 Iterator<String> itr - list.iterator(); while (itr.hasNext()) { String item = itr.next(); if (item.length() <= 3) { itr.remove(); } }
// remove all strings of length <= 3 theList.removeIf(str -> str.length() <= 3)
Linked lists can be advantageous over arrays if an application needs to add or remove data arbitrarily throughout the list; this process is relatively easy using linked lists but more difficult with arrays. A disadvantage is that randomly accessing elements within the linked list can be inefficient compared to an array.
Answers can vary here.
Since there is a known upper bound on the data (10,000 elements) and the employee directory is relatively fixed, one could argue the use of an array list due to its efficient random access operator. On the other hand, if the employee list is heavily modified, one may prefer a linked list due to its ease of modification.
In practice, 6,000 elements and several hundred accesses is not a large data set or a computationally complex problem. It's likely that there will be no noticeable performance difference between the two.
Since appointments are often added and removed, one would probably prefer a linked list. The linked list will allow easy addition and removal of appointments.
A queue since this data structure specifically limits additions to one end and removals from the other. A stack is the opposite where removals and additions occur on the same end.
When "A"..."Z" are pushed on the first stack they will be stored in reverse order "Z"..."A". When popped off the first and pushed on the second, they will be in alphabetical order again "A"..."Z". Thus, they will be popped off the second stack in alphabetical order and will print "A"..."Z".
Although both a set and map are unordered, the relevant property of a set is membership, where a map is a data structure that allows lookups of values based on a given key.
To compute the union of set A and set B, remove one element from B at a time and add each element to A; continue this until B is empty.
To compute the intersection of set A and set B, remove each element from A, use contains
to check whether the element is in B and if it is, add it to a temporary set; continue this until A is empty. The resulting set is the intersection between A and B.
A union between a set A and B can be easily computed with the addAll
method. First addAll
elements from A to a copy of A, then addAll
elements in B to that copy. The result is the union between A and B.
An intersection can be computed with the removeAll
method. First, make a copy of B, then removeAll
elements in B that are also in A. This leaves you all the elements in B that are not the intersection between B and A; thus removeAll
of those elements from the original set of B, and you're left with the intersection.
A map can have two keys with the same value because the map would fetch either value depending on the key.
On the other hand, a map cannot have two values with the same key, as the map would be unable to distinguish which one is associated with an identical key.
If a set contained (key, value) pairs, one could implement a get
by iterating over the set until a key was found that matched the requested key, then the algorithm would return the value associated with that key.
The put
operation can be implemented by first checking that no (key, value) pair exists with the same key, then adding the given (key, value) pair to the set.
Printing all key/values pairs of a map:
a) Using ketSet method:
//Assuming String/Integer key/value pairs for (String key : theMap.keySet()) { Integer value = theMap.get(key); System.out.println(key + " - " + value); }
b) Using entrySet method:
//Assuming String/Integer key/value pairs Set set = theMap.entrySet(); Interator itr = set.iterator(); while (itr.hasNext()) { Map.Extry entry = (Map.Entry)itr.next(); System.out.println(entry.getKey() + " - " + entry.getValue()); }
c) Using forEach and functional notation:
//Assuming String/Integer key/value pairs theMap.forEach((key, value) -> System.out.println(key + " - " + value));
This code:
String a = "Juliet"; System.out.println(a.hashCode());
Prints:
-2065036585
Which conforms to Table 6.
This code:
String a = "VII"; String b = "Ugh"; System.out.println(a.hashCode() == b.hashCode());
Prints:
true
Which proves the hash codes are the same.
The figure in the exercise should look like this:
Start at A
A (right)
Visit B
B (up)
B (right)
Visit H
H (up)
H (right)
H (left)
B (right)
Visit P
P (right)
P (left)
H (right)
H (left)
B (right)
Visit Q
Q (right)
Q (down)
P (left)
H (right)
H (left)
B (right)
Visit R. Dead end
Q (down)
P (left)
H (right)
H (left)
B (right)
Visit J
J (right)
P (left)
H (right)
H (left)
B (right)
Visit K. Exit.
Start at A
A-right
Visit B
B-up B-right
Visit C. Dead end
B-up
Visit H.
H-up H-right H-left
Visit G.
G-up H-up H-right
Visit I.
I-up G-up H-up
Visit P.
P-right P-left I-up G-up
Visit L. Dead end.
P-right P-left I-up
Visit N.
N-left P-right P-left
Visit O. Dead end.
N-left P-right
Visit Q.
Q-right Q-down N-left
Visit M. Dead end.
Q-right Q-down
Visit J.
J-right Q-right
Visit R. Dead end.
J-right
Visit K. Exit.
Insertion:
Removal:
Insertion:
Removal:
Insertion:
Removal:
Insertion:
Removal:
Both are O(n) operations, where n is the length of the list.
The first is an O(n) operation, but the second is O(n^2) since removing an element is an O(n) operation.
It is tempting to set previous
to null
after a call to add or remove, but that doesn't work. If one visits the first element, then previous
is legitimately null
.
Instead, one can set previous
and position
to the same value after each call to add
or remove
. This can never happen after a call to next
. (After calling next
, we either have previous == null
and position == first
, or previous != null
and position == previous.next
. In either case, previous != position
.)
public void remove() { if (position == previous) { throw new IllegalStateException(); } if (position == first) { removeFirst(); } else { previous.next = position.next; } position = previous; } public void add(Object element) { if (position == null) { addFirst(element); position = first; } else { Node newNode = new Node(); newNode.data = element; newNode.next = position.next; position.next = newNode; position = newNode; } previous = position; }
O(n)
Correction: The problem statement should refer to the size
method in P16.6.
The currentSize
instance variable needs to be incremented in the add
method and decremented in the addFirst
and removeFirst
method of the list class and the remove
method of the iterator. With this change, add
and remove
are still O(1). No other methods change the currentSize
variable.
Correction: The problem statement should refer to the size
method in P16.6.
With the implementation in P16.7, get
is O(n). Therefore, the loop is O(n^2).
Correction: The problem statement should refer to the size
method in P16.6.
Because a call get(i + 1)
that follows a call get(i)
is O(1), this loop is O(n).
When the iterator has traversed the first element, its position reference points to the first
node. If one calls removeFirst
, the iterator points to a node that is no longer in the linked list.
Now suppose we call remove
on the iterator:
if (position == first) { removeFirst(); } else { previous.next = position.next; } position = previous;
As you can see from the drawing, position != first
, and the second branch is executed. Because previous
is null, an exception is thrown.
public class R16_11 { public static void main(String[] args) { LinkedList staff = new LinkedList(); staff.addFirst("Tom"); staff.addFirst("Romeo"); staff.addFirst("Harry"); staff.addFirst("Diana"); ListIterator iterator = staff.listIterator(); // |DHRT iterator.next(); // D|HRT staff.removeFirst(); iterator.remove(); } } $ java R16_11 Exception in thread "main" java.lang.NullPointerException at LinkedList$LinkedListIterator.remove(LinkedList.java:163) at R16_11.main(R16_11.java:14)
Have the first iterator before the first element, and the second iterator traverse the first element of a list. Then insert an element through the first iterator. The figure shows the result.
Now call remove
on the second iterator.
if (position == first) { removeFirst(); } else { previous.next = position.next; } position = previous;
As you can see from the figure, position != first
, and the second branch is executed. Because previous
is null, an exception is thrown.
public class R16_13 { public static void main(String[] args) { LinkedList staff = new LinkedList(); staff.addFirst("Tom"); staff.addFirst("Romeo"); staff.addFirst("Harry"); staff.addFirst("Diana"); ListIterator iterator1 = staff.listIterator(); ListIterator iterator2 = staff.listIterator(); iterator1.next(); iterator1.add("Fred"); iterator2.remove(); } } $ java R16_13 Exception in thread "main" java.lang.IllegalStateException at LinkedList$LinkedListIterator.remove(LinkedList.java:155) at R16_13.main(R16_13.java:15)
Add a mutationCount
to the LinkedList
class. Add an iteratorMutationCount
in the LinkedListIterator
class. In the methods addFirst
and removeFirst
of the LinkedList
class, increment the mutationCount
field.
When you construct an iterator, set
iteratorMutationCount = mutationCount
In the methods add
and remove
of the LinkedListIterator
class, increment both counts.
At the beginning of the add
and remove
method of the LinkedListIterator
class, add the statement
if (mutationCount != iteratorMutationCount) { throw new ConcurrentModificationException(); }
To get to the kth element of a list of length n takes O(k) steps if one starts at the front, or O(min(k, n - k)) steps if one starts at the front or back, whichever is closer. Assuming k is randomly chosen between 0 and n - 1, on average, O(k) = O(n / 2) = O(n), and O(min(k, n - k)) = O(n / 4) = O(n).
The get
operation is now O(1) since we can look up the link to n - n % 10 in constant time, and then make < 10 hops to get to n. However, maintaining that array of node references is very expensive when adding or removing elements in the middle of an array. For example, if one removes an element in position 19, all references to locations 20, 30, ..., have to be updated - an O(n / 10) = O(n) operation. In other words, we have lost the benefit of O(1) insertion and removal.
As n elements are added, an O(n) resize will occur every 10 steps. Because Big-Oh discards constant factors (in this case, 1/10), the result remains O(n).
First fill the array with 10 * 2k elements, so that it is just about to reallocate.
Then add one element and remove one. The addition reallocates, and the removal reallocates again. The cost is not O(1) - you can make it arbitrarily high by choosing an appropriate k.
For each addLast
operation, charge $2. Spend $1 on moving the value to be added to the end of the array, and put the other $1 in the bank. When it comes time to reallocate the array to one that is twice as large, you must copy n elements, but there will be enough money in the bank to pay for that.
For each removeLast
operation, charge $2. Spend $1 on returning the removed value, and put the other $1 in the bank. When it comes time to reallocate the array to one that is 1/2 as large, you must copy n / 4 elements, so there will be more than enough money in the bank to pay for that.
Moving the head element to the tail is simply q.add(q.remove())
, also O(1). Moving the tail to the head requires a loop:
int n = q.size(); for (i = 1; i < n; i++) { q.add(q.remove()); }
For example, if n = 4
A B C D
D A B C
C D A B
B C D A
The loop is executed n - 1 times, so it's O(n).
a) addFirst
, removeFirst
, addLast
are O(1), but removeLast
is O(n); see Section 16.1.8
b) All are O(1)
c) All are O(1+)
No. There are two situations when head==tail
: when the queue is entirely empty, or when it is entirely full.
a.
1 2 3 4 5 _ _ _ _ _ currentSize = 5 H T
b.
1 2 3 4 5 _ _ _ _ _ currentSize = 2 H T
c.
6 7 8 4 5 1 2 3 4 5 currentSize = 10 H T 4 5 1 2 3 4 5 6 7 8 _ _ _ _ _ _ _ _ _ _ currentSize = 10 H T 4 5 1 2 3 4 5 6 7 8 9 10 _ _ _ _ _ _ _ _ currentSize = 12 H T
d.
4 5 1 2 3 4 5 6 7 8 9 10 _ _ _ _ _ _ _ _ currentSize = 4 H T
You have stacks S1 and S2.
When adding a value, add it to S1. When removing a value, first check if S2 is empty, in which case you pop all values from S1 and push them onto S2. Then pop the value from S2.
For example,
S1: S2:
Add 1
S1: 1 S2:
Add 2
S1: 1 2 S2:
Add 3
S1: 1 2 3 S2:
Remove
S1: S2: 3 2 1
S1: S2: 3 2
Remove
S1: S2: 3
Add 4
S1: 4 S2: 3
Remove
S1: 4 S2:
Remove
S1: S2: 4
S1: S2
The cost for adding is clearly O(1), because we just add to a stack. The cost for removing is O(1+). We pay for transferring elements from S1 to S2, but that cost is amortized over each removal.
You have two queues, an active one (A) and a temporary one (T). When pushing an element, add it to the active one. When popping an element, move all but the last element from the active one to the temporary one. The last one is the one to be returned. Then flip the active and temporary queues.
The cost for pushing is O(1) because we add to a queue. The cost for popping is O(n) because we need to move n - 1 elements to the other queue.
It doesn't work if one has different objects with the same content. Consider a hash set of Fred's favorite colors. You want to find out whether Fred loves green. No problem - look for Color.GREEN
. But what about chartreuse? If you construct a new Color(127, 255, 0)
to find out, then that object has a different ID than the new Color(127, 255, 0
) that Fred constructed.
There is only one general tree of a given height with one leaf:
o | o | . . . | o
If the tree is a binary tree, then there are 2(h - 1) versions, depending on whether each edge points left or right. For example, if h = 3:
o o o o / / \ \ o o o o / \ / \ o o o o
A general tree of height 2 has one root and k - 1 leaves:
o / / | \ \ o o o o o
If the tree is a binary tree, there are three possibilities:
o o o / \ / \ o o o o
Set maximum to the number of siblings in the root. Find the maximum number of siblings in each subtree and compare that to the number of siblings in the root. If any are larger, set maximum to that number.
If r is a leaf, TPL(r) = 1.
Otherwise, if r has children c1...ck, then TPL(r) = LEAVES(r) + TPL(c1) + ... + TPL(ck), where LEAVES(r) is the number of leaves of the tree r, recursively defined as
LEAVES(r) = 1 if r is a leaf, and
LEAVES(r) = LEAVES(c1) + ... + LEAVES(ck) if r has children c1... ck
Here is an inductive proof of both facts.
If the tree has one leaf, then it certainly has >= l - 1 interior nodes. There are three such trees:
o o o / \ o o
The latter two have interior nodes with one child, but the first one has no interior nodes at all, or l - 1 interior nodes.
Now assume that r is the root of a tree with children c1 and c2, which have l1 and l2 leaves respectively. Note that l1 + l2 = l. Inductively, c1 has >= l1 - 1 interior nodes and c2 has >= l2 - 1 interior nodes. Therefore, r has >= l1 - 1 + l2 - 1 + 1 = l - 1 interior nodes since r itself is an interior node.
Now assume that r = l - 1 = l1 - 1 + l2- 1 + 1. Then we know that c1 must have exactly l1 - 1 interior nodes and c2 must have exactly l2 - 1 interior nodes. (If one had more, the other would have to have fewer, violating the inductive assumption.) Therefore, all of the interior nodes in c1 and c2 have two children. In particular, neither is empty, and r has two children as well.
A binary search tree is a binary tree. However, in a binary search tree, each subtree has the property that all descendants to the left are smaller than the value in the subtree's root, and that all descendants to the right are larger than the value in the subtree's root.
Here is a binary tree that isn't a binary search tree:
Harry / \ Tom Diana
Here is a binary tree that is a binary search tree:
Diana \ Tom / Harry
In a balanced tree, each subtree has the property that the number of descendants to the left is approximately equal to the number of descendants to the right. In an unbalanced tree, this property does not hold.
Here is a balanced binary tree:
Harry / \ Tom Diana
Here is a binary tree that is not balanced:
Diana \ Tom / Harry
Adam Adam \ Eve Adam \ Eve \ Romeo Adam \ Eve \ Romeo / Juliet Adam \ Eve \ Romeo / \ Juliet Tom Adam \ Eve / \ Diana Romeo / \ Juliet Tom Adam \ Eve / \ Diana Romeo / \ Juliet Tom / Harry
The tree is
Harry / \ Diana Tom / \ / Adam Eve Juliet \ Romeo
Printing this tree with the print
method yields the printout
Adam Diana Eve Harry Juliet Romeo Tom
That's the same printout as the printout resulting from the tree in the preceding exercise because the tree contents are always printed in sorted order, no matter in which order the nodes were inserted.
2 7 4 1 8 5 3 9 6 10
Given a binary tree t with left and right children l and r, define
elem(
k, t)
= undefined if t is a leaf and k> 0, or if t is empty
= elem(
k, l)
if k<size(
l)
= t.data
if k = size(
l)
= elem(
k - size(
l)
- 1, r) otherwise
The algorithm must compute the size of each left subtree, which is O(n). (Consider the worst case where the tree is completely populated with 2h - 1 nodes. Then the left subtrees have sizes 2(h - 1) - 1, 2(h - 2) - 1, ..., which add up to about 2h or n.)
The remainder of the algorithm is O(log(n)). Therefore, the total execution time is O(n).
The algorithm is the same as the one described in Exercise R17.11. However, if each node has the size of its subtree pre-calculated, the total cost is O(log(n)), the length of the path to the kth node. (Here we assume the tree to be balanced.)
When adding an element, then the sizes need to be incremented on all nodes along the path from the added node to the root. You can do it as you recurse the tree, moving to the left or right to find the insertion location. The effort is proportional to the path to the insertion location, or O(log(n)), assuming the tree is balanced. This won't affect the efficiency of the add operation.
Similarly, when removing an element, you can decrement the sizes of the traversed nodes in O(log(n)) time.
Let t1 and t2 be binary trees with children l1, r1 and l2, r2 respectively.
sameShape(
t1, t2)
= true if t1 and t2 are both leaves or both empty
= false if t1 is a leaf but t2 is not, or t2 is a leaf and t1 is not
= false if t1 is empty but t2 is not, or t2 is empty and t1 is not
= sameShape(
l1, l2) && sameShape(
r1, r2)
otherwise
Since the algorithm recursively visits all nodes of t1 and t2 in the "worst" case in which the shapes are the same, its execution time is O(n1 + n2).
18: We show this by induction. If bh = 1, then the tree has at least 22 - 1 = 1 nodes. Now assume that bh> 1. If a child is black, then its black height is bh - 1. If it is red, it must have two black children, each of black height bh - 1. In either case, each subtree has >= 2(bh - 1) - 1 children by induction, and the tree has >= 2 * 2(bh - 1) - 2 + 1 = 2bh - 1 children.
Inorder:
a as fleece had its lamb little mary snow was white
Preorder:
mary had a fleece as little lamb its was snow white
Postorder:
as fleece a its lamb little had snow white was mary
No children: as, its, snow, white
One child: a, fleece, lamb, little
Two children: mary, had, was
No children: In each case, the node can be removed without any change to the rest of the tree.
One child: In each case, the node can be removed and be replaced by its single child:
Two children: mary, had, was
No children: as, its, snow, white
One child: a, fleece, lamb, little
Two children: mary, had, was
No children: In each case, the node can be removed without any change to the rest of the tree.
One child: In each case, the node can be removed and be replaced by its single child:
Two children: mary, had, was
No children: as, its, snow, white
One child: a, fleece, lamb, little
Two children: mary, had, was
No children: In each case, the node can be removed without any change to the rest of the tree.
One child: In each case, the node can be removed and be replaced by its single child:
Two children: mary, had, was
No children: as, its, snow, white
One child: a, fleece, lamb, little
Two children: mary, had, was
No children: In each case, the node can be removed without any change to the rest of the tree.
One child: In each case, the node can be removed and be replaced by its single child:
Two children: mary, had, was
No children: as, its, snow, white
One child: a, fleece, lamb, little
Two children: mary, had, was
No children: In each case, the node can be removed without any change to the rest of the tree.
One child: In each case, the node can be removed and be replaced by its single child:
Two children: mary, had, was
No children: as, its, snow, white
One child: a, fleece, lamb, little
Two children: mary, had, was
No children: In each case, the node can be removed without any change to the rest of the tree.
One child: In each case, the node can be removed and be replaced by its single child:
Two children: mary, had, was
No children: as, its, snow, white
One child: a, fleece, lamb, little
Two children: mary, had, was
No children: In each case, the node can be removed without any change to the rest of the tree.
One child: In each case, the node can be removed and be replaced by its single child:
Two children: mary, had, was
Underlined nodes are black; others are red.
No children: its, snow, a, fleece, white
One child: lamb, mary
Two children: little, had, was, as
No children: its
and snow
are red and can be removed without any change to the tree. Because a
and fleece
are black, we need to subtract one from each sibling and add one to the parent, making the children red and preserving the equal exit cost rule, before removing the red child:
To remove white, we need to change it to red and add one to the parent, creating a double-black and a double-red. After fixing the double-black, white
is red and can be removed:
One child: lamb, mary
Two children: To remove little
:
To remove had
:
To remove was
:
To remove as
:
No children: its, snow, a, fleece, white
One child: lamb, mary
Two children: little, had, was, as
No children: its
and snow
are red and can be removed without any change to the tree. Because a
and fleece
are black, we need to subtract one from each sibling and add one to the parent, making the children red and preserving the equal exit cost rule, before removing the red child:
To remove white, we need to change it to red and add one to the parent, creating a double-black and a double-red. After fixing the double-black, white
is red and can be removed:
One child: lamb, mary
Two children: To remove little
:
To remove had
:
To remove was
:
To remove as
:
No children: its, snow, a, fleece, white
One child: lamb, mary
Two children: little, had, was, as
No children: its
and snow
are red and can be removed without any change to the tree. Because a
and fleece
are black, we need to subtract one from each sibling and add one to the parent, making the children red and preserving the equal exit cost rule, before removing the red child:
To remove white, we need to change it to red and add one to the parent, creating a double-black and a double-red. After fixing the double-black, white
is red and can be removed:
One child: lamb, mary
Two children: To remove little
:
To remove had
:
To remove was
:
To remove as
:
No children: its, snow, a, fleece, white
One child: lamb, mary
Two children: little, had, was, as
No children: its
and snow
are red and can be removed without any change to the tree. Because a
and fleece
are black, we need to subtract one from each sibling and add one to the parent, making the children red and preserving the equal exit cost rule, before removing the red child:
To remove white, we need to change it to red and add one to the parent, creating a double-black and a double-red. After fixing the double-black, white
is red and can be removed:
One child: lamb, mary
Two children: To remove little
:
To remove had
:
To remove was
:
To remove as
:
No children: its, snow, a, fleece, white
One child: lamb, mary
Two children: little, had, was, as
No children: its
and snow
are red and can be removed without any change to the tree. Because a
and fleece
are black, we need to subtract one from each sibling and add one to the parent, making the children red and preserving the equal exit cost rule, before removing the red child:
To remove white, we need to change it to red and add one to the parent, creating a double-black and a double-red. After fixing the double-black, white
is red and can be removed:
One child: lamb, mary
Two children: To remove little
:
To remove had
:
To remove was
:
To remove as
:
No children: its, snow, a, fleece, white
One child: lamb, mary
Two children: little, had, was, as
No children: its
and snow
are red and can be removed without any change to the tree. Because a
and fleece
are black, we need to subtract one from each sibling and add one to the parent, making the children red and preserving the equal exit cost rule, before removing the red child:
To remove white, we need to change it to red and add one to the parent, creating a double-black and a double-red. After fixing the double-black, white
is red and can be removed:
One child: lamb, mary
Two children: To remove little
:
To remove had
:
To remove was
:
To remove as
:
No children: its, snow, a, fleece, white
One child: lamb, mary
Two children: little, had, was, as
No children: its
and snow
are red and can be removed without any change to the tree. Because a
and fleece
are black, we need to subtract one from each sibling and add one to the parent, making the children red and preserving the equal exit cost rule, before removing the red child:
To remove white, we need to change it to red and add one to the parent, creating a double-black and a double-red. After fixing the double-black, white
is red and can be removed:
One child: lamb, mary
Two children: To remove little
:
To remove had
:
To remove was
:
To remove as
:
No children: its, snow, a, fleece, white
One child: lamb, mary
Two children: little, had, was, as
No children: its
and snow
are red and can be removed without any change to the tree. Because a
and fleece
are black, we need to subtract one from each sibling and add one to the parent, making the children red and preserving the equal exit cost rule, before removing the red child:
To remove white, we need to change it to red and add one to the parent, creating a double-black and a double-red. After fixing the double-black, white
is red and can be removed:
One child: lamb, mary
Two children: To remove little
:
To remove had
:
To remove was
:
To remove as
:
No children: its, snow, a, fleece, white
One child: lamb, mary
Two children: little, had, was, as
No children: its
and snow
are red and can be removed without any change to the tree. Because a
and fleece
are black, we need to subtract one from each sibling and add one to the parent, making the children red and preserving the equal exit cost rule, before removing the red child:
To remove white, we need to change it to red and add one to the parent, creating a double-black and a double-red. After fixing the double-black, white
is red and can be removed:
One child: lamb, mary
Two children: To remove little
:
To remove had
:
To remove was
:
To remove as
:
No children: its, snow, a, fleece, white
One child: lamb, mary
Two children: little, had, was, as
No children: its
and snow
are red and can be removed without any change to the tree. Because a
and fleece
are black, we need to subtract one from each sibling and add one to the parent, making the children red and preserving the equal exit cost rule, before removing the red child:
To remove white, we need to change it to red and add one to the parent, creating a double-black and a double-red. After fixing the double-black, white
is red and can be removed:
One child: lamb, mary
Two children: To remove little
:
To remove had
:
To remove was
: