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

COMP2711 - Algorithms and Data Structures 1

Coursework 1

Question 1    [6 marks]

Suppose a problem involves an input array of n elements. There are five algorithms A1, A2, ..., A5 for solving the problem. Algorithm Ai performs ti(n) operations, i = 1,2, … ,5,

The graphs of the functions ti(n) are presented below.

1.1-1.8 The following pseudocode (containing gaps) is designed to run the fastest algorithm depending on the input size n. Notice that n is a positive integer.

Moreover, since t5(1) = 0, we assume that n ≥ 2.

Fill in the underlined gaps in the pseudocode.    [4 marks]

1.9-1.12 Arrange the functions ti(n), i = 1,2, … ,5, by growth rate, from slowest to fastest.    [2 marks]

Question 2    [6 marks]

For each of the functions given below, state the big-O complexity class.

2.1 25n(n + 2)

2.2 n³ + 2n² − 3n + 4

2.3 25n² − 12n

2.4 30 log2 n + n

2.5 30n log2 n + 31n

2.6 2n log2 n + n²

Question 3    [5 marks]

Specify the big-O complexity class for the function n² + n² log2 n − 3n + 3.

Use the formal big-O definition to prove your answer. The proof should include the values of the constants c and n0 and their justification.

Question 4    [12 marks]

The insertion sort algorithm is stated below. Operation of insertion sort can be described as follows. The list at any moment is divided into two parts: sorted and unsorted. In each pass of the algorithm, the first element of the unsorted sub-list is inserted into the appropriate place of the sorted sub-list.

4.1– 4.7    [7 marks]

Consider the tracing table presented below. The input array is (23, 78, 45, 8, 32, 56). Each line of the table represents the array after the assignment A[j+1]←A[j] or A[j+1]←tmp is made. There are gaps indicated in red. Fill in the gaps.

4.8 What is a worst-case instance for insertionSort?    [1 mark]

an array in descending order                    

an array consisting of equal elements        

an array in ascending order                      

none of the above                                   

4.9 What is the total number of comparisons tmp < A[j] done by the algorithm in the worst case for an array consisting of n elements? Provide a brief explanation. State the big-O complexity class (no need to use the formal definition).    [4 marks]

Question 5    [5 marks]

The following algorithm operates on array A of n non-negative integers that represent the quantities of products available at a store. To simplify the replenishment process, a manager needs to reorder the array so that small quantities appear first, followed by large quantities, where

A[i] is small if A[i]<100,

A[i] is large if A[i]≥100.

In the pseudocode we assume that array A contains at least one small value and at least one large value.

5.1 How many swaps (3 assignments) are performed in the worst case?    [3 marks]

State the big-O complexity class.    [1 mark]

5.2 The required outcome can be achieved if we apply insertion sort to array A.

Which approach is faster:    [1 mark]

Algorithm Reorder               

Algorithm insertionSort        

Question 6    [11 marks]

Consider the problem of calculating xⁿ. The straightforward (brute-force) algorithm exp1(x,n) performs n multiplications, achieving the time complexity O(n).

A more efficient approach implements the following formula for xⁿ:

or equivalently

Hint: to understand how the algorithm works, it is worth to trace it first for the case x = 2 and n = 8.

6.1 Trace algorithm exp2(x,n) with x = 2 and n = 11:    [9 marks]

State the output.

6.2 State the big-O complexity class.    [2 marks]