Reference no: EM131263130

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.

Input	1	2	3	4	ti	6	7	8	Sorted
COS	ARC	ARC	ARC	COS	ART	CHM	CHE	REL	ARC
PHY	CHE	CHE	ART	COS	CEE	ART	COS	PHY	ART
ELE	COS	COS	CEE	ELE	CHM	ARC	CHM	PHY	CEE
COS	COS	COS	CHE	PHY	ARC	CEE	COS	ELE	CHE
MAT	ECO	ECO	CHM	ARC	COS	CHE	COS	PHI	CHM
MOL	ELE	EEB	COS	LIN	CHE	COS	ART	ORF	COS
LIN	GEO	ELE	COS	MAT	EEB	COS	CEE	ORF	COS
ARC	LIN	ELE	COS	MOL	COS	COS	ARC	COS	COS
ECO	MAE	ENG	COS	CHE	COS	COS	COS	ELE	COS
CHE	MAT	GEO	COS	ECO	COS	COS	COS	EEB	COS
MAE	MOL	LIN	COS	GEO	EEB	COS	MAE	MUS	COS
GEO	PHY	MAE	ECO	MAE	COS	ORF	GEO	GEO	ECO
ORF	ORF	MAT	ORF	EEB	COS	EEB	ORF	ORF	EEB
EEB	EEB	MOL	EEB	ELE	ELE	ENG	EEB	MAT	EEB
ENG	ENG	ORF	ENG	ENG	MAE	ELE	ENG	LIN	ELE
ELE	ELE	PHY	ELE	ORF	ELE	GEO	ELE	COS	ELE
COS	COS	ART	MOL	CEE	ECO	ELE	ECO	COS	ELE
ELE	ELE	CEE	ELE	COS	ENG	MAE	ELE	ECO	ENG
CEE	CEE	COS	ELE	EEB	MAT	EEB	LIN	CEE	GEO
EEB	EEB	EEB	EEB	ELE	LIN	ECO	EEB	CHE	LIN
ART	ART	ELE	PHY	ART	ELE	MUS	MOL	ART	MAE
MUS	MUS	MUS	MUS	MUS	MUS	PHI	MUS	MAT	MAT
PHI	PHI	ORF	PHI	ORF	MAT	ORF	PHI	MAE	MAT
ORF	ORF	PHI	ORF	PHI	ORF	LIN	ORF	ELE	MOL
COS	COS	COS	GEO	COS	GEO	PHY	MAT	COS	MUS
PHY	PHY	PHY	PHY	COS	ORF	MOL	PHY	MOL	ORF
COS	COS	COS	LIN	MAT	MOL	MAT	COS	COS	ORF
MAT	MAT	MAT	MAT	PHY	PHY	MAT	MAT	EEB	ORF
CHM	CHM	CHM	MAT	CHM	ORF	ORF	ELE	CHM	PHI
ORF	ORF	ORF	ORF	COS	PHY	ELE	ORF	ENG	PHY
COS	COS	COS	MAE	ORF	PHI	REL	PHY	COS	PHY
REL	REL	REL	REL	REL	REL	PHY	REL	ARC	REL
Input	1	2	3	4	ti	6	7	8	Sorted

(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<Integer> pq = new MaxPQ<Integer>(); 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<Integer> sites = new ArrayList<Integer>(); 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<Item item>

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<String> gq = new GQ<String>(); 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().