Q1. Operation Bloopy Freedom ( 14 points )

In the midst of an epic adventure, our favorite agent, Mr. Bloop, finds himself locked in a dungeon. Looking around, he finds only two objects in the room: a note and a flute. The note says: play my favorite tune of 10 notes or less, and the door shall open with success. Mr. Bloop tests the flute and finds out that it can play only 3 notes: D, E, G. Hence, Mr. Bloops freedom relies on finding the sequence of these three notes that unlocks the door. As a diligent AI student, you want to help Mr. Bloop by formulating his predicament as a search problem: The initial state is silence (i.e., an empty sequence of notes) The successor function is to add one note (D, E, or G) to the sequence. The goal test is to see whether the resulting tune (i.e., sequence of notes) has unlocked the door or not. You also happen to know that there are 5 tunes that can unlock the door: GEDGE , GEDG, EGDEDGE, EDEDE, and DDDGGG. You can assume that if there is a tie between states, the note with alphabetical precedence wins (e.g., between E and G, E is expanded before G). a) [3pts] Which of the 5 tunes above will be returned by breadth-first search? Why?

b) [3pts] Which of the 5 tunes will be returned by depth-first search? Why?

c) [4pts] Mr. Bloop has a feeling that some notes are more likely to be in the correct tune. You help him capture this feeling by assigning costs to each note: c(D) = 2, c(E) = 4, and c(G) = 6. With this cost structure, which of the above 5 tunes will be returned by uniform cost search? Why?

d) [4pts] Now assume that there is only one tune that can unlock the door, which is unknown as it is randomly selected from the space of all possible tunes ( with 10 notes or less). Also assume that all notes have the same cost ( e.g., c( D) = c( E ) = c( G) = 1). Given any heuristic, would A* search expand on average fewer, more, or the same number of states as depth-first search? Why?