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
:
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
:
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.
rbts(1) = 3
b b b / \ r r
rbts(bh) = (rbts(bh - 1) + rbts(bh - 1)2)2
Therefore, rbts(2) = (3 + 9)2 = 144
rbts(3) = (144 + 1442)2 = 435974400
The maximum is attained when one has as many red nodes as possible.
b / \ r r / \ / \ b b b b /\ /\ /\ /\ r r r r r r r r
That's a complete tree with h = 2 * bh and 2h - 1 = 4bh - 1 nodes.
Every interior red node must have two black children. (It can't have red children because of the double red rule. If it had no children, it wouldn't be interior. If it had one black child, the equal exit cost rule would be violated.) Therefore, there must be at least twice as many black nodes as interior red nodes.
The color of the root never matters, except in the last step of bubbling up a double-red, where a red root is colored black. Omitting this step doesn't change the big-oh efficiency.
With dummy nodes, each node has exactly two children, and the "equal exit cost" refers to paths from the root to leaves of the tree, not nulls. It also eliminates one of the cases in the removal algorithm (the second easy one).
When removing an element from a priority queue, the element with the highest priority is retrieved. To implement a priority queue with a binary search tree is straightforward. We just need to add elements as we normally would; and, to remove an element from the priority queue, we would find the largest element in the tree (the rightmost element) and remove it. Adding, finding, and removing an element are each O(log(n)) operations. Thus, adding and removing an element from a priority queue - if implemented with a binary search tree - would take O(log(n)) time.
None of the traversal orders (preorder, inorder, postorder) would print a heap in sorted order because the heap structure is a level-by-level structure, and not a node-by-node structure like that of a binary search tree. On a heap there is no relationship between the left branch of a node and the right branch of a node, other than the fact that both contain elements that are greater or equal than the node itself (a min-heap). For example, consider the heap:
85 / \ 90 86 / \ / \ 91 92 88 89
Preorder traversal: 85 90 91 92 86 88 89
Inorder traversal:
91 90 92 85 88 86 89
Postorder traversal: 91 92 90 88 89 86 85
A heap of height h has h - 1 complete levels, but the last level can have 1 to 2h - 1 elements. A complete binary tree has 2h - 1 elements. Thus, a heap has 2h - 1 elements plus the number of elements in the last level. The minimum number of elements that a heap can have is 2h - 1 and the maximum number of elements that a heap can have is
2h - 1 + 2h - 1 - 1 = 2h - 1.
The nodes are stored as
Unused | Root = n00 | Level 1 = n10 n11 | Level 2 = n20 n21 n22 n23 | . . . [0] [1] [2] [4]
There are 2k nodes in level k (because each complete level has twice as many nodes as its parent).
Therefore, the kth level starts at index 1 + 1 + 2 + 4 + . . . + 2k -1 = 2k.
The jth node in the kth level has index i = 2k + j.
Since it is preceded by j nodes in its level, its children are preceded by 2j nodes in the next level. That is, they are in positions 2j and 2j + 1. (Note that we count positions starting with 0.)
Therefore, their array indexes are 2k + 1 + 2j and 2k + 1 + 2j + 1.
Those are the same values that the child node formula produces: The left child index is 2i = 2 * (2k + j) = 2k + 1 + 2j, and the right child index is 2i + 1 = 2 * (2k + j) + 1 = 2k + 1 + 2j + 1.
The formula for the parent index follows immediately. If the child of the parent with index p has index i = 2p or i = 2p + 1, then clearly p = i / 2, where / denotes integer division.
Start calling fixHeap
with the parent of the last node, then move to the root
11 | 27 8 | 14 45 6 24 | 81 29 33 -- 11 | 27 8 | 14 45 6 24 | 81 29 33 -- 11 | 27 8 | 81 45 6 24 | 14 29 33 - 11 | 27 24 | 81 45 6 8 | 14 29 33 -- 11 | 81 24 | 29 45 6 8 | 14 27 33 -- 81 | 45 24 | 29 33 6 8 | 14 27 11
Now keep swapping the root with the last unsorted element, and call fixHeap
after each swap.
45 | 33 24 | 29 11 6 8 | 14 27 / 81 33 | 29 24 | 27 11 6 8 | 14 / 45 81 29 | 27 24 | 14 11 6 8 / 33 45 81 27 | 14 24 | 8 11 6 / 29 33 45 81 24 | 14 6 | 8 11 / 27 29 33 45 81 14 | 11 6 | 8 / 24 27 29 33 45 81 11 | 8 6 / 14 24 27 29 33 45 81 8 | 6 / 11 14 24 27 29 33 45 81 6 / 8 11 14 24 27 29 33 45 81
Type parameters are variables that can be instantiated with class or interface types.
A generic class has one or more type parameters. In order to use a generic class, you need to instantiate the type parameters, that is, supply actual types. Ordinary classes do not use type parameters.
A generic class is a class with one or more type parameters. A generic method is a method with one or more type parameters.
You must provide a type argument for instantiating a generic class so that the compiler knows the memory size for each each element within the gereic class. There is no need to supply type arguments when invoking an instantiation of a generic class since the type class is already known.
The toArray
method in the java.util.LinkedList
class:
public <T> T[] toArray(T[] a)
AbstractMap<K,V> Dictionary<K,V> EnumMap<K extends Enum<E>,V> HashMap<K,V> Hashtable<K,V> IdentityHashMap<K,V> LinkedHashMap<K,V> TreeMap<K,V> WeakHashMap<K,V>
java.lang.Class<T> java.lang.Enum<T> java.util.concurrent.Exchanger<V> java.util.concurrent.ExecutorCompletionService<V> java.util.concurrent.FutureTask<T>
A binary search locates a value in a sorted array by determining whether the value occurs in the first or second half, then repeating the search in one of the halves. To know if the key occurs in the first half or second half, the binary search algorithm needs to be able to determine whether the key is smaller or greater than the middle element. The type bound allows it to use the compareTo
method of the Comparable
interface to compare values because any value in the array must implement Comparable
.
All classes are descendants of the class Object
. The class Object
has a method to calculate the hash code of an object. Thus, objects of any class can be stored in a hash set.
It is an array list of Pair
s of objects of the same type (e.g. an array list of String
pairs).
public static <T extends Comparable<? super T>> void sort(List<T> a)
means that the type variable T
must extend Comparable<U>
for some type U
where U
is any supertype of T
(or possibly T
itself).
The bound <T extends Comparable>
would not have been sufficient. Suppose we want to sort an ArrayList<BankAccount>
, where the class BankAccount
implements Comparable<BankAccount>
. Then we would get a warning. A Comparable
object is willing to compare itself against any object, but a BankAccount
is only willing to compare against another BankAccount
.
public static <T extends Comparable<T>> void sort(List<T> a)
does not suffice either because it is still too restrictive. Suppose the BankAccount
class implements Comparable<BankAccount>
. Then the subclass SavingsAccount
also implements Comparable<BankAccount>
and not Comparable<SavingsAccount>
.
We will call the method with the raw ArrayList
parameter the "legacy method". You can pass a parameterized type, such as ArrayList<String>
or ArrayList<BankAccount>
to the legacy method. This is not completely safe - after all, the legacy method might insert an object of the wrong type. Nevertheless, your program will compile without a warning.
For example, compiling and running the following program does not produce a warning or error:
import java.util.ArrayList; public class Test { public static void print(ArrayList list) { for (int i = 0; i < list.size(); i++) { System.out.println(list.get(i)); } } public static void main(String args[]) { ArrayList<String> strList = new ArrayList<String>(); strList.add("A"); strList.add("B"); strList.add("C"); print(strList); } }
We will call the method with the raw ArrayList
parameter the "legacy method".
The code calling the legacy method will compile without a warning. A warning is issued for the legacy method. When the wrong element is inserted, no error happens at that time. When the element with the wrong type is later retrieved, then a ClassCastException
occurs.
Consider this example:
import java.util.ArrayList; public class Test { public static void main(String args[]) { ArrayList<String> strList = new ArrayList<String>(); strList.add("A"); strList.add("B"); strList.add("C"); doSomethingBad(strList); String first = strList.get(0); } public static void doSomethingBad(ArrayList list) { list.add(0, new BankAccount(10000)); } }
Compiling with the -Xlint:unchecked
option yields this warning:
javac -Xlint:unchecked Test.java Test.java:17: warning: [unchecked] unchecked call to add(int,E) as a member of the raw type java.util.ArrayList list.add(0, new BankAccount(10000)); ^
We get the following run-time error:
java Test Exception in thread "main" java.lang.ClassCastException: BankAccount cannot be cast to java.lang.String at Test.main(Test.java:12)
Compiling
ArrayList<BankAccount> accounts = new ArrayList<BankAccount>(); if (accounts instanceof ArrayList<String>) { System.out.println("true"); } else { System.out.println("false"); }
produces the following error:
Test.java [15:1] illegal generic type for instanceof if (accounts instanceof ArrayList<String>) System.out.println("true"); ^
The virtual machine that executes Java programs does not work with generic classes or methods. Instead, it uses raw types, in which the type parameters are replaced with ordinary Java types. Each type parameter is replaced with its bound, or with Object
if it is not bounded. The compiler erases the type parameters when it compiles generic classes and methods.
At run time, Java uses raw types (e.g. Object
or Comparable
). Since "accounts instanceof ArrayList<String>
" cannot be translated to a run-time raw type, its use is not allowed.
You should look for the source code in a directory similar to
C:\Program Files\Java\jdk1.6.0_03\src.zip
and inside the zipped file, under java\util
you should find ArrayList.java
. Copy this file and look through it. You see immediately that the class contains an array of Object
elements.
private transient Object[] elementData;
There is a constructor:
public ArrayList(Collection<? extends E> c)
The argument is a Collection
that inherits from a class of type parameter E
. The Collection
elements are placed into the Object
array by using the following:
elementData = c.toArray();
It is expected that the toArray
method will return an Object
array. If the conversion doesn’t happen correctly, it compensates by coercing it with a copy and specifying the original class.
if (elementData.getClass() != Object[].class) { elementData = Arrays.copyOf(elementData, size, Object[].class); }
Traditional Code to collect 5 large words from an ArrayList<String>
int count = 0; ArrayList<String> resultList = new ArrayList<>(); Iterator<String> oldList = words.iterator(); while (oldList.hasNext() && count < 5) { String str = oldList.next(); if (str.length() > 10) { resultList.add(str); count++; } }
New code with Streams
resultStream = wordList.stream(); .filter(w -> w.length() > 10) .limit(5);
The new stream syntax is easier to understand.
a) This statement finds the first 100 elements that have a length greater than 10.
b) This statement finds the elements with length greater than 10 within the first 100 elements.
1) Using the Stream.of
method by listing the elements:
Stream<String> wordStream = Stream.of("Mary", "had", "a", "little", "lamb");
2) Using the Steam.of
method and an Array of objects:
String[] words = {"Mary", "had", "a", "little", "lamb"}; Stream<String> wordStream = Stream.of(words);
3) Using the stream
method of a collection:
List<String> wordList = new ArrayList<>();
Stream<String> wordStream = wordList.stream();
a) List<Integer> result = stream.collect(Collectors.toList());
b) Integer[] result = stream.toArray(Integer[]::new);
c) Use b) above and then process the wrapper array converting it to an array of primitives.
a) Stream<String> to Stream<Double>
Stream<Double> dblValues = strValues.stream() .mapToDouble(s -> Double.parseToDouble(s));
a) Stream<Double> to Stream<String>
Stream<String> strValues = dblValues.stream() .map(s -> Double.toString(s));
1. lambda body is a single expression
// returns names larger than 10 characters name -> name.length() < 10
2. lambda body uses a defined method call
// returns names larger than 10 characters name -> bigNames(name)
3. lambda body uses a functional block
// returns names larger than 10 characters name -> { int len = name.length(); if (len > 10) return name; }
Three different ways of printing when the optional value is present and not printing when it is not are as follows.
1. System.out.print(optResults.orElse("")); 2. optResults.ifPresent(v -> System.out.print(v)); 3. if (optResults.isPresent()) { System.out.print(optResults.get()): }
Options 1 and 3 above can be configured to print "None" if the optional value is not present.
1. Create an IntStream from individual integers or from an array.
IntStream stream = IntStream.of(3, 1, 4, 1, 5, 9);
int[] values = . . .;
stream = IntStream.of(values);
2. Create an IntStream from a range of consecutive integers.
IntStream stream = IntStream.range(a, b);
3. Create an IntStream from a random range of integers: inclusive of loBound and exclusive of hiBound.
Random generator = new Random();
IntStream dieTosses = generator.ints(loBound, hiBound);
4. Create an IntStream from a String objects Unicode points.
IntStream codePoints = str.codePoints();
5. Create an IntStream from another stream by applying some function.
IntStream lengths = words.mapToInt(w -> w.length());
Options 1, 3, and 5 can be used to create a DoubleStream with the corresponding methods used.
a) Using the mapToInt approach:
int maxOfLengths = words
.mapToInt(w -> w.length())
.max();
b) Using the stream.max approach on a non-primitive stream:
final Comparator<String> comp = (s1, s2) -> Integer.compare( s1.length(), s2.length()); int maxOfLengths = words .max(comp);The advantage of the first approach is that it does not need a comparator for primitive type streams.
findFirst findAny min max count toArray collect forEach allMatch anyMatch noneMatch
averagingDouble averagingInt
averagingLong
counting
groupingBy
joining
maxBy
minBy
summingDouble summingInt
summingLong
toList
toSet
The intent of the .orElse
values is to provide a meaningful value when the compution cannot be completed. For example, the average().orElse(0)
provides the value 0 when the average cannot be computed beacause there are no values to average and the result would require dividing by zero. Both min().orElse(Double.MAX_VALUE)
and max().orElse(Double.MIN_VALUE)
provide a default value when calculating the minimum and maximum of a set of values.
Yes, you can. You have to set the frame's layout (actually the frame's content pane layout) to FlowLayout
:
frame.setLayout(new FlowLayout());
Then, you can just add the user interface components, one by one:
frame.add(new JButton("A")); frame.add(new JButton("B"));
A layout manager is an object that arranges components inside a container. The advantage of a layout manager is that the layout works even if the size of the components or the container changes. That can happen because components have different sizes in different look and feel implementations, or simply because the user resizes the container.
If you place a single button in the CENTER
area, it grows to fill the entire center area.
If you place multiple buttons in the SOUTH
area, they are put on top of each other. Only the last one shows up.
If you omit the second parameter of the add
method when adding a component to a container that uses a border layout, then the component is added to the center.
The second button appears nested (inside) the first button.
The drawback of the grid layout is that the first and second column have the same size (because each cell gets the same size in a grid layout). It would be nicer if the first column was much narrower, so that there would be more room for the sliders.
Unfortunately, that isn't easy to achieve with the basic layouts. You can use (3,1) grid layout with 3 flow layouts, each of which contains a label and a slider. But then the sliders won't line up. Or you can use a border layout, put one (3,1) grid layout to hold the labels to the West and another grid layout to hold the sliders in the center. That will probably work OK, because labels and sliders have approximately the same height.
The best way to achieve a good layout is to use the GridBagLayout
, but that layout manager is quite complex and is not used in this book.
The GridBagLayout
, like the GridLayout
, arranges components in a grid of rows and columns. But, in the GridBagLayout
the rows and columns do not have to have the same size, a component can span several cells, and components do not have to fill the entire area. All this comes at the cost of increased complexity.
When creating a check box or radio button, you can specify an icon to use in the constructor:
new JRadioButton("JRadioButton", new ImageIcon("icon.gif")); new JCheckBox("JCheckBox", new ImageIcon("icon.gif"));
You cannot set an icon in a JComboBox
component.
Radio buttons are used to select exactly one of a number of options.
Check boxes are used to select any combination of a number of options.
The button group for radio buttons is responsible for turning the previously selected button off when another button is selected. That ensures that only one radio button from the group is selected at any time. You don't need a button group for check boxes because in a group of check boxes, it is OK to have several check boxes selected.
The menu bar is the horizontal bar at the top of a window.
A menu is a vertical arrangement of submenus and menu items.
A menu item is an individual item inside a menu. Only menu items generate action events.
The constructor with no arguments produces a slider with a range of min=0, max=100. Simply replacing the sliders in our program with default sliders would not have worked - there would be no way to specify white (red=green=blue=255). The maximum value (red=green=blue=100) would be a dark gray.
It would have been possible to fix the program by scaling the slider values from the range [0,100] to the range [0,255], but that would have been more work than using the other constructor.
You construct a vertical slider like this:
JSlider mySlider = new JSlider(SwingConstants.VERTICAL, min, max, value);
You can also use JSlider.VERTICAL
because JSlider
implements the SwingConstants
interface.
Action events describe one-time changes, such as button clicks. Change events describe continuous changes, such as moving a JSlider
. In the case of a JComboBox
, the events generated are one-time changes, not continuous changes.
Use the JList
component to show a list of items, with several items visible at the same time.
The Swing documentation lists the following components:
JButton JCheckBox JCheckBoxMenuItem JColorChooser JComboBox JComponent JDesktopPane JDialog JEditorPane JFileChooser JFormattedTextField JFrame JInternalFrame JLabel JLayeredPane JList JMenu JMenuBar JMenuItem JOptionPane JPanel JPasswordField JPopupMenu JProgressBar JRadioButton JRadioButtonMenuItem JRootPane JScrollBar JScrollPane JSeparator JSlider JSpinner JSplitPane JTabbedPane JTable JTextArea JTextField JTextPane JToggleButton JToolBar JToolTip JTree JViewport JWindow
Not all of them correspond to visible components, but about 30 of them do.
The following statistics are valid for Java 6.
Here are the 31 methods of JProgressBar
:
addChangeListener(ChangeListener l) createChangeListener() fireStateChanged() getAccessibleContext() getChangeListeners() getMaximum() getMinimum() getModel() getOrientation() getPercentComplete() getString() getUI() getUIClassID() getValue() isBorderPainted() isIndeterminate() isStringPainted() paintBorder(Graphics g) paramString() removeChangeListener(ChangeListener l) setBorderPainted(boolean b) setIndeterminate(boolean newValue) setMaximum(int n) setMinimum(int n) setModel(BoundedRangeModel newModel) setOrientation(int newOrientation) setString(String s) setStringPainted(boolean b) setUI(ProgressBarUI ui) setValue(int n) updateUI()
In addition, JProgressBar
inherits 130 methods from JComponent
, 57 methods from Container
, 150 methods from Component
, 10 methods from Object
, All together, the class has 378 methods!
Inheritance is not a requirement for JFrame. By extending the class, however, you can add instance variables and call helper methods you might want to use to create components.
A label is a display area for a short text string or an image, or both. The text cannot be edited.
A text field holds a single line of editable text. A text area displays multiple lines of editable text.
The append
method is declared in the JTextArea
class.
The setText
method is declared in the JTextComponent
class.
The getGraphics
method is declared in the JComponent
class.
JTextArea
can hold multiple lines of text. The program shows how the interest accumulates over time. So JTextArea
is used in the program to accumulate the results into one text area. An array of labels could be created in the actionListener
to display each result in a separate label.
Streams handle binary data, accessing sequences of bytes. Readers and writers handle data in text form, accessing sequences of characters.
The exercise should say PrintWriter, not FileWriter. Most text editors will automatically convert the text using the proper encoding. In Microsoft Word, the software detects the encoding and asks the user to confirm it before opening the file. If a different encoding is specified, the values in the file are interpreted as different characters.
import java.io.PrintWriter; import java.io.FileNotFoundException; import java.io.UnsupportedEncodingException; public class EncodingTester { public static void main(String[] args) throws FileNotFoundException, UnsupportedEncodingException { PrintWriter out = new PrintWriter("output1.txt", "UTF-8"); out.println("If you write to a file reader, there will be a " + "compile-time error because input files don't support output " + "operations such as print.\n If you write to a random access " + "file that was opened for reading only, there will be an " + "exception."); PrintWriter out2 = new PrintWriter("output2.txt", "UTF-16"); out2.println("If you write to a file reader, there will be a " + "compile-time error because input files don't support output " + "operations such as print.\n If you write to a random access " + "file that was opened for reading only, there will be an " + "exception."); out.close(); out2.close(); } }
You need to open a RandomAccessFile
to open a file for both reading and writing. For example,
RandomAccessFile f = new RandomAccessFile("bank.dat", "rw");
If you write to a file reader, there will be a compile-time error because input files don't support output operations such as print
.
If you write to a random access file that was opened for reading only, there will be an exception.
To break the Caesar cipher, you can try all 25 keys (b...z) to decrypt the message. Look at the decryptions and see which one of them corresponds to English text.
If you try to save an object to a object stream and the object is not serializable, an exception is thrown.
java.lang.Boolean java.lang.Character java.lang.Double java.lang.Integer java.lang.String
java.lang.Throwable
and its subclasses, i.e., all exceptions
java.io.File
If you simply save the entire ArrayList
, you do not have to save the number of elements. If you saved a collection manually, you'd first have to write out the length, then all entries. When reading the collection back in, you'd have to read in the length, then allocate sufficient storage, and then read and store all entries. It is much simpler to just write and read the ArrayList
and let the serialization mechanism worry about saving and restoring the length and the entries.
Sequential access forces you to read all bytes in a file in order, starting from the first byte and progressing through the last byte. Once a byte has been read, it cannot be read again, except by closing and reopening the file. With random access, you can repeatedly select any position in the file for reading or writing.
The file pointer denotes the current position in a random access file for reading and writing. You move it with the seek
method of the RandomAccessFile
class. You get the current position with the getFilePointer
method. The position is the number of bytes from the beginning of the file, as a long
integer, because files can be longer than 2GB (the longest length representable with an int
).
f.seek(0); f.seek(f.length() - 1); f.seek(f.length() / 2);
It is legal to move the file pointer past the end of the file. If you write to that location, the file will be enlarged. If you read from that location, an exception is thrown.
You can't move the file pointer on System.in
. It is not a RandomAccessFile
, therefore a call to the seek
method is a compile-time error.
Passing an absolute path to the resolve method returns the passed-in path.
The following example shows usage of relativize with both files and directories:
Path path01 = Paths.get("Foo.txt"); Path path02 = Paths.get("Bar.txt"); Path path03 = Paths.get("/Java/JavaTemp/Foo.txt"); Path path04 = Paths.get("/Java/2015"); Path path01_to_path02 = path01.relativize(path02); System.out.println(path01_to_path02); Path path02_to_path01 = path02.relativize(path01); System.out.println(path02_to_path01); Path path03_to_path04 = path03.relativize(path04); System.out.println(path03_to_path04); Path path04_to_path03 = path04.relativize(path03); System.out.println(path04_to_path03);
Would result in the following:
..\Bar.txt ..\Foo.txt ..\..\2015 ..\JavaTemp\Foo.txt
Depth first order means that it will traverse downward through the directories until it reaches the bottom of the tree. From there it will handle all siblings at each level as it moves through the tree in a recursive nature. Directory children are listed after their parents. Files will be listed before directories. The listing of each directory will be displayed alphabetically.
The reason is that the code calls run
on the GreetingRunnable
objects so they run in sequence in the same thread. It should create a thread for each and call start
on the threads.
Yes, the thread scheduler may just switch to thread B while thread A is sleeping. Then thread B may also go to sleep, and the scheduler may find both thread A and B sleeping at the same time.
Yes, for example, thread A can be printing to the console while the thread scheduler decides to give the time slice to thread B. Thread B gets its turn and resumes working on whatever it was doing.
There is one MAIN thread in the program plus other threads for the GUI. For example, when one does not implement the EXIT_ON_CLOSE
feature, the program will not end after a user closes the GUI window.
The stop
method for stopping a thread is deprecated because a thread may have occupied some resources, such as database connections. If we just stop the thread without releasing the resources, the database will eventually run out of connections for others that have work to do.
A thread can be terminated by calling threadName.interrupt()
.
Suppose a long computation is being carried out in a thread, the computation is not yet completed, and the user is no longer interested in the result and wishes to terminate the computation. Then it is time to terminate the thread.
The problem is that the threads cannot be terminated by interrupting them.
A race condition occurs if the effect of multiple threads on shared data depends on the order in which the threads are scheduled. Race conditions can be avoided using lock objects to control the threads that attempt to manipulate a shared resource.
If the remove
method goes to sleep after it removes an element but before it updates currentSize
, the add
method will use the wrong value when it increments currentSize
.
Similarly, if the remove
method goes to sleep after it removes an element but before it updates currentSize
, the growBufferIfNecessary
method may increase the buffer size and copy the removed element to the new buffer.
If push
goes to sleep before setting first
to the new node, an attempt to pop
the stack may return an error (if first
is null
) or the wrong value.
If pop
goes to sleep before setting first
to first.next
, push
could set the new node to link to the element that was to be removed by pop
. When pop
wakes, it will not remove the desired element, but rather set it to first
, thereby eliminating the new first
created by push
.
If the remove
method goes to sleep after it removes an element but before it updates head
, the growBufferIfNecessary
method will set head to the wrong value.
Similarly, if the remove
method goes to sleep after it removes an element but before it updates currentSize
, the growBufferIfNecessary
method may increase the buffer size, copy the removed element to the new buffer, and set tail
to the wrong value.
21.11
A deadlock occurs if no thread can proceed because each thread is waiting for another thread to do some work first.
One important way to avoid deadlocks is to call signalAll/notifyAll
after a state change that may allow waiting threads to proceed. But there are other potental causes for deadlocks that are not so easily remedied.
The sleep
method puts the current thread to sleep for a given number of milliseconds, after which it wakes up. The await
method blocks the thread and allows another thread to acquire the object lock. In other words, sleep
will sleep for a specified period of time; a waiting thread is blocked until another thread calls signalAll
or signal
on the condition object for which the thread is waiting.
It will wait forever.
There are two threads: the animation thread and the GUI thread. They share a resource, namely the array of values. But the animation thread is almost 100% certain to be sleeping when the GUI thread paints the graph. If for some reason, the display was repainted while the animation thread was modifying it, then it would display the wrong image. Thus, no synchronization is needed.
The array to be sorted is filled automatically with random numbers. There is no need for user input in the animation.
Answers will vary. Some IP addresses may be dynamically assigned by the Internet provider.
Yes. It needs the computer's IP address (or domain name) and the port number used by the desired application.
A port number is an integer between 0 and 65,535. It indicates the program that should receive data coming to the computer over TCP. Yes, a computer can receive data on different ports.
A server is a provider of services. A client is a consumer of services. Usually, multiple clients can connect to a server at one time.
A socket is an object that encapsulates a TCP/IP connection. A Socket
object is used by client applications to connect to the server for services. A ServerSocket
object is used by server applications to listen for client connections.
The socket constrcutor throws an UnknownHostExeption
if it can not find the host.
java.net.ConnectException
will be thrown. The exception message is Connection refused: connect
.
It uses the address of the computer to which you want to connect.
The purpose of the accept
method is to wait and listen for a new client socket.
You will use an InputStream
obtained from the Socket.
Because people usually want to communicate with the server by sending and receiving text. Then, turning the streams into scanners and writers is preferable.
Print writers buffer their outputs. They will not send the characters in the buffer until the buffer is full. That is why we sometimes needs to flush the output stream or writer in order make sure every character is send to the server.
HTTP, which stands for Hypertext Transfer Protocol, is the protocol that defines communication between web browsers and web servers.
HTML, which stands for Hypertext Markup Language, is a document format (with tags such as <h1>
or <ol>
) that describes the structure of a document, including headings, bulleted lists, images, hyperlinks, and so on.
(user input is in bold)
~$ telnet horstmann.com 80 Trying 67.220.118.65... Connected to horstmann.com. Escape character is '^]'. HEAD / HTTP/1.1 Host: horstmann.com Blank line HTTP/1.1 200 OK Date: Fri, 06 Jan 2012 14:54:13 GMT Server: Apache/2.2.22 (Unix) mod_ssl/2.2.22 OpenSSL/0.9.7a mod_auth_passthrough/2.1 mod_bwlimited/1.4 FrontPage/5.0.2.2635 mod_fcgid/2.3.5 Sun-ONE-ASP/4.0.3 Last-Modified: Thu, 08 Dec 2011 06:19:43 GMT ETag: "305e572-1944-4b38ea7747dc0" Accept-Ranges: bytes Content-Length: 6468 Content-Type: text/html Connection closed by foreign host. ~$
~$ openssl s_client -connect pop.gmail.com:995 CONNECTED(00000003) depth=1 C = US, O = Google Inc, CN = Google Internet Authority verify error:num=20:unable to get local issuer certificate verify return:0 --- Certificate chain 0 s:/C=US/ST=California/L=Mountain View/O=Google Inc/CN=pop.gmail.com i:/C=US/O=Google Inc/CN=Google Internet Authority 1 s:/C=US/O=Google Inc/CN=Google Internet Authority i:/C=US/O=Equifax/OU=Equifax Secure Certificate Authority --- Server certificate -----BEGIN CERTIFICATE----- MIIDWjCCAsOgAwIBAgIKaNGwUQADAAAirzANBgkqhkiG9w0BAQUFADBGMQswCQYD VQQGEwJVUzETMBEGA1UEChMKR29vZ2xlIEluYzEiMCAGA1UEAxMZR29vZ2xlIElu dGVybmV0IEF1dGhvcml0eTAeFw0xMTAyMTYwNDQwMzdaFw0xMjAyMTYwNDUwMzda MGcxCzAJBgNVBAYTAlVTMRMwEQYDVQQIEwpDYWxpZm9ybmlhMRYwFAYDVQQHEw1N b3VudGFpbiBWaWV3MRMwEQYDVQQKEwpHb29nbGUgSW5jMRYwFAYDVQQDEw1wb3Au Z22haWwuY29tMIGfMA0GCSqGSIb3DQEBAQUAA4GNADCBiQKBgQCc8H+gCR0/95Tb Lkj7jdj0oXmfGzsSswdSjo6yWdcHpjv6cbaakHakclxBs47M8Gs3fJxuNqVMpt2Q YorJuoBuVZjM59/rIeJwmOwSlzf1POxpEFUvm1ASAeBnBheBt0Fv+BCfI8DjZKgn SvHCqQJfNgxpJBXOLbFVjBsPqF8w6wIDAQABo4IBLDCCASgwHQYDVR0OBBYEFHzY GJFnJ+gmONoIX6cyTAEl9ePYMB8GA1UdIwQYMBaAFL/AMOv1QxE+Z7qekfv8atrj axIkMFsGA1UdHwRUMFIwUKBOoEyGSmh0dHA6Ly93d3cuZ3N0YXRpYy5jb20vR29v Z2xlSW50ZXJuZXRBdXRob3JpdHkvR29vZ2xlSW50ZXJuZXRBdXRob3JpdHkuY3Js MGYGCCsGAQUFBwEBBFowWDBWBggrBgEFBQcwAoZKaHR0cDovL3d3dy5nc3RhdGlj LmNvbS9Hb29nbGVJbnRlcm5ldEF1dGhvcml0eS9Hb29nbGVJbnRlcm5ldEF1dGhv cml0eS5jcnQwIQYJKwYBBAGCNxQCBBQeEgBXAGUAYgBTAGUAcgB2AGUAcjANBgkq hkiG9w0BAQUFAAOBgQB0GTFAoMNxCFJ3aVMzvrZgCD9hG2Ee3Sx5GMQ0yDjcFvzS ZIci9Gr18HMVBusIuFLw8TvBD7PEXtZLhh6hbj+Xdg9CIqlIjdqJFRixJU06xqKH akIhNBDxy5ky3VugqlGdysbMjo/aXCFdl42GproXdUPH24Erljur885LklMk/g== -----END CERTIFICATE----- subject=/C=US/ST=California/L=Mountain View/O=Google Inc/CN=pop.gmail.com issuer=/C=US/O=Google Inc/CN=Google Internet Authority --- No client certificate CA names sent --- SSL handshake has read 1738 bytes and written 347 bytes --- New, TLSv1/SSLv3, Cipher is RC4-SHA Server public key is 1024 bit Secure Renegotiation IS supported Compression: NONE Expansion: NONE SSL-Session: Protocol : SSLv3 Cipher : RC4-SHA Session-ID: E807CC6FD8596BE65B9F89276AA0826CAF767013986609117D7FB569D3A41892 Session-ID-ctx: Master-Key: EF204E4804C225E5CEB46D1A168FF3812DAB67144C4F9A1963F830C63EEEA245B6E15872DEE22A98A3C0DEF74491B22B Key-Arg : None PSK identity: None PSK identity hint: None Start Time: 1325862776 Timeout : 7200 (sec) Verify return code: 20 (unable to get local issuer certificate) --- +OK Gpop ready for requests from 108.81.230.128 f5pf97180872pbc.16 user xxx.xxx@xxx.xxx +OK send PASS pass xxxxxxx +OK Welcome. list +OK 286 messages (6055394 bytes) 1 10738 2 3787 3 10578 4 3371 5 2677 6 5064 ... 278 18139 279 6694 280 6118 281 4473 282 7932 283 2918 284 7725 285 34395 286 101699 . retr 284 +OK message follows Delivered-To: xxx.xxx@xxx.xxx Received: by 10.229.142.136 with SMTP id q8cs472qcu; Fri, 19 Nov 2010 19:23:00 -0800 (PST) Received: by 10.231.169.206 with SMTP id a14mr1065068ibz.13.1290223370535; Fri, 19 Nov 2010 19:22:50 -0800 (PST) Received: by Domino with HTTP; Tue, 8 Jun 2010 23:01:48 -0700 Message-ID: <EE4E633C3CB25FD8AFFBE30579D5FCFC@sjsu.edu> X-Notes-Message-ID: <DE3532AB794549BF8699DD5C5F91CA0D@ad.science.sjsu.edu> MIME-Version: 1.0 Date: Tue, 8 Jun 2010 23:01:48 -0700 From: xxx.xxx@xxx.xxxx To: xxx.xxx@xxx.xxx Reply-To: xxx.xxx@xxx.xxx Subject: RE: sharing question bank. Content-type: multipart/alternative; Boundary="0__=07BBFD72DF8227CA8f9e8a93df938690918c07BBFD72DF8227CA" Content-Disposition: inline --0__=07BBFD72DF8227CA8f9e8a93df938690918c07BBFD72DF8227CA Content-type: text/plain; charset=US-ASCII message body --0__=07BBFD72DF8227CA8f9e8a93df938690918c07BBFD72DF8227CA-- . quit +OK Farewell. read:errno=0
One can use high level APIs such as the URLConnection
and HttpURLConnection
classes.
A URL
instance represents a Uniform Resource Locator, a pointer to a "resource" on the World Wide Web.
A URLConnection
instance can be used both to read from and to write to the resource referenced by the URL.
A URL, or Uniform Resource Locator, is a pointer to an information resource (such as a web page or an image) on the World Wide Web.
You create a URL object from a URL string, such as new URL("http://horstmann.com/")
. To connect to the URL, use the openConnection
method. That yields a URLConnection
object. Call its getInputStream
method to get an InputStream
.
CREATE TABLE Person ( Name VARCHAR(30), Driver_License_No CHAR(16), Address VARCHAR(100) ) CREATE TABLE Car ( Vehicle_ID INTEGER, Owner_License CHAR(16), Manufacturer VARCHAR(20), Type VARCHAR(10), Year INTEGER )
CREATE TABLE LibraryBook ( Library_ID INTEGER, ISBN CHAR(13), Patron_ID INTEGER ) CREATE TABLE BookData ( ISBN CHAR(13), Author VARCHAR(40), Title VARCHAR(40) ) CREATE TABLE Patron ( Patron_ID INTEGER, Name VARCHAR(40), Street VARCHAR(40), City VARCHAR(30), State CHAR(2), Zip CHAR(5) )
CREATE TABLE Coin ( Name VARCHAR(20), Value INTEGER ) CREATE TABLE Purse ( Owner_Name VARCHAR(30), Purse_ID INTEGER ) CREATE TABLE Coin_Sets ( Purse_ID INTEGER, Coin_Name VARCHAR(20), Quantity INTEGER )
CREATE TABLE Student ( Student_ID INTEGER, Name VARCHAR(30) ) CREATE TABLE Class ( Class_ID INTEGER, Classroom_ID INTEGER, Professor_ID INTEGER, Title VARCHAR(30) ) CREATE TABLE Professor ( Professor_ID INTEGER, Name VARCHAR(30) ) CREATE TABLE Classroom ( Classroom_ID INTEGER, Location VARCHAR(20) ) CREATE TABLE Enrollment ( Student_ID INTEGER, Class_ID INTEGER )
CREATE TABLE Book ( ISBN INTEGER, Author VARCHAR(30), Title VARCHAR(50), ) INSERT INTO Book VALUES ( 123456789, 'Cay Horstmann', 'Big Java' ) INSERT INTO Book VALUES ( 234523897, 'Philip M. Lewis', 'Database and Transaction Processing' ) INSERT INTO Book VALUES ( 135754523, 'Mark Birbeck', 'Professional XML 2nd Edition' ) INSERT INTO Book VALUES ( 458734515, 'Damon Hougland', 'Core JSP' )
CREATE TABLE Car ( Car_ID INTEGER, Manufacturer VARCHAR(20), Model VARCHAR(10), Year INTEGER ) INSERT INTO Car VALUES ( 145460985, 'Honda', 'Civic', 1997 ) INSERT INTO Car VALUES ( 324052349, 'Ford', 'Ranger', 1987 )
SELECT Description FROM Product;
SELECT Name FROM Customer WHERE State = 'CA'
SELECT Name FROM Customer WHERE State = 'CA' OR State = 'NV'
SELECT Name FROM Customer WHERE State <> 'HI'
SELECT Name FROM Customer, Invoice WHERE Customer.Customer_Number = Invoice.Customer_Number AND Invoice.Payment = 0
SELECT Product.Description FROM Customer, Product, Invoice, LineItem WHERE Customer.Customer_Number = Invoice.Customer_Number AND Invoice.Invoice_Number = LineItem.Invoice_Number AND LineItem.Product_Code = Product.Product_Code AND Customer.State = 'CA'
SELECT Product.Description, LineItem.Quantity FROM Product, LineItem WHERE LineItem.Invoice_Number = 11731 AND LineItem.Product_Code = Product.Product_Code
SELECT SUM(LineItem.Quantity) FROM LineItem WHERE LineItem.Invoice_Number = 11731
SELECT SUM(Product.Price * LineItem.Quantity) FROM Product, LineItem WHERE LineItem.Invoice_Number = 11731 AND LineItem.Product_Code = Product.Product_Code
UPDATE Product SET Price = Price * 1.10
DELETE FROM Customer WHERE State = 'CA'
Oracle
JDBC driver: oracle.jdbCustomer.driver.OracleDriver URL: jdbc:oracle:oci8:@
MySQL
JDB driver: com.mysql.jdbc.Driver URL: jdbc:mysql://localhost/
A typical answer is
/home/username/jdk1.7.0_01/db/lib/derby.jar
or
c:\Program Files\java\jdk1.7.0_01\db\lib\derby.jar
Column 1 | Column 2 |
a | 3 |
b | 4 |
c | 5 |
d | 2 |
e | 1 |
The Connection
object makes a connection to the database and has a method that creates a Statement
object. One uses statements to execute SQL commands.
SELECT
yields a result set, INSERT
and UPDATE
yield an update count, CREATE TABLE
and DROP TABLE
yield neither.
1. An iterator initially points to the first element of the collection. The result set initially points before the first element, and you must advance it once in order to fetch the first element.
2. Conceptually, iteration is composed of three operations: test, fetch, and advance. The java.util.Iterator
groups the fetch and advance operations into a single method (next
). The ResultSet
groups the test and advance operations into a single method (also called next
).
HTML: "<li>" is same as "<LI>" XML: "<LI>" is not the same as "<li>" // case sensitive HTML: <img src="hamster.jpeg"> XML: <img src="hamster.jpeg"/> // must provide end-tag HTML: <img src="hamster.jpeg" width=400 height=300> XML: <img src="hamster.jpeg" width="400" height="300"/> // quote attribute values
<bankaccount> <accountnumber>1111</accountnumber> <interestrate>5</interestrate> <balance>15356</balance> </bankaccount>
<bankaccount> / | \ / | \ / | \ <accountnumber> <interestrate> <balance> / | \ 1111 5 15356
The exercise should refer to Figure 5.
<sentence> <noun-phrase> <article>the</article> <adjective-list> <adjective>hungry</adjective> </adjective-list> <noun>hamster</noun> </noun-phrase> <verb>eats</verb> <noun-phrase> <article>a</article> <adjective-list> <adjective>quick</adjective> <adjective-list> <adjective>brown</adjective> </adjective-list> </adjective-list> <noun>fox</noun> </noun-phrase> </sentence>
<book> <authorname>Cay Horstmann</authorname> <title>Big Java, Late Objects</title> <year>2013</year> </book>
<book> <authorname>Cay Horstmann</authorname> <title>Big Java</title> <year>2015</year> <language>EN</language> </book>
We choose to represent the language as an element because it is not used to interpret the element content. If the software actually translated the title into another language, then an attribute might be more appropriate, but library and shopping software will generally not care about the book's language - it will simply present the language as an informational item to the user, which is no different than the title and author information.
Mixed content means an element can contain text, sub-elements, or both.
Mixed content makes it more difficult to write a strict DTD because you can't specify any rules for the elements that are mixed with the text. For example, you cannot control the order in which elements appear.
<purse> <coins> <coin> <value>0.25</value> <name>quarter</name> </coin> <quantity>3</quantity> </coins> <coins> <coin> <value>0.10</value> <name>dime</name> </coin> <quantity>1</quantity> </coins> <coins> <coin> <value>0.05</value> <name>nickel</name> </coin> <quantity>2</quantity> </coins> </purse>
Because the paint program does not know why one arranged the graphical elements in a certain way, it cannot update the arrangement in a logical way when the image changes.
a. 0.5
b. quarter
c. en
d. value
e. 2
f. 1
a. /purse/coin[1]/value
b. count(/purse/coin)
c. name(/purse/coin[1]/*[1])
d. name(/purse/coin[1]/name/@*[1])
e. /purse/coin[2]/name/@lang
The output of p.getDescription()
can contain characters that are invalid XML.
If a description contains a <
sign, the XML parser will interpret it as the start of a tag. If it contains an &
symbol, the XML parser will interpret it as the start of an entity reference.
In this case, the remedy is to replace all &
with &
and all <
with <
.
If you generated code inside attributes, you would also have to escape " symbols. Knowing what to replace where requires a detailed understanding of the XML specification. It is much better to use an XML library to generate XML.
<!DOCTYPE bankaccounts [ <!ELEMENT bankaccounts (bankaccount*)> <!ELEMENT bankaccount (accountnumber, interestrate, balance)> <!ELEMENT accountnumber (#PCDATA)> <!ELEMENT interestrate (#PCDATA)> <!ELEMENT balance (#PCDATA)> ]>
<!DOCTYPE patron [ <!ELEMENT patron (name, phonenumber, book*)> <!ELEMENT name (#PCDATA)> <!ELEMENT phonenumber (#PCDATA)> <!ELEMENT book (bid, author, title)> <!ELEMENT bid (#PCDATA)> <!ELEMENT author (#PCDATA)> <!ELEMENT title (#PCDATA)> ]>
<!DOCTYPE productlist [ <!ELEMENT productlist (product*)> <!ELEMENT product (name, price, score)> <!ELEMENT name (#PCDATA)> <!ELEMENT price (#PCDATA)> <!ELEMENT score (#PCDATA)> <!ATTLIST price currency CDATA #IMPLIED> ]>
<!DOCTYPE invoice [ <!ELEMENT invoice (number, address, items)> <!ELEMENT number (#PCDATA)> <!ELEMENT address (name, company, street, city, state, zip)> <!ELEMENT name (#PCDATA)> <!ELEMENT company (#PCDATA)> <!ELEMENT street (#PCDATA)> <!ELEMENT city (#PCDATA)> <!ELEMENT state (#PCDATA)> <!ELEMENT zip (#PCDATA)> <!ELEMENT items (item*)> <!ELEMENT item (product, quantity)> <!ELEMENT product (description, price)> <!ELEMENT description (#PCDATA)> <!ELEMENT price (#PCDATA)> <!ELEMENT quantity (#PCDATA)> ]>
<!DOCTYPE sentence [ <!ELEMENT sentence (noun-phrase, verb, noun-phrase)> <!ELEMENT noun-phrase (article, adjective-list, noun)> <!ELEMENT article (#PCDATA)> <!ELEMENT adjective-list (adjective, adjective-list?) > <!ELEMENT adjective (#PCDATA)> <!ELEMENT noun (#PCDATA)> <!ELEMENT verb (#PCDATA)> ]>
<!DOCTYPE expression [ <!ELEMENT expression (term, (expression, additive-operator, term)?)> <!ELEMENT additive-operator (#PCDATA)> <!ELEMENT term (factor, (term, multiplicative-operator, factor)?)> <!ELEMENT multiplicative-operator (#PCDATA)> <!ELEMENT factor (integer | (lparen, expression, rparen))> <!ELEMENT lparen (#PCDATA)> <!ELEMENT rparen (#PCDATA)> <!ELEMENT integer (minus?, digits)> <!ELEMENT minus (#PCDATA)> <!ELEMENT digits (digit+)> <!ELEMENT digit (#PCDATA)> ]>
The language is HTML.
Images:
<img class="sideimage" alt="Photo of Cay Horstmann" src="images/cay-rowing.gif" /> <img alt="" src="images/violet.jpg" style="border: 0px solid ; width: 73px; height: 76px;" title="" /> <img alt="Zork 1 Logo" height="78" src="images/zork1.gif" width="99" />
Links: (there are many)
An email link:<a href="mailto:cay@horstmann.com">cay@horstmann.com</a>
A link to a file: <a href="caypubkey.txt">PGP Key</a>
A link to another site: <a href="http://www.uni-kiel.de/">Christian-Albrechts-Universität</a>
<a href="http://www.kiel.de/">Kiel</a> <a href="http://www.syr.edu">Syracuse University</a> <a href="http://www.umich.edu">University of Michigan</a
Bullets: (there are several like this list)
<ul> <li><a href="http://www.java.net/blogs/cayhorstmann/">My Java blog</a></li> <li><a href="https://plus.google.com/117406678785944293188/posts">My Google+ page</a></li> <li><a href="http://www.sjsu.edu/people/cay.horstmann">My SJSU course page</a></li> <li><a href="quotes.html">Memorable quotes</a></li> <li><a href="resume.html">My resume</a></li> <li>Fellow Horstmanns who are interested in the family genealogy may want to turn to <a href="http://www.family-horstmann.net">Bernhard Horstmann's site</a></li> </ul>
Input elements: none
The user data is after the equal signs in the last line (e.g., jqpublic, secret). login=log%20in
means the value generated by a mouse press on the submit button named login that has the label "Log in".
A JSF page contains HTML and JSF tags.
The JSF container is server-side software that converts a JSF page to an HTML page, replacing all JSF tags with text and HTML tags.
A bean is a Java class with a default constructor and getter/setter methods that allow access to its properties.
A bean property is a value of a bean that can be accessed through getter and setter methods.
Yes, because it allow users to get and set its properties, and it has a default constructor.
To separate the presentation (HTML) from the business logic (Java computation).
To see the distinction, consider an expression variable.feature
. In Java, this denotes the instance variable named feature
. In a JSF variable, this causes a method getFeature
or setFeature
to be called.
A bean is constructed when it is called in a value expression. Yes, different users accessing a JSF application will have their own instance of the bean associated with their browser.
The submit button of the login page should invoke a method that returns an outcome string. The method should return one string (such as "login_ok"
) if the user was properly authenticated and a different string (such as "login_error"
) otherwise. The faces-config.xml
file should contain navigation rules for each of these outcomes.
Component | JSF Tag | Swing Equivalent |
Text Field | h:inputText |
JTextField |
Password Field | h:inputSecret |
JPasswordField |
Text Area | h:inputTextArea |
JTextArea |
Radio Button Group | h:selectOneRadio |
JRadioButton , used with a ButtonGroup |
Checkbox | h:selectOneCheckbox |
JCheckBox |
Checkbox Group | h:selectManyCheckbox |
Use multiple JCheckBox objects |
Menu | h:selectOneMenu h:selectManyMenu |
JList |
Image | h:graphicImage |
Image (BufferedImage or VolatileImage) |
Submit Button | h:commandButton |
JButton |
In a client-server application, the business logic resides on the client machine. In a three-tier application, the business logic resides on the web server.