Analysis of Algorithms: Design and Implementation - Data Science

This assignment solution presents algorithms for three different problems. The first problem involves adding two integers with m and n digits respectively, with a time complexity of O(m+n). The solution provides pseudocode and analyzes the time complexity. The second problem focuses on finding an index i in a sorted array T such that T[i] = i, utilizing binary search with a time complexity of O(log n). The solution includes pseudocode and explains the divide and conquer approach. The third problem addresses finding a majority element in a sorted array T, utilizing a hashmap to determine if an element appears more than n/2 times, with a linear time complexity of O(n). The solution offers pseudocode for each algorithm and discusses their respective complexities, demonstrating a clear understanding of algorithm design and analysis.

Question 1:
Algorithm:
The algorithm is used to have two seperate loop which add an integer with m digits and integer with
n digits.
Pseudocode:
Procedure findSum ()
set sum=0
for (i : mInt) {
sum= sum +i
}
for (i : nInt) {
sum= sum +i
}
return sum
end procedure
The complexity of first loop is O(m) and second loop is O(n) then combine complexity is O(m) +
O(n) = O(m+n).
Question 2:
Algorithm:
For this mentioned the algorithm is Binary search, the best case complexity is O(1) the searched
element is present at mid-point, and worst case complexity is O(logn).
This algorithm is based on the Divide and conquer principle. Binary search compares the element
with the middle item in the collection if match is found then index is returned and if middle value is
greater than the element searched then it search to the sub array to the left of the middle term and if
middle term is small then it search in sub array to the left of middle term, this searching continues
until the sub array becomes to zero.
Pseudocode:
function binarySearch
T – Sorted array
n – Array size
i – Index to be searched
set lower=1
set upper =n
while i not found:
if upper < lower
EXIT : i does not exists

set mid=lower+ ( upper - lower ) / 2
if T[mid]< i
set lower = mid +1
if T[mid]>i
set lower = mid -1
if T[mid]=i
Exit : i found at mid.
End while
End Function
Question 3:
Algorithm:
The algorithm to find the majority element in T is HashMap (key-value pair), this algorithm works
in linear time complexity, the complexity of this algorithm is O(n).
This algorithm maintains the count of each element, the element is key and the count is value, once
the count of each element is stored in hashmap then it compares the count with n/2 and if count for
element is greater than n/2 then it returns key (element) as majority element.
Pseudocode:
procedure findMajority (T, n)
set map = {}
loop i from 0 to n-1
if T[i] exists:
map[T[i]] +=1
else
map[T[i]] +=1
end if
end loop
flag = 0
loop key in map:
if map[key]> n/2:
flag=1
print majority found key
end if

end loop
if flag==0
print("No Majority element")
end if
end procedure.