9 Aug, 2021

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.

  1. Is it possible that the task is impossible?
    1. Yes, even for K=2.
    2. Yes, but only when K is very large; and it seems like it should be always possible if K = 2.
    3. No, it's never impossible! In other words, the task is always possible for all values of K.
    4. Reveal answer
      βœ…

      Yes, even for K = 2

      Consider the input +- for K = 2.

  2. What is the solution for: - - - + - + + - with K = 3? (Enter -1 for impossible.)
    1. _______ (You were asked to enter a number in class.)
    2. Reveal answer
      βœ…

      3

      Flip at positions 1, 5, and 6 (1-based indexing).

  3. What is the solution for: + + + + + with K = 4? (Enter -1 for impossible.)
    1. _______ (You were asked to enter a number in class.)
    2. Reveal answer
      βœ…

      0

      Nothing to do.

  4. What is the solution for: + - + - with K = 4? (Enter -1 for impossible.)
    1. _______ (You were asked to enter a number in class.)
    2. Reveal answer
      βœ…

      -1

      This case is impossible.

  5. Does the order in which the flips happen matter?
    1. No, a set of flips executed in any sequence leads to the same outcome.
    2. Yes, the sequence matters I can always find two different sequences of the SAME SET of flips leading to different outcomes.
    3. It depends on the instance it may or may not matter.
    4. 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).

  6. Will an optimal solution ever repeat a flip?
    1. No.
    2. Repeated flips are present in any optimal solution.
    3. An optimal solution MAY have to repeat a flip.
    4. 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.