Ask Computer Engineering Expert

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.

224_Figure.png

(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  N2

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  N2

 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   N2           N2logN  N3           N4           2N

(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   N2           N2logN  N3           N4           2N

(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   N2           N2logN  N3           N4           2N

(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   N2           N2logN  N3           N4           2N

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().

Computer Engineering, Engineering

  • Category:- Computer Engineering
  • Reference No.:- M92017901

Have any Question?


Related Questions in Computer Engineering

Does bmw have a guided missile corporate culture and

Does BMW have a guided missile corporate culture, and incubator corporate culture, a family corporate culture, or an Eiffel tower corporate culture?

Rebecca borrows 10000 at 18 compounded annually she pays

Rebecca borrows $10,000 at 18% compounded annually. She pays off the loan over a 5-year period with annual payments, starting at year 1. Each successive payment is $700 greater than the previous payment. (a) How much was ...

Jeff decides to start saving some money from this upcoming

Jeff decides to start saving some money from this upcoming month onwards. He decides to save only $500 at first, but each month he will increase the amount invested by $100. He will do it for 60 months (including the fir ...

Suppose you make 30 annual investments in a fund that pays

Suppose you make 30 annual investments in a fund that pays 6% compounded annually. If your first deposit is $7,500 and each successive deposit is 6% greater than the preceding deposit, how much will be in the fund immedi ...

Question -under what circumstances is it ethical if ever to

Question :- Under what circumstances is it ethical, if ever, to use consumer information in marketing research? Explain why you consider it ethical or unethical.

What are the differences between four types of economics

What are the differences between four types of economics evaluations and their differences with other two (budget impact analysis (BIA) and cost of illness (COI) studies)?

What type of economic system does norway have explain some

What type of economic system does Norway have? Explain some of the benefits of this system to the country and some of the drawbacks,

Among the who imf and wto which of these governmental

Among the WHO, IMF, and WTO, which of these governmental institutions do you feel has most profoundly shaped healthcare outcomes in low-income countries and why? Please support your reasons with examples and research/doc ...

A real estate developer will build two different types of

A real estate developer will build two different types of apartments in a residential area: one- bedroom apartments and two-bedroom apartments. In addition, the developer will build either a swimming pool or a tennis cou ...

Question what some of the reasons that evolutionary models

Question : What some of the reasons that evolutionary models are considered by many to be the best approach to software development. The response must be typed, single spaced, must be in times new roman font (size 12) an ...

  • 4,153,160 Questions Asked
  • 13,132 Experts
  • 2,558,936 Questions Answered

Ask Experts for help!!

Looking for Assignment Help?

Start excelling in your Courses, Get help with Assignment

Write us your full requirement for evaluation and you will receive response within 20 minutes turnaround time.

Ask Now Help with Problems, Get a Best Answer

Why might a bank avoid the use of interest rate swaps even

Why might a bank avoid the use of interest rate swaps, even when the institution is exposed to significant interest rate

Describe the difference between zero coupon bonds and

Describe the difference between zero coupon bonds and coupon bonds. Under what conditions will a coupon bond sell at a p

Compute the present value of an annuity of 880 per year

Compute the present value of an annuity of $ 880 per year for 16 years, given a discount rate of 6 percent per annum. As

Compute the present value of an 1150 payment made in ten

Compute the present value of an $1,150 payment made in ten years when the discount rate is 12 percent. (Do not round int

Compute the present value of an annuity of 699 per year

Compute the present value of an annuity of $ 699 per year for 19 years, given a discount rate of 6 percent per annum. As