---------> hello i need solution for this question please. and also make sure yo
ID: 3743238 • Letter: #
Question
---------> hello i need solution for this question please. and also make sure you show me all steps to solve it please.
this is from:
Algorithms and Complexity
3 The Pancake Problem A stack of n pancakes is placed in front of you. You have a spatula which you can insert anywhere into the stack and flip over all the pancakes above the spatula. You want to arrange the pancakes in order of their diameter (they are perfectly round), and you want to use as few flips as possible. As an example suppose n = 6, and the pancakes are numbered 1 through 6 in order of their diameter with 1 the smallest and 6 the largest. Suppose sequence represents the top of the stack. In one flip I can get 643215 (by flipping the first three pancakes: 346), then in the next flip 512346, then 432156, then 123456, so four flips are enough in this case. Let F(n) be the worst case number of flips needed to arrange a stack of n pancakes Find an efficient (in a worst case sense) algorithm for this problem, where efficiency is measured by the worst case number of flips. Remember that your algorithm should work for pancakes with any order. To start you off you should easily be able to show that F(n) is at most 2n. Next, reduce that bound a little more if you can. (Hint: first think about how to move the largest pancake to the bottom..) the original order is 346215, and the left end of the 4 The Glass Jar problem You are doing stress-testing on some kind of glass jars to determine the height from which they can be dropped and sl not break. Here is the setup. You have a ladder with n rungs, and you want to find the highest rung from which you can drop a copy of this jar and not break. We call this the highest safe rung. Obviously, if a jar is not broken in a throwing, it can be reused; otherwise, you have to use a new jar Now you are only given K (identical) jars. For simplicity, supoose K-2 (i.e. you only have two copies of the glass jar). Of course, you can take the simplest way: try throwing one jar from the lowest rung and move one rung up if it does not break. But in the worst case you may need to throw n times, which seems to be not so optimal (note you only use one jar in this case). So our goal is to throw as few times as possible while only using at most K 2 jars. Now your task: describe a strategy for finding the highest safe rung that only uses K2 jars and also minimizes the number of throws in the worst case. Also tell me what is the smallest number of throws you need for the n 100 case (i.e. 100 rungs) 1.Explanation / Answer
AS PER CHEGG WE CAN ANSWER ONLY FIRST QUESTION
ANS:
In simple terms, the following two steps are enough to be called an algorithm to sort a stack of pancakes through flipping:
1. Find the largest out of order pancake and flip it to the bottom.
2. Repeat the step until the stack is ordered.
By following this algorithm we one by one place the largest element at the end and reduce the size by one.
Algorithm:
Let given array be arr[] and size of the array be n.
Start from the current size equal to n and reduce current size by one while it is greater than one. Let the current size be curr_size. Do following for every curr_size
a) Find index of maximum element in arr[0...curr_size-1]. Let the index be mi.
b) Call flip(arr,mi)
c) Call flip(arr, curr_size-1)
The above algorithm takes a total of O(n) flip operations
OR
ANS:
Consider any arbitrary sequence of pancakes.
We know that we can move the highest number pancake to the back of the stack in two operations. The first operation bisects the stack immediately after the highest value and moves it to the front.
e.g. x ... hi x ... x --> hi ... x x ... x
The second operation moves the highest value to the right most position.
e.g. hi ... x x ... x --> x ... x x ... hi
Once the highest value item is in position for the sequence of length n, we can do the same for the subsequence of length n-1.
It is only when we reach the last element that we need to do nothing, because a single element need not be flipped.
For sequences of length n, the sorting can be performed in 2n - 2 operations.
2 operations per element of the list with the exception of the last element.
Reducing beyond this would be another question.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.