1) E fficiency - Multiple Choice [10 points]

For each of the operations listed below, determine the time complexity of the operation as it pertains to the data structure. Select the bubble corresponding to your choice in the space provided, and

completely fill in the bubble. Unless otherwise stated, assume the worst-case time complexity.

However, make sure you choose the tightest Big-O upper bound possible for the operation. Do not use an amortized analysis for these operations unless otherwise specified.

A) What is the best-case time complexity of searching for all occurrences of a pattern of length m in a string of length n using the KMP algorithm?.

⃝ O(n / m)           ⃝ O(m)       ⃝ O(n)        ⃝ O(m + n)        ⃝ O(mn)

B) What is the time complexity of creating the failure table for KMP for a pattern of length m to search a string of length n?

⃝ O(n / m)           ⃝ O(m)       ⃝ O(n)        ⃝ O(m + n)        ⃝ O(mn)

C) What is the best-case time complexity of running Heap Sort on a reverse-sorted array?

⃝ O(1)           ⃝ O(log n)       ⃝ O(n)        ⃝ O(nlog n)        ⃝ O(n2)

D) What is the best-case time complexity of running Merge Sort on an already sorted array?

⃝ O(1)           ⃝ O(log n)       ⃝ O(n)        ⃝ O(nlog n)        ⃝ O(n2)

E) What is the best-case time complexity of running Quicksort when the minimum value is always selected as the pivot index?

⃝ O(1)           ⃝ O(log n)       ⃝ O(n)        ⃝ O(nlog n)        ⃝ O(n2)

2) Sorting Properties [5 points]

Please select the answer choice(s) that best answer the question below. Assume that all sorting algorithms are as taught in this course and as implemented on your homework. Select all that apply.

A) Both Quicksort and Bubble Sort share which of the following properties?

⃝ Stable           ⃝ In Place       ⃝ Out of Place        ⃝ Adaptive        ⃝ None of these

B) Both Merge Sort and Quicksort share which of the following properties?

⃝ Stable           ⃝ In Place       ⃝ Out of Place        ⃝ Adaptive        ⃝ None of these

3) Sorting Scenarios [5 points]

Given the following scenario, select the sorting algorithm that would perform best. In all of these situations, assume that we are sorting integers in ascending order.

A) We want to sort consistently in as little time as possible. Memory is not an issue, but the largest    element has 11 more digits than all the other elements, and the relative position of duplicates should be maintained.

⃝ Heap Sort           ⃝ Insertion Sort      ⃝ LSD Radix Sort       ⃝ Merge Sort

⃝ Quicksort       ⃝ Bubble Sort       ⃝ Selection Sort

B) We want to sort the data in as little time as possible, but the data is completely randomized and we have limited space in memory we can use.

⃝ Heap Sort           ⃝ Insertion Sort      ⃝ LSD Radix Sort       ⃝ Merge Sort

⃝ Quicksort       ⃝ Bubble Sort       ⃝ Selection Sort

4) Bubble Sort - Diagramming [10 points]

Given the following array, perform three iterations of the bubble sort algorithm as presented in class and in the modules. Use the last swapped optimization when necessary. After each iteration, rewrite the array on the following row.

5) Boyer-Moore Diagramming [10 points]

Given the pattern "happy" and the text "hippyhaphaphappy" perform the Boyer Moore pattern

matching algorithm to find ALL match(es) of the pattern in the text. For each alignment of the pattern,

rewrite the pattern on the following row and circle the characters in the pattern as they are compared.

6) KMP Failure Table [10 points]

The following Failure Table was generated according to the algorithm taught in class:

Give an example string that will generate this table by only choosing from the characters, "a", "b", "c", and "d".  You may or may not need to use all four characters.

This question does not have a singular correct answer.

The following Failure Table was generated according to the algorithm taught in class:

Give an example string that will generate this table by only choosing from the characters, "a", "b", "c", and "d".  You may or may not need to use all four characters.

This question does not have a singular correct answer.

7) Rabin-Karp Rolling Hash [10 points]

The hash below was generated from the below string as a part of a string search on a string of length 6 using the Rabin-Karp string searching algorithm. Given this string and hash, a base value of 2, and    the next string to search, calculate the next Rolling Hash that will be used for comparison during the   next iteration.

Your hash calculation should follow the same method that was taught in lecture. You may use a calculator for this question.

For reference, here is a table that includes the characters and ASCII values for every letter:

Current string: "Linked"

•Current hash: 5722

•Next string: "inkedQ"

