MPCS 55001 — Problem Set 2

Instructions

This problem set is due on Wednesday April 22, 2020 at 20:00 Central, to be submitted on Gradescope. Each problem is worth 10 marks in total.

Problems

  1. We say a string $u = a_1 \cdots a_k$ is a scattered subword of $v$ if $u$ can be obtained by deleting 0 or more symbols of $v$. For example, $thinly$ is a scattered subword of $otorhinolaryngology$.
    Give an algorithm, in pseudocode, that, when given a string $u$ of length $m$ and a string $v$ of length $n$, decides whether $u$ is a scattered subword of $v$ and runs in $O(m+n)$. Prove that your algorithm is correct and has the required running time.
  2. Rainbow3D is a Virtual YouTuber agency with many fun and interesting personalities. Suppose you are organizing a streaming event featuring a number of virtual 'tubers in order to attract new subscribers. This event will have a total time $T$. Each streamer $s_i$ has a block $t_i$ of time they are available and are expected to bring in $u_i$ new subscribers.
    What happens if a streamer near the end of the schedule exceeds the total time? In this case, they will be cut off, and we assume their number of new subscribers is proportional to the time they were able to stream. For example, suppose we have $T = 200$. Then one possible schedule is
    1. Akina plays Cooking Simulator for $t_a = 60$ and gets $u_a = 500$ new subs,
    2. Kanae plays ARK for $t_k = 120$ and gets $u_k = 1500$ new subs,
    3. Joe intended to multiply himself and chant around a campfire for $t_j = 30$ and was expecting to get $u_j = 3000$, but because he exceeds the time limit by 10, he only brings in $$u_j \times \left(1 - \frac{t_a + t_k + t_j - T}{t_j} \right) = 3000 \times \left( 1 - \frac{10}{30} \right) = 2000$$ new subs.
    The problem we would like to solve is the following:
    Given $n$ Virtual YouTubers $s_1, s_2, \dots, s_n$, where $s_i$ requires time $t_i$ and acquires new subscribers $u_i$, produce a schedule with total time $T$ such that the number of new subscribers is maximized.
    1. Assuming that the last streamer can get cut off, give an efficient algorithm in pseudocode for this problem and give a proof of its correctness and time complexity.
    2. Suppose that we decide that we would rather not just cut a streamer off. That is, we can only schedule $s_i$ if they are guaranteed to finish their block within time $T$. Show that your algorithm from part (a) no longer works.
  3. Recall that Dijkstra's algorithm requires that edge weights must be non-negative (i.e. $w : E \to \mathbb R^+$).
    1. Give an example of a graph containing negative edge weights where Dijkstra's algorithm fails to find a correct shortest path.
    2. Suppose we have $G$ with an edge weight function $w : E \to \mathbb R$ that contains negative edge weights. Consider each of the following proposed fixes.
      1. Define the edge weight function to be $w'(e) = w(e) + |k|$, where $k = \min_{e \in E} w(e)$.
      2. Define the edge weight function to be $w'(e) = w(e)^2$.
      For each of these fixes, determine whether they work (i.e. $P$ is a shortest path under $w$ iff $P$ is a shortest path under $w'$) and either give a proof of correctness or a counterexample.