QuestionQuestion

Transcribed TextTranscribed Text

1. [2 points] What makes a program easy to modify? 2. [3 points] Describe the order of magnitude of the following code section using Big(O) notation. j = 1; While (j < N) { j = j * 2); } 3. [3 points] What are the benefits we accrue by using a Java interface construct to formally specify the logical level of ADTs? 4. [5 points] Suppose we have a linked list of Strings, as defined in the textbook, named presidents. Suppose it contains three nodes, with the first node holding “Adams”, the second node “Washington”, and the third node “Kennedy”. What would be output by the following code: LLStringNode temp = presidents; while (temp != null) { temp = temp.getLink(); } System.out.println(temp.getInfo()); 5. [3 points] Suppose a collection object is defined to hold elements of class Object, and you use it to store String objects. Describe what you must do when you retrieve an object from the collection and intend to use it as a String. 6. [8 points] Show what is written by the following segment of code, given that item1, item2, and item3 are int variables, and stack is an object that fits our abstract description of a stack. Assume that you can store and retrieve variables of type int on stack. item1 = 1; item2 = 0; item3 = 4; stack.push(item2); stack.push(item1); stack.push(item1 + item3); item2 = stack.top(); stack.push (item3*item3); stack.push(item2); stack.push(3); item1 = stack.top(); stack.pop(); System.out.println(item1 + " " + item2 + " " + item3); while (!stack.isEmpty()) { item1 = stack.top(); stack.pop(); System.out.println(item1); } 7. [2 points] Explain the relationship between dynamic storage allocation and recursion. 8. [8 points] Analyze the factorial method and answer the following questions: int factorial (int n) { if (n > 0) return (n * factorial (n – 1)); else if (n == 0) return 1; } a. What is the base case? b. What is the general case? c. What are the constraints on the argument values? d. What does the method do? 9. [2 points] What are the three interfaces we defined related to our Queue ADT? 10. [2 points] Describe in general terms the approach we use to implement an unbounded queue based on an array. 11. [2 points] What does it mean for a class’s equals and compareTo methods to be “consistent”? 12. [10 points] Questions a-e below refer to the following figure: a. What are the ancestors of node J? b. What are the descendants of node T? c. What are the descendants of node B? d. What is the order in which the nodes are visited by a preorder traversal? e. What is the order in which the nodes are visited by a postorder traversal? tree A Q K D M B J P N T Y W R 13. [5 points] If a heap is used to implement a priority queue, what is the Big O efficiency of the enqueue operation, assuming the size of the priority queue is N? 14. [10 points] What would be the order of the following list after two iterations of the “inner” part of the Insertion Sort algorithm? 13 4 16 19 2 15 12 3 23 20 15. [10 points] Suppose we are using Merge Sort to sort the following list of numbers. What would be the order of the list immediately before the execution of the merge method in the original (nonrecursive) call to mergesort? 13 4 16 19 2 15 12 3 23 20 16. [25 points] Programming Sorting Algorithms: For this section, use the Sorts.java test harness (provided by instructor). a. Describe an approach to modifying the Sorts.java program so that after calling a sorting method the program prints out the number of swaps needed by the sorting method. b. Implement your approach. c. Test your new program by running the selectionSort method. Your program should report 49 swaps. d. Now, modify your program to also output the number of comparisons (compares) needed. You must include one or more statements to increment your counter within the sorting methods themselves. For each of the listed methods, make and test the changes needed, and list both the number of swaps and the number of compares needed by the Sorts program to sort an array of 50 random integers. selectionSort swaps:____ compares:____ bubbleSort swaps:____ compares:____ shortBubble swaps:____ compares:____ insertionSort swaps:____ compares:____

Solution PreviewSolution Preview

These solutions may offer step-by-step problem-solving explanations or good writing examples that include modern styles of formatting and construction of bibliographies out of text citations and references. Students may use these solutions for personal skill-building and practice. Unethical use is strictly forbidden.

import java.util.*;
import java.text.DecimalFormat;

public class Sorts
{
static final int SIZE = 50;            // size of array to be sorted
static int[] values = new int[SIZE];   // values to be sorted
static int swaps = 0;
static int compares = 0;

static void initValues()
// Initializes the values array with random integers from 0 to 99.
{
    Random rand = new Random();
    for (int index = 0; index < SIZE; index++)
      values[index] = Math.abs(rand.nextInt()) % 100;
}

static public boolean isSorted()
// Returns true if the array values are sorted and false otherwise.
{
    boolean sorted = true;
    for (int index = 0; index < (SIZE - 1); index++)
      if (values[index] > values[index + 1])
       sorted = false;
    return sorted;
}

static public void swap(int index1, int index2)
// Precondition: index1 and index2 are >= 0 and < SIZE.
//
// Swaps the integers at locations index1 and index2 of the values array.
{
    int temp = values[index1];
    values[index1] = values[index2];
    values[index2] = temp;
    swaps += 1;
}

static public void printValues()
// Prints all the values integers.
{
    int value;
    DecimalFormat fmt = new DecimalFormat("00");
    System.out.println("The values array is:");
    for (int index = 0; index < SIZE; index++)
    {
      value = values[index];
      if (((index + 1) % 10) == 0)
       System.out.println(fmt.format(value));
      else
       System.out.print(fmt.format(value) + " ");
    }
    System.out.println();
}


/////////////////////////////////////////////////////////////////
//
// Selection Sort

static int minIndex(int startIndex, int endIndex)
// Returns the index of the smallest value in
// values[startIndex]..values[endIndex].
{
    int indexOfMin = startIndex;
    for (int index = startIndex + 1; index <= endIndex; index++)
      if (values[index] < values[indexOfMin])
       indexOfMin = index;
    return indexOfMin;
}

static void selectionSort()
// Sorts the values array using the selection sort algorithm.
{
    swaps = 0;
    compares = 0;
    int endIndex = SIZE - 1;
    for (int current = 0; current < endIndex; current++)
    {
      compares++;
      swap(current, minIndex(current, endIndex));
      // printValues();
    }
    System.out.println("Selection Sort");
    System.out.println("Number of swaps: " + swaps);
    System.out.println("Number of compares: " + compares);
}


/////////////////////////////////////////////////////////////////
//
// Bubble Sort

static void bubbleUp(int startIndex, int endIndex)
// Switches adjacent pairs that are out of order
// between values[startIndex]..values[endIndex]
// beginning at values[endIndex].
{
    for (int index = endIndex; index > startIndex; index--) {
      compares++;
      if (values[index] < values[index - 1])
       swap(index, index - 1);
    }
}

static void bubbleSort()
// Sorts the values array using the bubble sort algorithm.
{
    int current = 0;
    swaps = 0;
    compares = 0;
    while (current < (SIZE - 1))
    {
      bubbleUp(current...

By purchasing this solution you'll be able to access the following files:
Solution.java and Solution.docx.

$60.00
for this solution

PayPal, G Pay, ApplePay, Amazon Pay, and all major credit cards accepted.

Find A Tutor

View available Data Structures and Algorithms Tutors

Get College Homework Help.

Are you sure you don't want to upload any files?

Fast tutor response requires as much info as possible.

Decision:
Upload a file
Continue without uploading

SUBMIT YOUR HOMEWORK
We couldn't find that subject.
Please select the best match from the list below.

We'll send you an email right away. If it's not in your inbox, check your spam folder.

  • 1
  • 2
  • 3
Live Chats