Building Java Programs A Back To Basics Approach 5th Edition Stuart Reges, Marty Stepp - Solutions

Which one of the following statements about sorting and big-Oh is true?a. Selection sort can sort an array of integers in O(N) time.b. Merge sort achieves an O(N log N) runtime by dividing the array in half at each step and then recursively sorting and merging the halves back together.c. Merge
Consider the following array of int elements:int[] numbers = {7, 1, 6, 12, –3, 8, 4, 21, 2, 30, –1, 9};a. Show the state of the elements after five passes of the outermost loop of selection sort have occurred.b. Show a trace that is two levels deep of the merge sort algorithm. Show the
Consider the following array of int elements:int[] numbers = {7, 2, 8, 4, 1, 11, 9, 5, 3, 10};a. Show the state of the elements after five passes of the outermost loop of selection sort have occurred.b. Show a trace that is two levels deep of the merge sort algorithm. Show the splitting of the
How many calls on the mergeSort method are generated by a call to sort a list of length 32?
Trace the execution of the selection sort algorithm as shown in this section when run on the following input arrays. Show each element that will be selected by the algorithm and where it will be moved, until the array is fully sorted.a. {29, 17, 3, 94, 46, 8, –4, 12}b. {33, 14, 3, 95, 47, 9,
Consider the following array:int[] numbers = {29, 17, 3, 94, 46, 8, –4, 12};After a single pass of the selection sort algorithm (a single swap), what would be the state of the array?a. {–4, 29, 17, 3, 94, 46, 8, 12}b. {29, 17, 3, 94, 46, 8, 12}c. {–4, 29, 17, 3, 94, 46, 8, –4, 12}d. {–4,
What modifications would you have to make to the selectionSort method to cause it to sort an array of double values rather than one of integer values?
Consider the following sorted array of integers. When a binary search is performed on this array for each of the following integer values, what indexes are examined in order? What result value is returned?a. –5b. 0c. 11d. –100 // index 1 2 3 4 5 6 7 8 10 11 12 13 int [] numbers = {-30, -9, -6,
Implement a “bogus” sorting algorithm called bogo sort that uses your shuffling algorithm from the previous exercise to sort an array of numbers. The bogo sort algorithm is the following:Obviously, this is not a very efficient sorting algorithm, but it eventually does shuffle the array into
Consider the following sorted array of integers. When a binary search is performed on this array for each of the following integer values, what indexes are examined in order? What result value is returned?a. 42b. 11c. 74d. 30 7 9 10 11 12 3 // index 13 14 5, 31 8, 15, 18, 22, 39, 40, 42, 50, 57,
Implement an algorithm to shuffle an array of numbers or objects. The algorithm for shuffling should be the following:(The constraint about j being greater than or equal to i is actually quite important, if you want your shuffling algorithm to shuffle fairly. Why?) for (each index i) { choose a
What indexes will be examined as the middle element by a binary search for the target value 8 when the search is run on the following input array? Notice that the input array isn’t in sorted order. What can you say about the binary search algorithm’s result?int[] numbers = {6, 5, 8, 19, 7, 35,
Write a modified “dual” version of the selection sort algorithm that selects both the largest and smallest elements on each pass and moves each of them to the appropriate end of the array. Will this algorithm be faster than the standard selection sort? What predictions would you make about its
What indexes will be examined as the middle element by a binary search for the target value 8 when the search is run on the following input arrays? What value will the binary search algorithm return?a. int[] numbers = {1, 3, 6, 7, 8, 10, 15, 20, 30};b. int[] numbers = {1, 2, 3, 4, 5, 7, 8, 9,
Write a modified version of the selection sort algorithm that selects the largest element each time and moves it to the end of the array, rather than selecting the smallest element and moving it to the beginning. Will this algorithm be faster than the standard selection sort? What will its
How many elements (at most) does a binary search examine if the array contains 60 elements?
Why does the binary search algorithm require the input to be sorted?
Write a Comparator that compares String objects by the number of words they contain. Consider any nonwhitespace string of characters to be a word. For example, “hello” comes before “I see”, which comes before “You can do it”.
What is the runtime complexity class of a sequential search on an unsorted array? What is the runtime complexity class of the modified sequential search on a sorted array?
Write a Comparator that compares Point objects by their distance from the origin of (0, 0). Points that are closer to the origin are considered to come before those which are further from the origin.
Suppose an algorithm takes exactly the given number of statements for each value below, in terms of an input size N. Give a tight big-Oh bound for each algorithm, representing the closest complexity class for that algorithm based on that runtime.a. ½N log N + log Nb. N2 − (N + N log N + 1000)c.
Write code to read a dictionary from a file, then prompt the user for two words and tell the user how many words in the dictionary fall between those two words. Here is a sample run of the program:Type two words: goodbye helloThere are 4418 words between goodbye and helloUse the binary search
Determine the complexity classes of the algorithms that could be used to perform the following tasks:a. Finding the average of the numbers in an array of integersb. Finding the closest distance between any pair of points in an array of Pointsc. Finding the maximum value in an array of real
Using the same arrays from the previous problem, trace the complete execution of the merge sort algorithm when called on each array. Show the subarrays that are created by the algorithm and show the merging of subarrays into larger sorted arrays.Data from Previous ExerciseWrite the state of the
Approximate the runtime of the following code fragment, in terms of n: int sum = = 0; for (int i = 1; i
Write the state of the elements of each of the following arrays after each pass of the outermost loop of the selection sort algorithm has occurred (after each element is selected and moved into place).int[] numbers5 = {22, 44, 11, 88, 66, 33, 55, 77};int[] numbers6 = {–3, -6, -1, -5, 0, -2, -4,
Approximate the runtime of the following code fragment, in terms of n: int sum = 0; for (int i 1; i
Using the same arrays from the previous problem, trace the complete execution of the merge sort algorithm when called on each array. Show the subarrays that are created by the algorithm and show the merging of subarrays into larger sorted arrays.Data from Previous ExerciseWrite the state of the
Approximate the runtime of the following code fragment, in terms of n: int sum = 0; %3D for (int i = 1; i
Write the state of the elements of each of the following arrays after each pass of the outermost loop of the selection sort algorithm has occurred (after each element is selected and moved into place).int[] numbers3 = {8, 5, –9, 14, 0, –1, –7, 3};int[] numbers4 = {15, 56, 24, 5, 39, –4, 27,
Approximate the runtime of the following code fragment, in terms of n: int sum 0; %3D for (int j 1; j < n; j++) { %3D sum++; if (j % 2 0) { sum++;
Using the same arrays from the previous problem, trace the complete execution of the merge sort algorithm when called on each array. Show the subarrays that are created by the algorithm and show the merging of subarrays into larger sorted arrays.Data from Previous ExerciseWrite the state of the
Approximate the runtime of the following code fragment, in terms of n: int sum = 0; int j = 1; while (j
Write the state of the elements of each of the following arrays after each pass of the outermost loop of the selection sort algorithm has occurred (after each element is selected and moved into place). int [] numbersl = {63, 9, 45, 72, 27, 18, 54, 36}; int[] numbers2 {37, 29, 19, 48, 23, 55, 74,
In this section, we wrote a LengthComparator that would allow a list or array of strings to be sorted in ascending order by length. How could we easily sort the collection in descending order by length, from longest to shortest, without modifying the code of LengthComparator?
To which complexity class does the following algorithm belong? public static void mystery4 (List list) { for (int i = 0; i < list.size () 1; i += 2) { %3D String first list.get (i); !! list.set (i, list.get (i + 1)); list.set (i + 1, first);
The following Comparator class is attempting to arrange BankAccount objects by account name, breaking ties by account balance. But the code has some syntax errors and some logic errors. What is wrong with the code? How would you correct it? 1 import java.util.*; 2 public class AccountComparator
To which complexity class does the following algorithm belong? public static void mystery3 (List list) { for (int i = 0; i < list.size () 1; i += 2) { String first = list.remove (i); list.add (i + 1, first);
Why wouldn’t the Collections.sort method work when used on a list of Point objects? How can you make it so that the sort method can be used on Points or any other type of objects?
To which complexity class does the following algorithm belong? public static void mystery2 (int [] list) { for (int i = 0; i < list.length / 2; i++) { int j = list.length 1 i; int temp = list[i]; list[i] = list[j]; list[j] temp;
In what order does the Collections.sort method arrange a list of strings? How could you arrange them into a different order?
Write a program that discovers all anagrams of all words listed in an input file that stores the entries in a large dictionary. An anagram of a word is a rearrangement of its letters into a new legal word. For example, the anagrams of “share” include “shear”, “hears”, and “hares”.
To which complexity class does the following algorithm belong? Consider N to be the length or size of the array or collection passed to the method. Explain your reasoning. public static int[] mystery1 (int [] list) { int [] result = new int [2 * list.length]; for (int i = 0; i < list.length; i++) {
Under what circumstances can the Arrays.binarySearch and Collections.binarySearch methods be used successfully?
Write a program that processes a data file of students’ course grade data. The data arrive in random order; each line stores information about a student’s last name, first name, student ID number, grade as a percentage, and letter grade. For example, here are a few lines of data:Your program
Suppose the following array has been declared:What indexes will be examined as the middle element by a binary search for each of the following target values? What value will be returned?a. 65b. 9c. 90d. 147 // index 0 1 2. 3 4 5 6 8 9 10 11 12 13 14 int [] numbers = {0, 5, 10, 15, 40, 55, 60, 65,
Should you use a sequential or binary search on an array of Point objects, and why?
Suppose the following array has been declared:What indexes will be examined as the middle element by a binary search for each of the following target values? What value will be returned?a. 13b. 39c. 50d. 2 // index 0 1 2 4 5 6. 7 9. 10 11 int [] numbers {-1, 3, 8, 15, 18, 22, 39, 40, 42, 50, 57};
Write a program that reads a series of input lines and sorts them into alphabetical order, ignoring the case of words. The program should use the merge sort algorithm so that it efficiently sorts even a large file.
Describe two ways to search an unsorted array of String objects using the Java class libraries.
Write a method called writeNums that takes an integer n as a parameter and prints to the console the first integers starting with 1 in sequential order, separated by commas. For example, consider the following calls:writeNums(5);System.out.println(); // to complete the line of
What are base cases and recursive cases? Why does a recursive method need to have both?
Modify the WordCount program so that it prints the most frequently occurring words sorted by number of occurrences. To do this, write code at the end of the program to create a reverse map from counts to words that is based on the original map. Assume that no two words of interest occur the exact
Write a program that solves the classic “stable marriage” problem. This problem deals with a group of men and a group of women. The program tries to pair them up so as to generate as many stable marriages as possible. A set of marriages is unstable if you can find a man and a woman who would
Write a recursive method called dedup that takes a string as a parameter and that returns a new string obtained by replacing every sequence of repeated adjacent letters with just one of that letter. For example, the string "bookkkkkeeper" has three repeated adjacent letters ("oo", "kkkkk", and
Write a method called stdev that returns the standard deviation of an array of integers. Standard deviation is computed by taking the square root of the sum of the squares of the differences between each element and the mean, divided by one less than the number of elements. (It’s just that
Write a method grayscale that converts a color image into a blackand-white image. This is done by averaging the red, green, and blue components of each pixel. For example, if a pixel has RGB values of (red = 100, green = 30blue = 80), the average of the three components is (100 + 30 + 80) /3 = 70,
For the next four problems, consider the task of representing types of tickets to campus events. Each ticket has a unique number and a price. There are three types of tickets: walk-up tickets, advance tickets, and student advance tickets. Figure 9.10 illustrates the types:Walk-up tickets are
Modify the Sieve program developed in Section 11.1 to make two optimizations. First, instead of storing all integers up to the maximum in the numbers list, store only 2 and all odd numbers from 3 upward. Second, write code to ensure that if the first number in the numbers list ever reaches the
Write a program that computes the edit distance (also called the Levenshtein distance, for its creator Vladimir Levenshtein) between two words. The edit distance between two strings is the minimum number of operations that are needed to transform one string into the other. For this program, an
When should you use a LinkedList instead of an ArrayList ?
Write a method called alternate that accepts two Lists as its parameters and returns a new List containing alternating elements from the two lists, in the following order:First element from first listFirst element from second listSecond element from first listSecond element from second listThird
Would a LinkedList or an ArrayList perform better when run on the following code? Why? public static int min (List list) { int min list.get (0); for (int i = 1; i < list.size (); i++) { if (list.get (i) < min) { min = list.get (i); return min;
Write a method called removeInRange that accepts four parameters: a LinkedList , an element value, a starting index, and an ending index.The method’s behavior is to remove all occurrences of the given element that appear in the list between the starting index (inclusive) and the ending index
Write a program that solves the classic “random writer” problem. This problem deals with reading input files of text and examining the frequencies of characters. On the basis of those frequencies, you can generate randomized output that appears to match the writing style of the original
What is an iterator? Why are iterators often used with linked lists?
Write a method called partition that accepts a list of integers and an integer value E as its parameter, and rearranges (partitions) the list so that all the elements with values less than E occur before all elements with values greater than E. The exact order of the elements is unimportant, so
Write a piece of code that counts the number of duplicate elements in a linked list, that is, the number of elements whose values are repeated at an earlier index in the list. Assume that all duplicates in the list occur consecutively. For example, the list [ 1, 1, 3, 5, 5, 5, 5, 7, 7, 11] contains
Write a method called sortAndRemoveDuplicates that accepts a list of integers as its parameter and rearranges the list’s elements into sorted ascending order, as well as removing all duplicate values from the list. For example, the list [7, 4, –9, 4, 15, 8, 27, 7, 11, –5, 32, –9, –9]
Write a piece of code that inserts a String into an ordered linked list of Strings, maintaining sorted order. For example, for the list ["Alpha", "Baker", "Foxtrot", "Tango", "Whiskey"], inserting "Charlie" in order would produce the list [" Alpha", "Baker", "Charlie", "Foxtrot", "Tango",
Write a method countUnique that accepts a list of integers as a parameter and returns the number of unique integer values in the list. Use a set as auxiliary storage to help you solve this problem. For example, if a list contains the values [3, 7, 3, –1, 2, 3, 7, 2, 15, 15], your method should
Write a method called removeAll that accepts a linked list of integers as a parameter and removes all occurrences of a particular value. You must preserve the original relative order of the remaining elements of the list. For example, the call removeAll(list, 3) would change the list [3, 9, 4, 2,
Write a method countCommon that accepts two lists of integers as parameters and returns the number of unique integers that occur in both lists. Use one or more sets as storage to help you solve this problem. For example, if one list contains the values [ 3, 7, 3, –1, 2, 3, 7, 2, 15, 15] and the
Write a method called wrapHalf that accepts a linked list of integers as a parameter and moves the first half of the list to the back of the list. If the list contains an odd number of elements, the smaller half is wrapped (in other words, for a list of size N, the middle element, N/2, becomes the
Write a method maxLength that accepts a set of strings as a parameter and that returns the length of the longest string in the list. If your method is passed an empty set, it should return 0.
What is an abstract data type (ADT)? What ADT does a linked list implement?
Write a method hasOdd that accepts a set of integers as a parameter and returns true if the set contains at least one odd integer and false otherwise. If passed the empty set, your method should return false.
Self-Check Problem 4 asked you to write code that would count the duplicates in a linked list. Rewrite your code as a method called countDuplicates that will allow either an ArrayList or a LinkedList to be passed as the parameter.Data from Problem 4Write a piece of code that counts the number of
Write a method removeEvenLength that accepts a set of strings as a parameter and that removes all of the strings of even length from the set.
A List has every method that a Set has, and more. So why would you use a Set rather than a List?
Write a method called symmetricSetDifference that accepts two Sets as parameters and returns a new Set containing their symmetric set difference (that is, the set of elements contained in either of the two sets but not in both). For example, the symmetric difference between the sets [1, 4, 7, 9]
When should you use a TreeSet, and when should you use a HashSet?
Write a method contains3 that accepts a list of strings as a parameter and returns true if any single string occurs at least 3 times in the list, and false otherwise. Use a map as auxiliary storage.
A Set doesn’t have the get and set methods that an ArrayList has. How do you examine every element of a Set?
Write a method isUnique that accepts a map whose keys and values are strings as a parameter and returns true if no two keys map to the same value (and false if any two or more keys do map to the same value). For example, if the map contains the following key/value pairs, your method would return
What elements are contained in the following set after this code executes?Set set = new HashSet<>();set.add(74);set.add(12);set.add(74);set.add(74);set.add(43);set.remove(74);set.remove(999);set.remove(43);set.add(32);set.add(12);set.add(9);set.add(999);
Write a method intersect that accepts two maps whose keys are strings and whose values are integers as parameters and returns a new map containing only the key/value pairs that exist in both of the parameter maps. In order for a key/value pair to be included in your result, not only do both maps
How do you perform a union operation on two sets? An intersection? Try to give an answer that doesn’t require any loops.
Write a method maxOccurrences that accepts a list of integers as a parameter and returns the number of times the most frequently occurring integer (the “mode”) occurs in the list. Solve this problem using a map as auxiliary storage. If the list is empty, return 0.
Write the output produced when the following method is passed each of the following lists:a. [marty, stuart, helene, jessica, amanda]b. [sara, caitlin, janette, zack, riley]c. [zorah, alex, tyler, roy, roy, charlie, phil, charlie, tyler] public static void mystery (List list) { Set result = new
Write a method called is1to1 that accepts a map whose keys and values are strings as its parameter and returns true if no two keys map to the same value. For example, {Marty=206–9024, Hawking=123–4567, Smith=949–0504, Newton=123–4567} should return false, but {Marty=206–9024,
Write the code to declare a Map that associates people’s names with their ages. Add mappings for your own name and age, as well as those of a few friends or relatives.
Write a method called subMap that accepts two maps from strings to strings as its parameters and returns true if every key in the first map is also contained in the second map and maps to the same value in the second map. For example, {Smith=949–0504, Marty=206–9024} is a submap of
A Map doesn’t have the get and set methods that an ArrayList has. It doesn’t even have an iterator method like a Set does, nor can you use a for-each loop on it directly. How do you examine every key (or every value) of a Map?
Write a method called reverse that accepts a map from strings to strings as a parameter and returns a new map that is the reverse of the original. The reverse of a map is a new map that uses the values from the original as its keys and the keys from the original as its values. Since a map’s
What keys and values are contained in the following map after this code executes?Map map = new HashMap<>();map.put(8, "Eight");map.put(41, "Forty-one");map.put(8, "Ocho");map.put(18, "Eighteen");map.put(50, "Fifty");map.put(132, "OneThreeTwo");map.put(28, "Twenty-eight");map.put(79,
Write a method called rarest that accepts a map whose keys are strings and whose values are integers as a parameter and returns the integer value that occurs the fewest times in the map. If there is a tie, return the smaller integer value. If the map is empty, throw an exception.
Write the output produced when the following method is passed each of the following maps:a. {two=deux, five=cinq, one=un, three=trois, four=quatre}b. {skate=board, drive=car, program=computer, play=computer}c. {siskel=ebert, girl=boy, H=T, ready=begin, first=last, begin=end}d. {cotton=shirt,
Write a modified version of the Vocabulary program developed in Chapter 10 that uses sets rather than ArrayLists to store its words. (The program will be noticeably shorter and will run faster!).
Write the output produced when the following method is passed each of the following maps:a. {sheep=wool, house=brick, cast=plaster, wool=wool}b. {ball=blue, winkie=yellow, corn=yellow, grass=green, emerald=green}c. {pumpkin=peach, corn=apple, apple=apple, pie=fruit, peach=peach}d. {lab=ipl,

Showing 300 - 400 of 1041

Building Java Programs A Back To Basics Approach 5th Edition Stuart Reges, Marty Stepp - Solutions

Step by Step Answers