Assignment Instructions
Answer the following questions. Please TYPE your answers below each question.
Part 1: Search
Solve each of the following problems using a best-first search method as described in the background section. Diagram out your search trees; note that you will need to design a representation of each state in the tree that is appropriate to the problem that you are solving (Hint: on 1 & 3 use a text description for each state). IMPORTANT NOTE: 2/3rds of the grade on these questions will be for showing that you understand the problem solving technique, only 1/3 of the grade is for correctness of you answer. So you MUST show your work in order to get most of the points on these questions; just listing the correct answer is only worth 1/3 of the points.
Q1: What is the minimum number of steps required to transform the eight-puzzle below into its solution state? Solve this using the method and evaluation functions shown in the background section. Show your state search tree!
1 / 2 / 38 / 4
7 / 6 / 5
1 / 3
6 / 2 / 4
8 / 7 / 5
Q1 Answer (show your state search tree for the above starting state and goal state, you may draw this with pencil/paper and then scan or photo the image and paste it here):
Q2: On a dark, cold and stormy night four friends find themselves on one side of a bridge. There is only one lamp between them and because the bridge is so old, at most two of them can cross the bridge at once. Whenever anyone crosses the bridge—either alone or with a partner—the lamp must go with him.
One of the friends can cross the bridge in 15 minutes, the second in 10 minutes, the third in 2 minutes and the last in 1 minute. Find the minimum amount of time needed before they each reach the other side of the bridge.
Hint on a representation: Use a text description for each state; something like:
Starting side: Friend1, Friend2, Friend3, Friend4
Goal side: no one
Time so for: none
Your transformation function is crossing the bridge given the time and light restrictions noted. A state value would likely be the total time used so far, and an evaluation function would be to choose the next state to expand that has the minimal time. Note that from the beginning state, there are 6 possible child states. Solve this problem by creating the search tree similar to the one done for Q1, but with the new state representation. Draw entire search tree.
Q2 Answer (show your state search tree for the above starting state and goal, you may draw this with pencil/paper and then scan or photo the image and paste it here):
Q3: Challenge Question (not required, no credit):
Two boys with a small boat agree to help three soldiers cross a river without a bridge. The boat is so small it can support only one soldier or two boys. A soldier and a boy can't be in the boat at the same time for fear of sinking it. What is the minimum number of trips it will take to ferry all the soldiers across? (Adapted from Science News for Kids,
Part 2: Data Structures
(See the online tutorials for the background on data structures)
Q4:Show how a stack would appear after each of the following 16 operations:
push(t), push(s), push(y), pop(), push(g), push(u), push(o), pop(), pop(), pop(), push(o), pop(), pop(), push(i), pop(), pop()
Answer: (just show the sequence of characters on the stack with the right side being the top of the stack; I have filled in the answers for the first and second steps for you):
1: t
2: t s
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
Q5:Show how a queue would appear after each of the following operations:
add(a), add(p), add(p), remove(), add(l), remove(), remove(), add(e), remove(), remove() (node: add is the same as enqueue; remove is the same as dequeue).
Answer: (the head/front of the list should be to the left side, the tale/end of the list to the right side)
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
Part 3: Introduction to Programming (SNAP!)
Q6: This project will be split over the last 2 labs (Lab #8 & #9). The project is for you to create an animation, simulation, or game in SNAP! that somehow demonstrates or teaches any concept that we have learned in CS160 this term. You project does not need to be elaborate, as long as some concept is clearly demonstrated to the end user of your program. At minimum, your project should have some graphics, some animation or motion and some sound (you could even record your own voice!). As a model of what you might do, review any of the 50 flash animations and java applets that have been used to teach concepts in this class. You are welcome to simply re-implement any one of these if you wish.
The requirement for Lab #9 is to complete the project that you started in Lab #8 (the prototype of your project). TAKE SEVERAL SCREEN SHOTS (alt + print screen) of your final SNAP! project and paste it into your assignment document as your answer for Q6. Please try to show most of your scripts in your screen shots, and a couple showing the execution of your program.
TURN IN your document that answers the assignment questions, and also TURN in your SNAP! project file (the XML file). See the following description on using the XML export method of saving your project locally. This is the only method that can be used to export your project for you to submit it!
XML Export (from the SNAP! User Manual)
The second way to save a project on your computer requires two steps, but it doesn’t have the limitations of localstore. Projects saved in this second way are normal files on your computer and can be shared with friends, can be opened in any browser, and have no size limitation.
From the file menu, choose “Export project…” The entire Snap! window will disappear, replaced by a screenful of what looks like gibberish. Don’t panic! This is what’s supposed to happen. You are looking at your project, in a notation called XML. The main reason it looks like gibberish is that it includes an encoding of the pictures and other media in the project. If you look through the XML, the actual scripts of the project are pretty readable, although they don’t look like Snap! blocks. Snap! has opened a new browser tab for this XML text; the actual Snap! window is still there, hiding in its original tab.
But the point of this XML text isn’t for you to read. Once you’re looking at that tab, use your browser’s Save command (in its File menu, or usually with a shortcut of command-S (Mac) or control-S (everything else). You can choose a filename for it, and it’ll be saved in your usual Downloads folder. You can then close that tab and return to the Snap! tab.
Western Oregon University Page 1 of 4