Spring 2015

CS 202: Math of CS

Jadrian Miles

Due Mon 4/27 @ 1:30pm.

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

- 11.109
- 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.

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