PS10: Graphs & Trees

Due Mon 4/27 @ 1:30pm.

Do these problems from the book, listed on page 1140.

  1. 11.109
  2. 11.110 (By “simultaneously”, we mean “in the same bubble”. BFS gives you no guarantee about the order in which neighbors of a given node are iterated over, and therefore the order in which they're added to the frontier. But we do know that every node in the bubble $k$ edges away from the starting node will be discovered before any node in the $k+1$ bubble.)

Also do these problems, listed on pages 1155–1157.

  1. 11.112
  2. 11.128
  3. 11.146 (The definition of “complete binary tree” is above question 11.143.)