Data structures: Given an N-by-N grid of sites, you wish to repeated select a si

Question

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.

(a) The java.u5l.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? Choose the best answer: (N, N logN, N2, N2 logN, N3, N4, 2N)

(b) Assuming you have to choose an alternative implementation, which data structure that might be used instead of java.u5l.ArrayList?

i. union-find

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? Choose the best answer: (N, N logN, N2, N2 logN, N3, N4, 2N)

(d) For your version in (b), what is the order-of-growth of the best-case running time as a funcyion of N? Choose the best answer: (N, N logN, N2, N2 logN, 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? Choose the best answer: (N, N logN, N2, N2 logN, N3, N4, 2N)

Even if you can't answer all of the parts, any help is appreciated. I am totally lost :(

Explanation / Answer

(a) 2N

(b) Stack / Queue

(c) N logN

(d) N logN

(e) N

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.