Answer to Question #216694 in Java | JSP | JSF for Anuj Yadav

Question

Consider a pile of coins. You have given ‘n’ coins of different sizes and you want to sort the pile so that smaller coins are on the top of larger ones. The only “operation” you are allowed to perform is- take top ‘k’ coins together, and place them back to the pile upside down.

Describe an algorithm to sort an arbitrary pile of n coins using O(n) operations. Exactly how many operations does your algorithm perform in the worst case.
For every positive integer ‘n’, describe the pile structure that requires (Omega) Ω(n) operations to sort. In other words, generate an example of a pile that will require at least cn operations for some c > 0. (n > 3)
Now suppose in the sorted array we want all coins to have heads face up. Describe an algorithm to sort an arbitrary pile of ‘n’ coins, such that all coins have tails face down, using O(n) operations. Exactly how many operations does your algorithm perform in the worst case

Answer 1

1. Find a O(log(n)) algorithm to find a single heavy coin.
2. Find a O(log(n)) algorithm to split a set into two sets with equal number of heavy and light counts plus up to two leftovers (for when there are not even amounts of each).
3. Combine algorithms #1 and #2.