Egg drop and DAG DP

Questions 1 to 5 of 8

1. 1. Put the steps of Kahn's algorithm in the order the lesson gives them.

   Use the arrows to put the steps in order.

   1. 1.Take a vertex from the front of the queue, add it to the order, and lower the in-degree of each vertex it points to↑↓
   2. 2.Stop when the queue is empty, then check that the order holds every vertex↑↓
   3. 3.Put every vertex with in-degree 0 into a queue↑↓
   4. 4.Count the in-degree of every vertex↑↓
2. 2. What does this program print? ``python reach = [[0] * 3 for _ in range(5)] for m in range(1, 5): for e in range(1, 3): reach[m][e] = reach[m - 1][e - 1] + reach[m - 1][e] + 1 print(reach[3][2], reach[4][2]) ``

   3 67 116 106 9
3. 3. In the moves table reach[m][e], what does the value mean?

   The most floors that m drops and e eggs can always resolveThe fewest drops needed for m eggs and e floorsThe number of ways to choose m items from eThe number of eggs that survive m drops
4. 4. Match each term from the lessons to its meaning.

   Choose the matching item for each row.

   reach[m][e]Choose…the number of arrows that point into a vertexupdate the target's best length if the new path is longerNone, a value no real path length can bethe most floors that m drops and e eggs can always resolvein-degreeChoose…the number of arrows that point into a vertexupdate the target's best length if the new path is longerNone, a value no real path length can bethe most floors that m drops and e eggs can always resolverelax an edgeChoose…the number of arrows that point into a vertexupdate the target's best length if the new path is longerNone, a value no real path length can bethe most floors that m drops and e eggs can always resolveNone markerChoose…the number of arrows that point into a vertexupdate the target's best length if the new path is longerNone, a value no real path length can bethe most floors that m drops and e eggs can always resolve
5. 5. What happens when this Python code runs? ``python unknown = None candidate = unknown + -1 print('NONE + -1 =', candidate) ``

   It prints NONE + -1 = -1, because None counts as 0It raises TypeError: unsupported operand type(s) for +: 'NoneType' and 'int'It prints NONE + -1 = 0It wraps around to the largest int