THIS QUESTION MUST BE ANSWERED WITH CLEAR ENGLISH PSEUDOCODE! Your army consists

Question

THIS QUESTION MUST BE ANSWERED WITH CLEAR ENGLISH PSEUDOCODE! Your army consists of a line of N giants, each with a certain height. You must designate precisely L N of them to be leaders. Leaders must be spaced out across the line; specifically, every pair of leaders must have at least K 20 giants standing in between them. Given N,L,K and the heights H[1.N] of the giants in the order that they stand in the line as input, find the maximum height of the shortest leader among all valid choices of L leaders. We call this the optimisation version of the problem. Forinstance,supposeN =10,L=3,K-2andH-|1,10,4,2,3,7, 12,87,2]. Then among the 10 giants, you must choose 3 leaders so that each pair of lead- ers has at least 2 giants standing in between them. The best choice of leaders has heights 10, 7 and 7, with the shortest leader having height 7. This is the best possible for this case. (a) In the decision version of this problem, we are given an ad- ditional integer T as input. Our task is to decide if there exists some valid choice of leaders satisfying the constraints whose shortest leader has height no less than Give an algorithm that solves the decision version of this problem in O(N) time (b) Hence, show that you can solve the optimisation version of this problem in O(N log N) time

Explanation / Answer

1.Start
2.Read N, L, H[], T
3.for every element in H[] find the max of all the elements
H[i]>H[i+1]
Max=H[i]
4.assign Leader1 L=Max
5.To find next short leader:
remove Max from H[]
Again find max of all elements in H[]
H[i]>H[i+1]
Max=H[i]
6.assign Leader2 L=Max
contine this until all Leaders, L are found.
7.maximum height of shortest leader is least value of Max
8.Compare T and least Max value
9.Stop
This algorithm gives O(N) time.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.