Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

DDA6050 Assignment 1

1 Sorting Algorithm (20 marks)

Given an unsorted array, we want to find the median of this array.

(a). Adapt the algorithm of the quick sort (which randomly selects a pivot) and find an efficient approach to solve the above task. “Efficient” is in the sense that you do not need to sort the whole array in most cases. (10 marks).

(b). Analyze the time complexity of the best, average and worst case and auxiliary space (10 marks).

2 Master Theorem (20 marks)

If T(1) = O(1), give asymptotic upper and lower bounds for T(n) in each of the following recurrences. Make your bounds as tight as possible, and justify your answers. Note: You are only allowed to use the following version of the Master theorem which is a slightly generalized one compared with that in the course slides and it is stated below. More generalized versions of the Master theorem are not allowed to be directed used.

Let T(n) be a monotonically increasing function that satisfies

T(n) = aT(n/b) + f(n)

T(1) = c

where a ≥ 1,b ≥ 2, c > 0. If f(n) is Θ  where d ≥ 0 then

3 Recursion Tree (5 marks)

Plot a recursion tree and compute an asymptotically tight solution to the recurrence relation

where d ≥ 1 and k > 0 are constants.

4 Substitution Method (5 marks)

If T(n) = 4T(n/2 + 2) + n, obviously, T(n) = O(n²). Use the substitution method to verify the above answer.

5 Valid Parentheses (10 marks)

We want to compute how many valid ways to add n pairs of parentheses, e.g. There are 5 valid ways to add 3 pairs of parentheses. ((())), (()()), (())(), ()(()), ()()(). Let r_n denote the number of ways to add n pairs of parentheses. How do we compute r_n using r₁,r₂,...,r_n−1? Brief your solution.

6 Maximum Length of Stair (20 marks)

Given a square matrix, a stair is defined as a 2D integer series where each new integer a_n+1 can appear in the right or down of the current integer a_n. Also, we have |a_n+1 − a_n| = 1. We want to find the maximum length of stairs in the square matrix. For example, in the following square matrix, 5 → 4 → 5 → 6 → 7 → 8 → 7 → 6 highlighted in the red color is a maximum stair and 2 → 3 → 4 and 7 → 8 → 9 highlighted in the green color are stairs but not maximum stairs. Please write recursive formulation and pseudocode to find the maximum length of stairs.

7 Tetris Container (20 marks)

Given an integer array, where a₀,a_n = 0, a_i represents the number of cubics stacked in the position i. These cubics can contain rice represented in yellow. The following figure is an example: the unit of rice that can be contained is 1 + 6 + 17 = 24. Please write recursive formulation and pseudocode to find the unit of contained rice.