•Character to add to current string: 'Q'

•Base value: 2

Give the computed hash (and optionally, the hash calculation) in the text box below. (Full credit will be awarded for a correct hash value. Partial credit can still be awarded for an incorrect hash value if a correct hash calculation is given)

7) Quicksort - Code Ordering [10 points]

Below you are given a bank of unordered code lines from A to O where some of the code lines make    up the Quicksort method. You are to arrange the code lines from this code bank in the correct order to complete the Quicksort algorithm as taught in the course modules.

Write the letter(s) corresponding to each code line in the order they are to be called within the

method. Denote the order with a left to right list. Separate individual letters in the list using spaces.

List the letters (capitalized) associated with each step, starting with the first step to the last step.

NOTE: You will not need to use every step.  No step is used more than once.

Steps:

A: Swap the pivot with the first indexof the subarray

B: Increment a pointer until it points to an element greater than the pivot

C: If the pointers have not crossed, stop and move on to the next step

D: If the pointers have not crossed, swap the elements they point to, move the pointers by one position each, and repeat some of the previous step(s)

E: Swap the pivot with the last indexof the subarray

F: If the pointers have crossed, stop and move on to the next step

G: Decrement a pointer until it points to an element greater than the pivot

H: Select a random index to be the pivot

I: Decrement a pointer until it points to an element less than the pivot

J: Swap the pivot with the right pointer (based on initialization, not current position) K: Swap the pivot with the left pointer (based on initialization, not current position)

L: Increment a pointer until it points to an element less than the pivot

M: Create two integer pointers, one to the beginning of the current subarray and one to the end (not counting where the pivot is located)

N: Make two recursive calls, on the subarrays to the left and right of the pivot

8) LSD Radix Sort - Coding [15 points]

Goal: Write code that implements lsdRadixSort(...) by completing the body of the method, which modifies the input array so that the integer values contained are in sorted order.

Requirements: Your code must be as efficient as possible. The largest number of digits among the integers contained in the input array, int k, is provided to you, as well as an array of LinkedLists,

buckets. You must use the LinkedList<Integer>[] buckets array that is provided in the first line of

lsdRadixSort(...). Do not return a value; modify the input array directly to create an integer array in

ascending order. You may assume that the input will always be valid and that there are no null spots in the array.

import java.util.LinkedList;

public class Sorting {

/**

* Empties the buckets and places them back into the input array in order

* according to the LSD Radix Sort implementation discussed in class.

*

* @param arr the array to be sorted

* @param buckets array of LinkedList<Integer> that hold values

*/

private void emptyBuckets(int[] arr, LinkedList<Integer>[] buckets) {

// implementation omitted

}

/**

* Implement LSD (Least Significant Digit) Radix sort.

*

* Modifies the int array arr such that the elements end up in sorted order

from

* smallest to largest. The passed in array will only have non-negative values

*

* @param arr the array to be sorted

* @param k the largest number of digits among the integers contained in data

*/

public static void lsdRadixSort(int[] arr, int k) {

LinkedList<Integer>[] buckets = (LinkedList<Integer>[]) new LinkedList[19];

for (int i = 0; i < 19; i++) {

buckets[i] = new LinkedList<>();

}

// WRITE YOUR CODE ON THE NEXT PAGE

} // END OF METHOD

} // END OF CLASS

9) AVL - Coding [15 points]

Goal: Given a basic class for an AVL, write the sumDeepestBranch() method. This method will sum the data in the tree along the deepest branch. If the left and right branches are equally deep, you

should go right.

Requirements: Your code MUST be written recursively. Feel free to write any helper methods you   consider to be necessary, but you may NOT call any AVL methods you have not implemented. You   may NOT create additional instance variables for the AVL class. Since Node is a private inner class, you should access its fields directly (e.g. node.data) instead of using getters/setters. Your code  should be as efficient as possible.

Examples:

Given the AVL above:

●   sumDeepestBranch() on the AVL on the left will return 15 + 20 + 25 + 23 = 83.

●   sumDeepestBranch() on the AVL on the right will return 33 + 40 + 35 + 37 = 145 (since the left and right branches from the root are equally heavy, we go right).

public class AVL {

private class Node {

int data;

int height;

int bf; // balance factor

Node left;

Node right;

}

private Node root;

/**

* Sums the data along the deepest branch in the tree.

* @return sum.

*/

public int sumDeepestBranch() {

// YOUR CODE HERE

} // END OF METHOD

} // END OF CLASS