Greedy Algorithms. Need help with solving this. Thank you Let E = {e1, e2, ....,

Question

Greedy Algorithms.

Need help with solving this. Thank you

Let E = {e1, e2, ...., en} be a sequence of integers. We say that an integer ei forms a majority in E if it appears more than ceil(n/2) times in E. For instance, the integer 3 is a majority in sequence E = {2, 3, 3, 2, 3, 3), whereas the sequence E = {6, 3, 2, 7, 3, 1} has no majority. It can be proved that if ei not equal to ej and E has value em as majority, then sequence E - {ei, ej} also has em as majority. a) Present a greedy algorithm to decide whether E has a majority. b) Explain why we can or can't use Dynamic programming to solve this problem.

Explanation / Answer

2)

dynemic programming has some principles like

overlapping subproblems etc.

and it is used to convert exponential time algorithms to polynomial time algorithms by memorising the already solved sub problems.

here we are not solving here any overlapped subproblems we cannot use dynemic programming here

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

---

---

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