Question

Q1) (1 point) Design an efficient algorithm (in terms of asymptotic complexity in the worst case) to determine if two students in a class of n students have the same height. What is the complexity of your algorithm?

a.Provide the pseudo-code of that algorithm.

b.Implement the algorithm in a language of your choice and provide a sample run with meaningful input.

Answer 1

Solution

1)

Consider we have 2 cases for the mentioned scenario

Case 1:The smallest measure in cm

Case 2:There is no such a limit

Time Complexity

Case 1

Answer

Θ(n)

Explanation

First Initializie the height slots to unmark

Then Measure each student

Then mark the corresponding to the height slot

return true if the marked slot is visited

--

Case 2

Answer

Θ(n lg n)

Explanation

we need to apply any Θ(n lg n) sorting algorithm

Scan the sorted array from left & right , return true whenever 2 neighbours are of the same height

return false in case if there is no true retun at the both cases

---

Pseudocode

Height(i) is the height of the student i

Mark(j) is the mark for the height j

miinimum_height & maximum_height are predetermined can be calculated in the linear time

HEIGHT_CASE_1(Height, A)
1 for j<-minimum_height to maximum_height
2 Mark[j]<-false
3 for i<-1 to n
4 if Mark(Height(i))
5 then return true
6 else Mark(Height(i))<-true
7 return false

HEIGHT_CASE_2(Height, A)
1 quicksort (Height)
2 for i<-1 to n-1
3 if Height(i) = Height(i + 1)
4 then return true
5 return false

---

provided complexity and pseudocode

really sorry couldnt able to complete the b

all the best