5 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 were about the activity selection problem, where we are given a collection of activities in terms of their start and end times , and the goal is to select a largest collection of non-overlapping activities, where two activities are said to overlap if their corresponding intervals intersect.

  1. The the most obvious rule might be to always select the available request that starts earliestβ€” that is, the one with minimal start time. Does this work?
    1. Yes,always
    2. No,never
    3. There exist examples on which the answer fails.
    4. Reveal answer
      βœ…

      There exist examples on which the answer fails.

      You can construct examples on which this works (an instance with only one activity, for examples) and ones on which this doesn't (e.g, the first request may block all others).

  2. Follow up strategy: start out by accepting the request that requires the smallest interval of time-namely, the request for which is as small as possible. Does this work?
    1. Yes,always
    2. No,never
    3. There exist examples on which the answer fails.
    4. Reveal answer
      βœ…

      There exist examples on which the answer fails.

      You can construct examples on which this works (an instance with only one activity, for examples) and ones on which this doesn't (e.g, one with three requests where a short request intersecting two large non-overlapping ones).

πŸ“

These questions were about the Islands War problem.

  1. What is the optimal answer for the example below?
    1. image
    2. _____ (In class, you were asked to enter a number.)
    3. Reveal answer
      βœ…

      1

      The bridge (3,4) will work.

  2. What is the optimal answer for the example below?
    1. image
    2. _____ (In class, you were asked to enter a number.)
    3. Reveal answer
      βœ…

      2

      The bridges (4,5) and (7,8) will work.

  3. If is the largest number of mutually disjoint requests and is the optimal answer, which of the following is true?
    1. Neither of the two
    2. Both [option wasn't available during class!]
    3. Reveal answer
      βœ…

      Note that option (a) is also true, so the correct answer is in fact (d); but at this point in the lecture the question was to identify the "obvious" inequality, which is the one in (b).