Reference no: EM131650846

Data Structures Assignment

• Question 1: Asymptotic Notations

(a) Which one of the following is wrong?

1. Θ(n) + O(n) = Ω(n)
2. O(n) + Ω(n) = Θ(n)
3. Θ(n) + O(n) = O(n)
4. f (n) = O(g(n)) implies g(n) = Ω(f (n))

(b) Which one of the following sorting algorithms will have the best best-case running time?

1. Selection sort
2. Insertion sort
3. Heap sort
4. Quick sort

(c) Explain why the statement, "The running time of an algorithm is at most Ω(n)," is meaningless.

• Question 2: Running Time and Growth of Functions

(a) Assume evaluating a function f (n) in the pseudocode below takes Θ(n) time.

i = 1;
sum = 0;
while (i <= n)
do if (f(i) > k)
then sum += f(i);
i = 2*i;

What is the running time (use an asymptotic notation) of the above code? Justify your answer.

(b) For the following functions, please list them again but in the order of their asymptotic growth rates, from the least to the greatest. For those functions with the same asymptotic growth rate, please underline them together to indicate that.

(log₂ n)ⁿ, (log₂ nⁿ), n², (log₂ n²), n^1/2, 2ⁿ, (√2)², log₁₀ n

• Question 3: Sorting

(a) For a given input array A : < 3, 7_a, 5, 9, 8, 11, 7_b, 12, 13 >, what is the sequence of numbers in A after calling Build-Max-Heap(A) ? (please show the intermediate trees).

(b) For a given input array A : < 2_a, 9, 3, 1, 8, 5, 2_b, 7, 4 >, what is the sequence of numbers in A after the first partition (by calling Partition(A, 1, 9))? Note that 1 and 9 in Partition(A, 1, 9) function call are array indexes.

(c) By using the Max-Heap data structure to implement a priority queue, some applications may need to change the data (priority) of a specific node i. That is, given an index i, change the priority of node i to a new priority t. Please write a pseudocode for this procedure.

Max-Heap-update(A, i, t)
{

}

(d) Please describe how to use a priority queue to implement a queue.

• Question 4: Linear Time Sorting

(a) Please describe the reason(s) why we choose the counting sort algorithm to sort each digit in the Radix Sort?

(b) What is the best running time to sort n integers in the range [0, n³ - 1], and How?

(c) Given an input array A with n integers in [0, k], we can use the array C in the counting sort to find out how many integers in A are in a range [a, b]. Write a pseudocode for this query. Assume C[i] already contains the number of input integers ≤ i.

FindNumIn(a, b) // both a and b are integers.