CSE 326 - Winter 2002

Homework #8

Not to be turned in! Doing this homework will be good practice for the final exam.

K-d trees are described in Weiss 12.6 as well as the class lecture notes.

Quad trees are (briefly) described in exercise 12.39 of Weiss.

1. Weiss 12.38.

2. Weiss 12.39.

3. Henry, Nick, and Hannah, have each developed new algorithms for playing blackjack:

• Henry has an average-case analysis that his algorithm will make money.
• Nick has an amortized analysis that his algorithm will make money.
• Hannah has an expected-case analysis that her algorithm will make money.

They all go down to Las Vegas and hit the tables. This is what happens:

a) One of them sees his or her winnings fluctuate up and down randomly throughout the day, but at the end of the day comes out ahead.

b) One of them always sometimes loses and sometimes wins, but at the end of every complete pass through the deck has made money.

c) One of them quickly loses all of his money, playing against a shady-looking dealer named “Lefty”, who appears to be stacking the deck. However, Lefty is unable to consistently beat the other two players.

Question: Which of Henry, Nick, and Hannah were players (a), (b), and (c)? What on earth does this problem have to do with CSE 326?

4. Weiss 9.7 (a).

5. Weiss 9.15.

6. Suppose you are searching a tree-shaped maze with a branching factor of 2 (that is, for each non-leaf node there is one way in and two ways out). The exit and all dead-end rooms are at distance D. What is the probability that the first room you visit at distance D is in fact the exit, and not a dead-end?