Algorithms Project - If any question seems ambiguous, you may add an explanation for your answer.

1. Analysis of algorithms.

(a) Tilde notation is more precise than Big-­-Oh notation at describing the growth of a function because:

I. Tilde notation includes the coefficient of the highest order term.

II. Tilde notation provides only a lower bound on the growth of a function.

III. Big-­-Oh notation suppresses lower order terms, so it does not necessarily accurately describe the behavior of a function for small values of N.

Select the best answer.

(a) I only.

(b) I and II only.

(c) I and III only.

(d) I, II and III.

(e) None.

(b) Consider the following code fragment.

int count = 0;

for (int i = 0; i < N; i++)

for (int j = i+1; j < N; j++) for (int k = j+1; k < N; k++)

if (a[i] + a[j] >= a[k]) count++;

1. Suppose that it takes 2 seconds to execute this code fragment when N = 1000. Using tilde notation, express a hypothesis for the number of array accesses of the code fragment as a function of N.

2. Suppose that it takes 2 seconds to execute this code fragment when N = 1000. Using tilde notation, express a hypothesis for the running time (in seconds) of the code fragment as a function of N.

2. Sorting algorithms.

The column on the leU is the original input of strings to be sorted; the column on the right are the string in sorted order; the other columns are the contents at some intermediate step during one of the 8 sorting algorithms listed below. Match up each algorithm by writing its column number aUer the corresponding leXer and sort name. Use each column exactly once.

(a) Selection sort

(b) Insertion sort

(c) Shell sort (13-­-4-­-1 increments)

(d) Merge sort (top-­-down)

(e) Merge sort (boXom-­-up)

(f) Quick sort (standard, no shuffle)

(g) Quick sort (3-­-way, no shuffle)

(h) Heap sort

Extra credit (just a bit): why don't f and g make use of a shuffle?

 3. Binary heaps.

Consider the following max-­-heap.

(a) The max-­-heap above result edaUera sequence of insert and remove-­-the-­-maximum operations. Assume that the last operation was an insert. Which key(s) could have been the one inserted last? Circle all possible keys.

A             E              H             I               J              K             M            O             R             S              T

(b) Draw the heap that results aUer deleting the maximum key from the heap above.

4. More sorting.

(a) Modern computers have memory caches, which speed up reads and writes if they are to locations near recently-­-accessed memory. This makes sequential access to memory faster, in general, than random access. Circle the sorting algorithm below that you would expect to benefit most from caching? (Then explain why you chose that sort.)

inserHonsort      mergesort           quicksort             heapsort

(b) You are managing the accounts for BigIBankCo, and have an array of customers together with their balances. You would like to rearrange the array such that the richest customers (those with balances greater than $1 million) are grouped at the beginning, with everyone else at the end.

Describe an algorithm for performing this task (preferably in linear time, and using only constant extra memory). If you can, adapt an algorithm from the textbook and describe only the changes you would make.

5. Priority queues.

Consider the following code fragment.

MaxPQ pq = new MaxPQ(); int N = a.length;

for (int i = 0; i < N; i++) { pq.insert(a[i]);

if (pq.size() > k) pq.delMax(); /* MARK */

}

for (int i = 0; i < k; i++) System.out.println(pq.delMax());

Assume that  a[]  is an array of integers,  MaxPQ  is implemented using a binary heap, and N ≥ k ≥ 1.

(a) What does it output?

(b) What is the order of growth of its worst-­-case running time? Circle the best answer.

k log k   k logN   N log k  N logN  N²

Now suppose the marked line was deleted. Repeat the previous two questions.

(c) What does it output?

(d) What is the order of growth of its worst-­-case running time? Circle the best answer.

k log k   k logN   N log k  N logN  N²

 6. Data structures.

Given an N-­-by-­-N grid of sites, you wish to repeated select a site (i; j) at random among all sites not yet chosen. Consider the following code fragment for accomplishing this task.

ArrayList sites = new ArrayList(); for (int id = 0; id < N*N; id++) { // for each site, sites.add(id); // add to end of list

}

while (!sites.isEmpty()) {

int n = sites.size(); // number of elements left in list int r = StdRandom.uniform(n); // between 0 and n-1

int id = sites.remove(r); // remove and return item at index r int i = id / N, j = id % N; // site (i, j)

...

}

(a) The java.util.ArrayList data type is implemented using an array (with doubling and halving). What is the order-­-of-­-growth of the worst-­-case running time of the code fragment as a function of N? Select the best answer.

N             NlogN   N²           N²logN  N³           N⁴           2^N

(b) Assuming you have to choose an alternative implementation, which data structure that we've encountered in this course might you use instead of java.util.ArrayList? Select an answer and explain why you choseit.

i. union-­-?nd

ii. stack /queue

iii. deque

iv. randomized queue

v. binary heap

(c) For your version in (b), what is the order-­-of-­-growth of the worst-­-case running time as a function of N? Circle the best answer.

N             NlogN   N²           N²logN  N³           N⁴           2^N

(d) For your version in (b), what is the order-­-of-­-growth of the best-­-case running time as a function of N? Circle the best answer.

N             NlogN   N²           N²logN  N³           N⁴           2^N

(e) For your version in (b), what is the order-­-of-­-growth of the average-­-case running time as a function of N? Circle the best answer.

N             NlogN   N²           N²logN  N³           N⁴           2^N

7. Generalized queue.

Design a data structure that supports the following API for a generalized queue.

Generalized queue API

public class GQ

GQ() create an empty generalized queue

Item get(int i) return the ith item from queue

void addFirst(Item item) insert item at the front of the queue void addLast(Item item) append item to the end of the queue Item remove(int i) remove the ith item from the queue

Here is a sample client, showing the contents of the queue aUer each insertion / deletion.

GQ gq = new GQ(); gq.addFirst("A");    //A

gq.addFirst("B");              // BA

gq.addLast("C");               // B AC

gq.addLast("D");              // B A CD

gq.addFirst("E");              // E B A CD

gq.addFirst("F");              // F E B A CD

gq.addLast("G");              // F E B A CD G

String s1=gq.get(2);        // s1= "B"

gq.remove(2);   // F E A CD G

String s2=gq.get(2);        // s2 ="A"

Try to produce an efficient data structure (implement all operations in logarithmic time or beXer as a function of the size of the queue). Solutions will be graded for correctness, clarity, efficiency, and conciseness.

Alternatively, describe a data structure that implements all operations except remove in constant amortized time.

(a) Describe the underlying data structure.

(b) Draw it aUer the ?rst 7 insertions for the example above.

(c) Describe how to implement get().

(d) Describe how to implement addFirst() and addLast().

(e) Describe how to implement remove().