Questions and Answers of Building Java Programs A Back to Basics Approach

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
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
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
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
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,
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
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
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
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
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.
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
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
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
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”,
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
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
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
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
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
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
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
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
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
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
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,
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
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,
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];
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
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[]
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
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.
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.
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
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
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
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
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.
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
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
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,
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
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
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
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
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
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
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
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
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
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
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.
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
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
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
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
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
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
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
What elements are contained in the following set after this code executes?Set set = new
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
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
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,
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,
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
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
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
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,
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
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,
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,

Showing 300 - 400 of 1041