You may use any resource (book, internet, notes, etc) as long as you complete this exam by yourself. Turn in your exam by 5pm on Thursday March 4. E-mail submission is preferred (I will acknowledge) but you may turn it in to the CS department office in 202 Chapman. If you have questions, I am available via e-mail and office hours (12-1 on Tuesday March 2 and 11-2 on Wednesday March 3.) Normal office hours on Monday Mar 1 and Thursday Mar 4 are cancelled due to travel. If you are unsure how to proceed on a question and are unable to reach me in time, write down your assumptions and solve the problem based on those assumptions. You will be graded on your solution and how reasonable your assumptions were.

1. Develop an algorithm that will take as input two web page URLs and find a path of links from one to the other. Describe your search method and why you chose that one. Discuss the differences between finding any path as fast as possible and finding a path with the fewest number of links. Give an example that you solved by hand and shows how your algorithm works. (25 points)
    
2. Describe your approach to create a world champion Scrabble program. How much AI is necessary? Would you go with the Chinook approach or use the evolutionary learning approach? (25 points)
    
3. The sliding-tile puzzle consists of 3 black tiles, 3 white tiles, and an empty space:

   B

   B

   B

   W

   W

   W

   The puzzle has two legal moves with associated costs: a tile may move into an adjacent empty location at a cost of 1 OR a tile can hop over one or two other tiles into the empty position at a cost of the number of tiles jumped. The goal is to have all of the white tiles to the left of the black tiles. (25 points)
   1. What is the average branch factor?
   2. How deep can the search tree go? What if you eliminate cycles?
   3. Propose a heuristic to help in choosing the next move.
   4. What is required to find an optimal solution?
   
   
4. Google has some interesting ideas on their Labs page. One is sets (labs.google.com/sets), which creates sets of items from a few samples. For example, entering {chess, checkers, othello} returns {chess, checkers, othello, go, bridge, backgammon, poker, scrabble, battleship, overview, mahjongg}. Given the wealth of information they have, how do they do this? How much AI do you think is involved? (25 points)