a) Design a greedy algorithm that solves the problem; describe your algorithm wi

Question

a) Design a greedy algorithm that solves the problem; describe your algorithm with clear pseudocode; and prove the time efciency class of your algorithm.

If x,y are two adjacent elements in a sequence, with x before y, we say that the pair x,y is in order when x y and the pair is out of order when x > y. For example, in the string
“BEGGAR”
the pair G, A are out of order, but all the other pairs are in order. The out-of-order counting problem is: input: a list L of n comparable elements output: the number of out-of-order pairs in L
Hint: An optimal algorithm for this problem takes O(n) time.

b) Sort the characters of the string “SEQUENCE” using in-place selection sort; show your work.

Explanation / Answer

a)
currentElement = sequence[0]
for element in sequence{1:]:
   if(currentElement > element)
       out of order
   currentElement = element

b)

S E Q U E N C E

C E Q U E N S E

C E E E Q N S U

C E E E N Q S U

C E E E N Q U S

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

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