General description: A tiny Lotto system allows up to 1000 people play “lotto”. This system provides some functions to facilitate lotto players to check their game status and get more information of l
Question 3:
c. Algorithm analysis
Binary search algorithm
def binarySearch(data, elem):
low = 0
high = len(data) - 1
while low <= high:
middle = (low + high)//2
if data[middle] == elem:
return "exists"
elif data[middle] > elem:
high = middle - 1
else:
low = middle + 1
return -1
def displayStatisticsOfWinners(PWNs, SWNs, userNo):
first_class = 0
snd_class = 0
thrd_class = 0
frth_class = 0
for elem in range(len(userNo)):
matches = 0
for num in range(len(userNo[elem])):
result = binarySearch(PWNs, userNo[elem][num])
if result == "exists":
matches = matches+1
if matches == 6:
first_class = first_class+1
elif matches == 5:
snd_class = snd_class+1
elif matches == 4:
thrd_class = thrd_class + 1
elif matches == 3:
frth_class = frth_class + 1
else:
for num in range(len(userNo[elem])):
result = binarySearch(SWNs, userNo[elem][num])
if result == "exists":
matches = matches+1
if matches == 2:
frth_class = frth_class + 1
Given sorted array of 6 say arr1=[4,13,17,21,25,28] and arr2=[2,13,18,21,29,30]
To find elements in arr1 matching in arr2, there will be many iterations.
Iteration 1:
Lets say to search 21, the binary search algorithm on first iteration finds 18 the middle element.
Since 21 is more than 18, the array is sub divided into two,sub array with elements greater than 18 is taken. [21,29,30]
Iteration 2:
Select middle element from array [21,29,30]
Which the middle element is 21. Since it is the middle element, iteration stops there.
The iteration stops after j iterations.
At each iteration, the array is divided by half.
The algorithm takes constant n size to store the array thereby space complexity is O(log n)
Best case performance: O(1)
Average case performance:O(log n)
Worst case performance:O(1)
Match based algorithm
def checkMyLottoStatus(PWN, SWN, userNos, ID):
result = []
for num in userNos:
for each in PWN:
if (num == each):
result.append(num)
if(len(result) < 3):
result = []
for num in userNos:
for each in SWN:
if (num == each):
result.append(num)
The algorithm iterates array userNos, n times, giving O(log n)
It then iterates array PWN O(n log n)
It then checks for each element on PWN if matches with num of userNos,
This takes constant time O(1)
Average best performance: O(n logn)
Best case :O(1)
Average performance: O(n)
