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.

Β