Question

Given a list of randomly arranged numbers, for example (6,2,9,5,8,7). Find the total number

of upturns in such list. If (a list[b]), then the pair (a,b) is called an upturn of

the list. In the given example, (6,2), (6,5), (9,5), (9,8), (9,7), (8,7) are of possible upturns that

meet the conditions and hence there are 6 upturns in such list.

a) Design a brute-force algorithm to return the number of possible upturns, and analyse

the complexity of your solution (5 marks)

b) Design a more efficient algorithm to do the same task with less complexity, and analyse

the complexity of your solution. (15 marks)

[Important instruction to be followed: Create an arbitrary unsorted list of 6 numbers

and use it to provide full explanation of how your proposed algorithm should work

step by step]

Answer 1

a) Brute-force algorithm:

To design a brute-force algorithm to return the number of possible upturns, we can use two nested loops to compare every pair of numbers in the list for upturns. Here is an outline of the algorithm:

• Initialize a counter variable to zero.

• Use a loop to iterate over each number in the list.

• Within the first loop, use another loop to iterate over each subsequent number in the list.

• For each pair of numbers (a,b), check if a < b. If so, increment the counter by 1.

• After all pairs have been compared, return the counter as the total number of upturns.

`Example code:`

# Create an arbitrary unsorted list of 6 numbers

numbers = [6, 2, 9, 5, 8, 7]

# Define a function to count upturns using brute force

def count_upturns(numbers):

count = 0

for i in range(len(numbers)):

for j in range(i+1, len(numbers)):

if numbers[i] < numbers[j]:

count += 1

return count

# Call the function with the example list and print the result

print(count_upturns(numbers)) # Output: 6

`b) Efficient algorithm:`

To design a more efficient algorithm to count upturns, we can use a modified version of the merge sort algorithm. Here is an outline of the algorithm:

• Divide the list into two halves.

• Recursively sort each half and count the number of upturns within them.

• Merge the two sorted halves together, and count the number of upturns between them.

• Return the total number of upturns as the sum of the upturns within each half and between them.

`Example code:`

# Create an arbitrary unsorted list of 6 numbers

numbers = [6, 2, 9, 5, 8, 7]

# Define a function to count upturns using merge sort

def count_upturns(numbers):

# Base case: if the list has only one or zero elements, it is sorted and has no upturns

if len(numbers) <= 1:

return 0

# Recursive case: divide the list into two halves

mid = len(numbers) // 2

left_half = numbers[:mid]

right_half = numbers[mid:]

# Recursively sort each half and count the upturns within them

count_left = count_upturns(left_half)

count_right = count_upturns(right_half)

# Merge the sorted halves together and count the upturns between them

i = j = k = count_merge = 0

while i < len(left_half) and j < len(right_half):

if left_half[i] < right_half[j]:

numbers[k] = left_half[i]

i += 1

else:

numbers[k] = right_half[j]

j += 1

count_merge += len(left_half) - i

k += 1

# Copy any remaining elements from the left or right half

while i < len(left_half):

numbers[k] = left_half[i]

i += 1

k += 1

while j < len(right_half):

numbers[k] = right_half[j]

j += 1

k += 1

# Return the total number of upturns as the sum of the upturns within each half and between them

return count_left + count_right + count_merge

# Call the function with the example list and print the result

print(count_upturns(numbers)) # Output: 6

The time complexity of this algorithm is O(n log n), where n is the length of the input list. This is because we are using a divide-and-conquer approach to sort the list, which has a time complexity of O(n log n), and then counting the upturns during the merging step, which has a time complexity of O(n). Overall, this algorithm is more efficient than the brute-force approach for large input sizes.

Step-by-step explanation: