Java Concepts Late Objects 3rd Edition Cay S. Horstmann - Solutions

Airline seating. Write a program that assigns seats on an airplane. Assume the airplane has 20 seats in first class (5 rows of 4 seats each, separated by an aisle) and 90 seats in economy class (15 rows of 6 seats each, separated by an aisle). Your program should take three commands: add
Every BMW is a vehicle. Should a class BMW inherit from the class Vehicle? BMW is a vehicle manufacturer. Does that mean that the class BMW should inherit from the class VehicleManufacturer?
Some books on object-oriented programming recommend using inheritance so that the class Circle extends the class java.awt.Point. Then the Circle class inherits the setLocation method from the Point superclass. Explain why the setLocation method need not be overridden in the subclass. Why is it
In an airplane, each passenger has a touch screen for ordering a drink and a snack. Some items are free and some are not. The system prepares two reports for speeding up service:1. A list of all seats, ordered by row, showing the charges that must be collected.2. A list of how many drinks and
Implement a program to teach a young child to read the clock. In the game, present an analog clock, such as the one shown at left. Generate random times and display the clock. Accept guesses from the player. Reward the player for correct guesses. After two incorrect guesses, display the correct
Write a program that can be used to design a suburban scene, with houses, streets, and cars. Users can add houses and cars of various colors to a street. Write more specific requirements that include a detailed description of the user interface. Then, discover classes and methods, provide UML
Write a simple graphics editor that allows users to add a mixture of shapes (ellipses, rectangles, and lines in different colors) to a panel. Supply commands to load and save the picture. Discover classes, supply a UML diagram, and implement your program.
A file contains a set of records describing countries. Each record consists of the name of the country, its population, and its area. Suppose your task is to write a program that reads in such a file and prints• The country with the largest area.• The country with the largest population.• The
Discover classes and methods for generating a student report card that lists all classes, grades, and the grade point average for a semester. Produce a set of CRC cards, a UML diagram, and a set of javadoc comments.
Consider the following problem description:Users place coins in a vending machine and select a product by pushing a button. If the inserted coins are sufficient to cover the purchase price of the product, the product is dispensed and change is given. Otherwise, the inserted coins are returned to
Consider the following problem description:Employees receive their biweekly paychecks. They are paid their hourly rates for each hour worked; however, if they worked more than 40 hours per week, they are paid overtime at 150 percent of their regular wage. What classes should you use to implement a
Consider the following problem description:Customers order products from a store. Invoices are generated to list the items and quantities ordered, payments received, and amounts still due. Products are shipped to the shipping address of the customer, and invoices are sent to the billing address.
The following method was known to the ancient Greeks for computing square roots. Given a value x > 0 and a guess g for the square root, a better guess is (g + x/g) / 2. Write a recursive helper method public static squareRootGuess(double x, double g). If g2 is approximately equal to x, return g,
The Koch Snowflake. A snowflake-like shape is recursively defined as follows. Start with an equilateral triangle:Next, increase the size by a factor of three and replace each straight line with four line segments:Repeat the process:Write a program that draws the iterations of the snowflake shape.
Implement a SubstringGenerator that generates all substrings of a string. For example, the substrings of the string "rum" are the seven strings "r", "ru", "rum", "u", "um", "m", "" First enumerate all substrings that start with the first character. There are n of them if the string has length
Implement a SubsetGenerator that generates all subsets of the characters of a string. For example, the subsets of the characters of the string "rum" are the eight strings "rum", "ru", "rm", "r", "um", "u", "m", "" Note that the subsets don’t have to be substrings—for example, "rm" isn’t a
Recursively generate all ways in which an array list can be split up into a sequence of nonempty sublists. For example, if you are given the array list [1, 7, 2, 9], return the following lists of lists:[[1], [7], [2], [9]], [[1, 7], [2], [9]], [[1], [7, 2], [9]], [[1, 7, 2], [9]],[[1], [7], [2,
Given an array list a of integers, recursively find all lists of elements of a whose sum is a given integer n.
Suppose you want to climb a staircase with n steps and you can take either one or two steps at a time. Recursively enumerate all paths. For example, if n is 5, the possible paths are:[1, 2, 3, 4, 5], [1, 3, 4, 5], [1, 2, 4, 5], [1, 2, 3, 5], [1, 4, 5]
Repeat Exercise E13.18, where the climber can take up to k steps at a time.Data from Exercise E13.18,Suppose you want to climb a staircase with n steps and you can take either one or two steps at a time. Recursively enumerate all paths. For example, if n is 5, the possible paths are:[1, 2, 3, 4,
Given an integer price, list all possible ways of paying for it with $100, $20, $5, and $1 bills, using recursion. Don’t list duplicates.
Extend the expression evaluator in Section 13.5 so that it can handle the % operator as well as a “raise to a power” operator ^. For example, 2 ^ 3 should evaluate to 8. As in mathematics, raising to a power should bind more strongly than multiplication: 5 * 2 ^ 3 is 40.
The backtracking algorithm will work for any problem whose partial solutions can be examined and extended. Provide a PartialSolution interface type with methods examine and extend, a solve method that works with this interface type, and a class EightQueensPartialSolution that implements the
Refine the program for solving the eight queens problem so that rotations and reflections of previously displayed solutions are not shown. Your program should display twelve unique solutions.
Refine the program for solving the eight queens problem so that the solutions are written to an HTML file, using tables with black and white background for the board and the Unicode character ♕ '\u2655' for the white queen.
Generalize the program for solving the eight queens problem to the n queens problem. Your program should prompt for the value of n and display the solutions.
Using backtracking, write a program that solves summation puzzles in which each letter should be replaced by a digit, such as send + more = money Other examples are base + ball = games and kyoto + osaka = tokyo.
The recursive computation of Fibonacci numbers can be speeded up significantly by keeping track of the values that have already been computed. Provide an implementation of the fib method that uses this strategy. Whenever you return a new value, also store it in an auxiliary array. However, before
What is the difference between searching and sorting?
Modify the selection sort algorithm to sort an array of integers in descending order.
It is common for people to name directories as dir1, dir2, and so on. When there are ten or more directories, the operating system displays them in dictionary order, as dir1, dir10, dir11, dir12, dir2, dir3, and so on. That is irritating, and it is easy to fix. Provide a comparator that compares
Checking against off-by-one errors. When writing the selection sort algorithm of Section 14.1, a programmer must make the usual choices of < versus <=, a.length versus a.length - 1, and from versus from + 1. This is fertile ground for off-by-one errors. Conduct code walkthroughs of the
Modify the selection sort algorithm to sort an array of coins by their value.
Sometimes, directory or file names have numbers in the middle, and there may be more than one number, for example, sec3_14.txt or sec10_1.txt. Provide a comparator that can compare such strings in a way that makes sense to humans. Break each string into strings not containing digits and digit
For the following expressions, what is the order of the growth of each? a. n+2n+1 b. n10+9n" + 20n + 145n' c. (n+1)* d. (n² +n)? g. n+log(n) h. n? +n log(n) i. 2" +n? .3 j. n + 2n n? + 0.75 e. n+0.001n f. n - 1000n2 + 10°
Write a program that automatically generates the table of sample run times for the selection sort algorithm. The program should ask for the smallest and largest value of n and the number of measurements and then make all sample runs.
The median m of a sequence of n elements is the element that would fall in the middle if the sequence was sorted. That is, e ≤ m for half the elements, and m ≤ e for the others. Clearly, one can obtain the median by sorting the sequence, but one can do quite a bit better with the following
We determined that the actual number of visits in the selection sort algorithm isand compare them withwhere f(n) = n2. T(n) = }n² + n - 3 2
Modify the merge sort algorithm to sort an array of strings in lexicographic order.
Suppose algorithm A takes five seconds to handle a data set of 1,000 records. If the algorithm A is an O(n) algorithm, approximately how long will it take to handle a data set of 2,000 records? Of 10,000 records?
Modify the selection sort algorithm to sort an array of objects that implement the Measurable interface from Chapter 9.
Bentley and McIlroy suggest the following modification to the quicksort algorithm when dealing with data sets that contain many repeated elements. Instead of partitioning as(where ≤ denotes the elements that are ≤ the pivot), it is better to partition asHowever, that is tedious to achieve
Suppose an algorithm takes five seconds to handle a data set of 1,000 records. Fill in the following table, which shows the approximate growth of the execution times depending on the complexity of the algorithm.For example, because 3,0002/1,0002 = 9, the algorithm would take nine times as long, or
Modify the selection sort algorithm to sort an array of objects that implement the Comparable interface (without a type parameter).
Implement the radix sort algorithm described in Exercise R14.22 to sort arrays of numbers between 0 and 999.Data from Exercise R14.22The radix sort algorithm sorts an array of n integers with d digits, using ten auxiliary arrays. First place each value v into the auxiliary array whose index
Sort the following growth rates from slowest to fastest growth. O(n) O(log(n) O(2") O(nvn) O(n) O(n? log(n)) O(n) O(n") O(n log(2))
Modify the selection sort algorithm to sort an array of objects, given a parameter of type Comparator (without a type parameter).
Implement the radix sort algorithm described in Exercise R14.22 to sort arrays of numbers between 0 and 999. However, use a single auxiliary array, not ten.Data from Exercise R14.22The radix sort algorithm sorts an array of n integers with d digits, using ten auxiliary arrays. First place each
What is the growth rate of the standard algorithm to find the minimum value of an array? Of finding both the minimum and the maximum?
Write a telephone lookup program. Read a data set of 1,000 names and telephone numbers from a file that contains the numbers in random order. Handle lookups by name and also reverse lookups by phone number. Use a binary search for both lookups.
Implement the radix sort algorithm described in Exercise R14.22 to sort arbitrary int values (positive or negative).Data from Exercise R14.22The radix sort algorithm sorts an array of n integers with d digits, using ten auxiliary arrays. First place each value v into the auxiliary array whose index
Implement the sort method of the merge sort algorithm without recursion, where the length of the array is an arbitrary number. Keep merging adjacent regions whose size is a power of 2, and pay special attention to the last area whose size is less.
A run is a sequence of adjacent repeated values. Describe an O(n) algorithm to find the length of the longest run in an array.
Implement the bubble sort algorithm described in Exercise R14.21.Data from Exercise R14.21.Consider the following algorithm known as bubble sort:While the array is not sorted For each adjacent pair of elements If the pair is not sorted Swap its elements. What is the big-Oh efficiency of this
Consider the task of finding the most frequent element in an array of length n. Here are three approaches:a. Sort the array, then find the longest run.b. Allocate an array of counters of the same size as the original array. For each element, traverse the array and count how many other elements are
Implement the algorithm described in Section 14.7.4, but only remember the value with the highest frequency so far:int mostFrequent = 0;int highestFrequency = -1;for (int i = 0; i < a.length; i++)Count how often a[i] occurs in a[i + 1] ... a[a.length - 1]If it occurs more often than
Trace a walkthrough of selection sort with these sets:a. 4 7 11 4 9 5 11 7 3 5b. –7 6 8 7 5 9 0 11 10 5 8
Write a program that sorts an ArrayList in decreasing order so that the largest country is at the beginning of the array. Use a Comparator.
Trace a walkthrough of merge sort with these sets:a. 5 11 7 3 5 4 7 11 4 9b. 9 0 11 10 5 8 –7 6 8 7 5
Consider the binary search algorithm in Section 14.6. If no match is found, the search method returns −1. Modify the method so that if a is not found, the method returns −k − 1, where k is the position before which the element should be inserted. (This is the same behavior as
Trace a walkthrough of:a. Linear search for 7 in –7 1 3 3 4 7 11 13b. Binary search for 8 in –7 2 2 3 4 7 8 11 13c. Binary search for 8 in –7 1 2 3 5 7 10 13
Implement the sort method of the merge sort algorithm without recursion, where the length of the array is a power of 2. First merge adjacent regions of size 1, then adjacent regions of size 2, then adjacent regions of size 4, and so on.
Your task is to remove all duplicates from an array. For example, if the array has the values4 7 11 4 9 5 11 7 3 5then the array should be changed to4 7 11 9 5 3Here is a simple algorithm: Look at a[i]. Count how many times it occurs in a. If the count is larger than 1, remove it. What is the
Use insertion sort and the binary search from Exercise E14.13 to sort an array as described in Exercise R14.20. Implement this algorithm and measure its performance.Data from Exercise E14.13Consider the binary search algorithm in Section 14.6. If no match is found, the search method returns −1.
Modify the merge sort algorithm to remove duplicates in the merging step to obtain an algorithm that removes duplicates from an array. Note that the resulting array does not have the same ordering as the original one. What is the efficiency of this algorithm?
Supply a class Person that implements the Comparable interface. Compare persons by their names. Ask the user to input ten names and generate ten Person objects. Using the compareTo method, determine the first and last person among them and print them.
Consider the following algorithm to remove all duplicates from an array: Sort the array. For each element in the array, look at its next neighbor to decide whether it is present more than once. If so, remove it. Is this a faster algorithm than the one in Exercise R14.15?Data from Exercise
Sort an array list of strings by increasing length. Hint: Supply a Comparator.
Develop an O(n log(n)) algorithm for removing duplicates from an array if the resulting array must have the same ordering as the original array. When a value occurs multiple times, all but its first occurrence should be removed.
Sort an array list of strings by increasing length, and so that strings of the same length are sorted lexicographically. Hint: Supply a Comparator.
Why does insertion sort perform significantly better than selection sort if an array is already sorted?
Consider the following speedup of the insertion sort algorithm of Special Topic 14.2. For each element, use the enhanced binary search algorithm that yields the insertion position for missing elements. Does this speedup have a significant impact on the efficiency of the algorithm?
Consider the following algorithm known as bubble sort:While the array is not sorted For each adjacent pair of elements If the pair is not sorted Swap its elements. What is the big-Oh efficiency of this algorithm?
The radix sort algorithm sorts an array of n integers with d digits, using ten auxiliary arrays. First place each value v into the auxiliary array whose index corresponds to the last digit of v. Then move all values back into the original array, preserving their order. Repeat the process, now using
A stable sort does not change the order of elements with the same value. This is a desirable feature in many applications. Consider a sequence of e-mail messages. If you sort by date and then by sender, you’d like the second sort to preserve the relative order of the first, so that you can see
Give an O(n) algorithm to sort an array of n bytes (numbers between –128 and 127). Use an array of counters.
You are given a sequence of arrays of words, representing the pages of a book. Your task is to build an index (a sorted array of words), each element of which has an array of sorted numbers representing the pages on which the word appears. Describe an algorithm for building the index and give its
Given two arrays of n integers each, describe an O(n log(n)) algorithm for determining whether they have an element in common.
Given an array of n integers and a value v, describe an O(n log(n)) algorithm to find whether there are two values x and y in the array with sum v.
Given two arrays of n integers each, describe an O(n log(n)) algorithm for finding all elements that they have in common.
Suppose we modify the quicksort algorithm from Special Topic 14.3, selecting the middle element instead of the first one as pivot. Find a sequence of values for which this algorithm has an O(n2) running time.
An invoice contains a collection of purchased items. Should that collection be implemented as a list or set? Explain your answer.
Write a methodpublic static void downsize(LinkedList employeeNames, int n)that removes every nth employee from a linked list.
Read all words from a list of words and add them to a map whose keys are the phone keypad spellings of the word, and whose values are sets of words with the same code. For example, 26337 is mapped to the set { "Andes", "coder", "codes", . . .}. Then keep prompting the user for numbers and print out
Consider a program that manages an appointment calendar. Should it place the appointments into a list, stack, queue, or priority queue? Explain your answer.
Write a methodpublic static void reverse(LinkedList strings)that reverses the entries in a linked list.
Reimplement Exercise E15.4 so that the keys of the map are objects of class Student. A student should have a first name, a last name, and a unique integer ID. For grade changes and removals, lookup should be by ID. The printout should be sorted by last name. If two students have the same last name,
One way of implementing a calendar is as a map from date objects to event objects. However, that only works if there is a single event for a given date. How can you use another collection type to allow for multiple events on a given date?
Implement the sieve of Eratosthenes: a method for computing prime numbers, known to the ancient Greeks. This method computes all prime numbers up to n. Choose an n. First insert all numbers from 2 to n into a set. Then erase all multiples of 2 (except 2); that is, 4, 6, 8, 10, 12, . . . . Erase all
Write a class Polynomial that stores a polynomial such asas a linked list of terms. A term contains the coefficient and the power of x. For example, you would store p(x) asSupply methods to add, multiply, and print polynomials. Supply a constructor that makes a polynomial from a single term. For
Look up the descriptions of the methods addAll, removeAll, retainAll, and containsAll in the Collection interface. Describe how these methods can be used to implement common operations on sets (union, intersection, difference, subset).
Write a program that keeps a map in which both keys and values are strings—the names of students and their course grades. Prompt the user of the program to add or remove students, to modify grades, or to print all grades. The printout should be sorted by name and formatted like this:Carl: B+Joe:
Repeat Exercise P15.3, but use a Map for the coefficients.Data from Exercise P15.3,Write a class Polynomial that stores a polynomial such asas a linked list of terms. A term contains the coefficient and the power of x. For example, you would store p(x) asSupply methods to add, multiply, and print
Explain what the following code prints. Draw a picture of the linked list after each step.LinkedList staff = new
Write a program that reads a Java source file and produces an index of all identifiers in the file. For each identifier, print all lines in which it occurs. For simplicity, we will consider each string consisting only of letters, numbers, and underscores an identifier. Declare a Scanner in for
Try to find two words with the same hash code in a large file. Keep a Map>. When you read in a word, compute its hash code h and put the word in the set whose key is h. Then iterate through all keys and print the sets whose size is greater than one.
Explain what the following code prints. Draw a picture of the linked list after each step.LinkedList staff = new
Supply compatible hashCode and equals methods to the Student class described in Exercise P15.2. Test the hash code by adding Student objects to a hash set.Data from Exercise P15.2.Reimplement Exercise E15.4 so that the keys of the map are objects of class Student. A student should have a first
Explain what the following code prints. Draw a picture of the linked list after each step.LinkedList staff = new
Explain what the following code prints. Draw a picture of the linked list and the iterator position after each step.LinkedList staff = new LinkedList<>();ListIterator iterator = staff.listIterator();iterator.add("Tom");iterator.add("Diana");iterator.add("Harry");iterator =

Showing 400 - 500 of 835

Java Concepts Late Objects 3rd Edition Cay S. Horstmann - Solutions

Step by Step Answers