Courses βΈ± Algorithms
You can also access the quiz on Itempool here if you want to practice, or see the notes below for more context.
Lecture Recording
In-class Quiz Questions
These questions pertain to the Oversized Pancake Flipper. "+" denotes happy side up.
- Is it possible that the task is impossible?
- Yes, even for K=2.
- Yes, but only when K is very large; and it seems like it should be always possible if K = 2.
- No, it's never impossible! In other words, the task is always possible for all values of K.
Reveal answer
Yes, even for K = 2
Consider the input +- for K = 2.
- What is the solution for: - - - + - + + - with K = 3? (Enter -1 for impossible.)
- _______ (You were asked to enter a number in class.)
Reveal answer
3
Flip at positions 1, 5, and 6 (1-based indexing).
- What is the solution for: + + + + + with K = 4? (Enter -1 for impossible.)
- _______ (You were asked to enter a number in class.)
Reveal answer
0
Nothing to do.
- What is the solution for: + - + - with K = 4? (Enter -1 for impossible.)
- _______ (You were asked to enter a number in class.)
Reveal answer
-1
This case is impossible.
- Does the order in which the flips happen matter?
- No, a set of flips executed in any sequence leads to the same outcome.
- Yes, the sequence matters I can always find two different sequences of the SAME SET of flips leading to different outcomes.
- It depends on the instance it may or may not matter.
Reveal answer
No, a set of flips executed in any sequence leads to the same outcome.
See the lecture for a proof. Hint. Think about the experience of any single cookie through two different sequences of flips (but at the same locations).
- Will an optimal solution ever repeat a flip?
- No.
- Repeated flips are present in any optimal solution.
- An optimal solution MAY have to repeat a flip.
Reveal answer
No
An odd number of flips at a given location is the same as one flip at said location and an even number of flips is the same as none.
Β