### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# Intro Artificial Intelligence CS 580

Mason

GPA 3.66

### View Full Document

## 261

## 0

## Popular in Course

## Popular in ComputerScienence

This 21 page Class Notes was uploaded by Leland Swift on Monday September 28, 2015. The Class Notes belongs to CS 580 at George Mason University taught by Zoran Duric in Fall. Since its upload, it has received 261 views. For similar materials see /class/215120/cs-580-george-mason-university in ComputerScienence at George Mason University.

## Popular in ComputerScienence

## Reviews for Intro Artificial Intelligence

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 09/28/15

CS 580 Spring 2006 Dr Duric Final Review 1 Consider the following game tree MAXA A to 03 a Find the best move for the MAX player using the minimaX procedure b Perform a left to right alpha beta pruning on the tree lndicate where the cutoffs occur c Perform a right to left alpha beta pruning on the tree Discuss why different pruning occurs For each of the following pairs of atomic sentences7 give the most general uni er7 if it exists PABB PIy2 QCIiGmiBM QGIIiy OlderFathergy OldeTFatherIJohn KnowsFathergy Knowsxx Ancestorxy Ancestor fohnFather fohn 1pr SD The function consry denotes list formed by inserting the element x at the head of the list y We denote the empty list by Nil the list 2 by cons2Nil the list 12 by cons1cons27 Nil and so on The formula Membede is intended to mean that e is a member of the list 1 We have the following axioms 7 Vz7 y Memberm consm7 7 VmyzMembermy D Membermconszy U a T 00 Dr Prove Memberb consaconsb from these axioms by the method of resolution refu tation Somebody Dr Anybody and Dr following facts about them Nobody are computer scientists We know the 1 Dr Somebody is an associate professor 2 Dr Nobody is an assistant professor and has published papers with Dr Anybody 3 Dr Anybody is either an associate or an assistant professor but not both and has published papers with Dr Somebody Use resolution refutation to prove that an assistant professor has published papers with an associate professor that is prove Hz yAssistantz A Associatey A PPWz We are given the following paragraph Tony Mike and John belong to the Alpine Club Every member of the Alpine Club is either a skier or a mountain climber or both No mountain climber likes rain and all skiers like snow Mike dislikes whatever Tony likes and likes whatever Tony dislikes Tony dislikes rain and snow Represent this information by predicatecalculus sentences in such a way that you can rep resent the question ls there a member of the alpine club who is a skier but not a mountain climber77 as a predicatecalculus expression Use resolution refutation to answer it A simple version of the MM game is played as follows Two players alternate in removing stones from three piles initially containing one two and three stones respectively The player who picks up the last stone wins Each player can pick one or more stones from a single pile at least one stone has to be picked every time At every turn the players can pick from different piles Show by drawing the game tree which player can always win ls it necessary to generate the whole tree to nd a winning strategy Consider the following statements 1 Whoever can read is literate VmRm 2 Horses are not literate a 3 Some horses are intelligent A Use these statements to prove the following statement by resolution 4 Some who are intelligent cannot read Hzz A You are given the following table H 0 H H to Consider the sentence Heads 1 win tail you lose77 Outlook Temperature Humidity 76 Windy Class sunny warm lt 75 yes Play sunny hot gt 75 yes Don t Play sunny hot gt 75 no Don t Play sunny warm gt 75 no Don t Play sunny warm lt 75 no Play overcast warm gt 75 yes Play overcast hot gt 75 no Play overcast cool lt 75 yes Play overcast hot lt 75 no Play rain warm gt 75 yes Don t Play rain cool lt 75 yes Don t Play rain warm lt 75 no Play rain cool gt 75 no Play a Build a decision tree to distinguish the tow classes Use the information theory to decide which attribute should be used at the root of the decision tree 10p for this step b Indicate the 7Play7 concept represented by the tree We represent the statement that everything is representable in the predicate calculus as Vmrepresentspc General Problem Solver GPS is a system for automated problem solving We represent the statement that all problems representable in predicate calculus are solvable using GPS as Va problemm A representspc solvesgps Now using these two statements and the fact that the Traveling Salesperson Problem TSP is a problem problemtsp prove that GPS solves it Attempt to unify the following pairs of expressions Either show their most general uni ers or explain why they will not unify pXY and paZ pXX and pab ancestorXY and ancestorbillfatherbill ancestorXfatherX and ancestordavidgeorge a b c d VVVV We can represent this sentence plus associated domain knowledge in the propositional logic using the following proper axioms where Heads Tails WinMe and Lose You are propositional variables Heads WinMe Tall LoseYou Heads Tail 3 LoseYou WinMe a Determine if it is possible to prove WinMe using the rule of inference modus ponens and these four axioms b Convert each of the four axioms to a disjunction of literals c For each of the resulting disjunctions specify if it is a Horn clause H to H 03 H F H 01 d Determine if it is possible to prove WinMe using the resolution rule of inference and the four axioms written as disjunctions of literals We have de ned four different binary logical connectives A V a a Are there any others that might be useful b How many binary connnectives can there be c Why are some of them not very useful Consider the following problem The rules in the National Zoo forbid visitors to feed animals A prairie dog an animal has some candy and all of its candy was given to it by BB who is a Zoo visitor a Represent these facts as rst order logic clauses b Use backward chaining to prove that BB broke Zoo rules c Use forward chaining to prove that BB broke Zoo rules Build a decision tree to distinguish two classes reads7 and 7skips from the following table Example Action Author Thread Length e1 skips known new long e2 skips known followup long e3 skips unknown followup long e4 reads known followup short e5 reads unknown new short e6 reads known new short e7 skips unknown new long e8 skips unknown followup short Use the information theory to decide which attribute to use at each non terminal node of the tree Sam Clyde and Oscar are rabbits We know the following facts about them 1 Sam is pink 2 Clyde is gray and likes Oscar 3 Oscar is either pink or gray but not both and likes Sam Use resolution refutation to prove that a gray rabbit likes a pink rabbit that is prove 3m yGraym A A Likesm The function consry denotes list formed by inserting the element x at the head of the list y We denote the empty list by ml the list 2 by cons2nil the list 12 by cons1cons2nil and so on The formula Lastle is intended to mean that e is the last element of the list 1 We have the following axioms 7 VuLastconsu nilu 7 VmyzLa3tyz D Lastconszyz 1 Prove the following theorem from these axioms by the method of resolution refutation 3ULa8tcons2 cons1nll 11 2 Use answer extraction to nd 1 the last element of the list 2 1 17 The set of inputs 1 2 de ne a 2 dimensional space A boolean function de ning a concept is said to be linearly separable if there exists a hyperplane line dividing the space into inputs for which the function produces a 1 and inputs for which the function produces a O a Which of these four boolean functions are linearly separable or and IOT equal Justify your answer b What needs to be done to make concepts which are not linearly separable learnable by the perceptron learning rule lllustrate your answer using a boolean function that is not linearly separable 18 A simple version of a Kayles game77 is played as follows Two players have in front of them a single contiguous sequence of objects say 5 pennies which are placed next to each other so that the rst penny touches the second the second touches the third the third touches the fourth and the fourth touches the fth penny The rst player removes 1 or 2 pennies whose sides that are touching for example the rst player can remove any single penny or pennies 1 and 2 or pennies 2 and 3 or pennies 3 and 4 or pennies 4 and 5 Each player alternatively thereafter removes 1 penny or 2 pennies whose sides are touching Note If the rst player removes penny 2 the pennies 1 and 3 will have a gap between them and cannot be removed at the same time The last player to pick a penny or two loses Show by drawing a game tree whether any of the players can always win You can ignore symmetries and obvious losing plays if there is a winning play available such as picking both pennies when there are 2 pennies left 19 Consider a vocabulary with only four propositions A B C and D How many models are there for the following sentences a AABVBAC b AVB c A gtB gtC Hint In each sentence all four propositions have to be considered 20 Build a decision tree to distinguish two classes 77 and 77 from the following table food medium type class description herbivore land harmless mammal deer e1 carnivore land harmful mammal 7 lion c1 omnivorous water harmless sh 1 gold sh e2 herbivore amphibious harmless amphibian 7 frog c2 omnivorous air harmless bird 7 parrot c3 carnivore land harmful reptile cobra e3 carnivore land harmless reptile 7 lizard c4 omnivorous land moody mammal bear e4 2 H 2 to Use information theory to decide which attribute should be used at each nonleaf node of your decision tree A simple version of the nz39m game is played as follows Two players alternate in removing stones from two piles initially containing several stones each The player who picks up the last stone wins At any given turn a player can pick one or more stones from a single pile at least one stone has to be picked every time a Show7 by drawing a game tree7 which player can always win if the piles have two and two stones b Show7 by drawing a game tree7 which player can always win if the piles have two and three stones You can use your result from a c What can you say about a game in which the piles have m gt 0 and n gt 0 stones You are building a decision tree which tells us whether we should go to a restaurant based on various attributes how many patrons it has7 whether or not the food is cheap7 and what type of food is served The information is Example patrons cheap type go 1 some yes french yes 2 empty yes thai no 3 some no burger yes 4 some yes thai yes 5 full no french no 6 empty yes italian yes a Show the tree after asking attribute questions in this order type7 cheap7 patrons b Express the concept represented by the decision tree as a rst order logical expression c What is the rst attribute question you should ask and why Show your work A simple version of the nz39m game is played as follows Two players alternate in removing stones from three piles initially containing two stones each The player who picks up the last stone wins Each player can pick one or more stones from a single pile at least one stone has to be picked every time At any turn the player can pick from any one pile Show7 by drawing the game tree7 whether a player can always win7 and if so which one ls it necessary to generate the whole tree to nd a winning strategy 24 A typical belief network with conditional probabilities is given in the following gure Cloudy C PSlC C PRlC T 10 Sprinkler Rain T 80 F 50 F 20 Wet Grass S R PWlSR T T 99 T F 90 F T 90 F F 01 The letters CRS and Wstand for Cloudy Ram Sprinkler and Wet Grass respectively All variables nodes are Boolean so the probability of say A in any row of its table is 17PA a Assuming that the nodes are introduced in the following order Wet Grass Sprinkler Ram and Cloudy construct a corresponding belief network Show which probabilities need to be speci ed b Compute probabilities PW and PSlW 25 A typical belief network with conditional probabilities is given in the following gure Burglary lim T 70 F 01 The letters B EAJ and Mstand for Burglary Earthquake Alarm JohnC alls and MaryC alls respectively All variables nodes are Boolean so the probability of say A in any row of its table is 17 PA CS 580 Spring 2006 Dr Duric Final Review 1 Consider the following game tree MAXA A to 03 a Find the best move for the MAX player using the minimaX procedure b Perform a left to right alpha beta pruning on the tree lndicate where the cutoffs occur c Perform a right to left alpha beta pruning on the tree Discuss why different pruning occurs For each of the following pairs of atomic sentences7 give the most general uni er7 if it exists PABB PIy2 QCIiGmiBM QGIIiy OlderFathergy OldeTFatherIJohn KnowsFathergy Knowsxx Ancestorxy Ancestor fohnFather fohn 1pr SD The function consry denotes list formed by inserting the element x at the head of the list y We denote the empty list by Nil the list 2 by cons2Nil the list 12 by cons1cons27 Nil and so on The formula Membede is intended to mean that e is a member of the list 1 We have the following axioms 7 Vz7 y Memberm consm7 7 VmyzMembermy D Membermconszy U a T 00 Dr Prove Memberb consaconsb from these axioms by the method of resolution refu tation Somebody Dr Anybody and Dr following facts about them Nobody are computer scientists We know the 1 Dr Somebody is an associate professor 2 Dr Nobody is an assistant professor and has published papers with Dr Anybody 3 Dr Anybody is either an associate or an assistant professor but not both and has published papers with Dr Somebody Use resolution refutation to prove that an assistant professor has published papers with an associate professor that is prove Hz yAssistantz A Associatey A PPWz We are given the following paragraph Tony Mike and John belong to the Alpine Club Every member of the Alpine Club is either a skier or a mountain climber or both No mountain climber likes rain and all skiers like snow Mike dislikes whatever Tony likes and likes whatever Tony dislikes Tony dislikes rain and snow Represent this information by predicatecalculus sentences in such a way that you can rep resent the question ls there a member of the alpine club who is a skier but not a mountain climber77 as a predicatecalculus expression Use resolution refutation to answer it A simple version of the MM game is played as follows Two players alternate in removing stones from three piles initially containing one two and three stones respectively The player who picks up the last stone wins Each player can pick one or more stones from a single pile at least one stone has to be picked every time At every turn the players can pick from different piles Show by drawing the game tree which player can always win ls it necessary to generate the whole tree to nd a winning strategy Consider the following statements 1 Whoever can read is literate VmRm 2 Horses are not literate a 3 Some horses are intelligent A Use these statements to prove the following statement by resolution 4 Some who are intelligent cannot read Hzz A You are given the following table H 0 H H to Consider the sentence Heads 1 win tail you lose77 Outlook Temperature Humidity 76 Windy Class sunny warm lt 75 yes Play sunny hot gt 75 yes Don t Play sunny hot gt 75 no Don t Play sunny warm gt 75 no Don t Play sunny warm lt 75 no Play overcast warm gt 75 yes Play overcast hot gt 75 no Play overcast cool lt 75 yes Play overcast hot lt 75 no Play rain warm gt 75 yes Don t Play rain cool lt 75 yes Don t Play rain warm lt 75 no Play rain cool gt 75 no Play a Build a decision tree to distinguish the tow classes Use the information theory to decide which attribute should be used at the root of the decision tree 10p for this step b Indicate the 7Play7 concept represented by the tree We represent the statement that everything is representable in the predicate calculus as Vmrepresentspc General Problem Solver GPS is a system for automated problem solving We represent the statement that all problems representable in predicate calculus are solvable using GPS as Va problemm A representspc solvesgps Now using these two statements and the fact that the Traveling Salesperson Problem TSP is a problem problemtsp prove that GPS solves it Attempt to unify the following pairs of expressions Either show their most general uni ers or explain why they will not unify pXY and paZ pXX and pab ancestorXY and ancestorbillfatherbill ancestorXfatherX and ancestordavidgeorge a b c d VVVV We can represent this sentence plus associated domain knowledge in the propositional logic using the following proper axioms where Heads Tails WinMe and Lose You are propositional variables Heads WinMe Tall LoseYou Heads Tail 3 LoseYou WinMe a Determine if it is possible to prove WinMe using the rule of inference modus ponens and these four axioms b Convert each of the four axioms to a disjunction of literals c For each of the resulting disjunctions specify if it is a Horn clause H to H 03 H F H 01 d Determine if it is possible to prove WinMe using the resolution rule of inference and the four axioms written as disjunctions of literals We have de ned four different binary logical connectives A V a a Are there any others that might be useful b How many binary connnectives can there be c Why are some of them not very useful Consider the following problem The rules in the National Zoo forbid visitors to feed animals A prairie dog an animal has some candy and all of its candy was given to it by BB who is a Zoo visitor a Represent these facts as rst order logic clauses b Use backward chaining to prove that BB broke Zoo rules c Use forward chaining to prove that BB broke Zoo rules Build a decision tree to distinguish two classes reads7 and 7skips from the following table Example Action Author Thread Length e1 skips known new long e2 skips known followup long e3 skips unknown followup long e4 reads known followup short e5 reads unknown new short e6 reads known new short e7 skips unknown new long e8 skips unknown followup short Use the information theory to decide which attribute to use at each non terminal node of the tree Sam Clyde and Oscar are rabbits We know the following facts about them 1 Sam is pink 2 Clyde is gray and likes Oscar 3 Oscar is either pink or gray but not both and likes Sam Use resolution refutation to prove that a gray rabbit likes a pink rabbit that is prove 3m yGraym A A Likesm The function consry denotes list formed by inserting the element x at the head of the list y We denote the empty list by ml the list 2 by cons2nil the list 12 by cons1cons2nil and so on The formula Lastle is intended to mean that e is the last element of the list 1 We have the following axioms 7 VuLastconsu nilu 7 VmyzLa3tyz D Lastconszyz 1 Prove the following theorem from these axioms by the method of resolution refutation 3ULa8tcons2 cons1nll 11 2 Use answer extraction to nd 1 the last element of the list 2 1 17 The set of inputs 1 2 de ne a 2 dimensional space A boolean function de ning a concept is said to be linearly separable if there exists a hyperplane line dividing the space into inputs for which the function produces a 1 and inputs for which the function produces a O a Which of these four boolean functions are linearly separable or and IOT equal Justify your answer b What needs to be done to make concepts which are not linearly separable learnable by the perceptron learning rule lllustrate your answer using a boolean function that is not linearly separable 18 A simple version of a Kayles game77 is played as follows Two players have in front of them a single contiguous sequence of objects say 5 pennies which are placed next to each other so that the rst penny touches the second the second touches the third the third touches the fourth and the fourth touches the fth penny The rst player removes 1 or 2 pennies whose sides that are touching for example the rst player can remove any single penny or pennies 1 and 2 or pennies 2 and 3 or pennies 3 and 4 or pennies 4 and 5 Each player alternatively thereafter removes 1 penny or 2 pennies whose sides are touching Note If the rst player removes penny 2 the pennies 1 and 3 will have a gap between them and cannot be removed at the same time The last player to pick a penny or two loses Show by drawing a game tree whether any of the players can always win You can ignore symmetries and obvious losing plays if there is a winning play available such as picking both pennies when there are 2 pennies left 19 Consider a vocabulary with only four propositions A B C and D How many models are there for the following sentences a AABVBAC b AVB c A gtB gtC Hint In each sentence all four propositions have to be considered 20 Build a decision tree to distinguish two classes 77 and 77 from the following table food medium type class description herbivore land harmless mammal deer e1 carnivore land harmful mammal 7 lion c1 omnivorous water harmless sh 1 gold sh e2 herbivore amphibious harmless amphibian 7 frog c2 omnivorous air harmless bird 7 parrot c3 carnivore land harmful reptile cobra e3 carnivore land harmless reptile 7 lizard c4 omnivorous land moody mammal bear e4 2 H 2 to Use information theory to decide which attribute should be used at each nonleaf node of your decision tree A simple version of the nz39m game is played as follows Two players alternate in removing stones from two piles initially containing several stones each The player who picks up the last stone wins At any given turn a player can pick one or more stones from a single pile at least one stone has to be picked every time a Show7 by drawing a game tree7 which player can always win if the piles have two and two stones b Show7 by drawing a game tree7 which player can always win if the piles have two and three stones You can use your result from a c What can you say about a game in which the piles have m gt 0 and n gt 0 stones You are building a decision tree which tells us whether we should go to a restaurant based on various attributes how many patrons it has7 whether or not the food is cheap7 and what type of food is served The information is Example patrons cheap type go 1 some yes french yes 2 empty yes thai no 3 some no burger yes 4 some yes thai yes 5 full no french no 6 empty yes italian yes a Show the tree after asking attribute questions in this order type7 cheap7 patrons b Express the concept represented by the decision tree as a rst order logical expression c What is the rst attribute question you should ask and why Show your work A simple version of the nz39m game is played as follows Two players alternate in removing stones from three piles initially containing two stones each The player who picks up the last stone wins Each player can pick one or more stones from a single pile at least one stone has to be picked every time At any turn the player can pick from any one pile Show7 by drawing the game tree7 whether a player can always win7 and if so which one ls it necessary to generate the whole tree to nd a winning strategy 24 A typical belief network with conditional probabilities is given in the following gure Cloudy C PSlC C PRlC T 10 Sprinkler Rain T 80 F 50 F 20 Wet Grass S R PWlSR T T 99 T F 90 F T 90 F F 01 The letters CRS and Wstand for Cloudy Ram Sprinkler and Wet Grass respectively All variables nodes are Boolean so the probability of say A in any row of its table is 17PA a Assuming that the nodes are introduced in the following order Wet Grass Sprinkler Ram and Cloudy construct a corresponding belief network Show which probabilities need to be speci ed b Compute probabilities PW and PSlW 25 A typical belief network with conditional probabilities is given in the following gure Burglary lim T 70 F 01 The letters B EAJ and Mstand for Burglary Earthquake Alarm JohnC alls and MaryC alls respectively All variables nodes are Boolean so the probability of say A in any row of its table is 17 PA CS 580 Spring 2006 Dr Duric Midterm Review 1 Answer brie y a What is the major difference between blind and heuristic search methods b Enumerate and de ne three major blind search methods c How is the hill climbing method different from the best rst search method For what classes of problems are the hill climbing and the best rst search methods equivalent 2 List the order in which nodes are visited in the tree below for each of the following search strategies choosing leftmost branch in all cases a Depth rst search b Depth rst iterative deepening search increasing the depth by 1 each iteration c Breadth rst search A 3 A boy brings a basket of cabbage7 a wolf7 and a goat to a river There is a small boat on their river bank that they can use to cross to the other side However7 the boat is so small that it can hold only the boy and the cabbage or the boy and one of the animals The boy cannot leave the goat alone with either the cabbage or the wolf How should the boy use the boat to take the cabbage and the animals to the other side of the river in such a way that the number of river crossings is minimal and that the goat is never left alone with either the wolf or the cabbage on any side of the river Use iterative deepening search to solve this problem q In the water jug puzzle we are given a 4 liter jug7 and a 7 liter jug lnitially7 both jugs are empty Either jug can be lled with water from a tap7 and we can discard water from either jug down a drain Water may be poured from one jug into the other There is no additional measuring device We want to nd a set of operations that will leave precisely z liters of water in either one of the jugs i Set up a statespace search formulation of the water jug puzzle U a 7 a Given the initial iconic state description as a data structure b Give a goal condition on states as some test on data structures c Name the operators on states and give precise descriptions of what each operator does to a state description ii Find whether the goals z 1 2 3 4 5 6 7 can be accomplished in 8 or fewer steps Hint Use breadth rst search A simple sliding tile puzzle consists of 3 numbered tiles and an empty space The puzzle has two legal moves with associate costs A tile may move into an adjacent empty location This has a cost of 1 ii A tile can move over one other tile into the empty position This has a cost of 2 The start and goal positions are given below Set up a state space search formulation for this puzzle 93 V Specify the form of state descriptions the starting state and the goal state for this problem 7 V Name the operators on states and describe what each operator does to a state description Write a lisp function that takes a state as input and outputs a list of states that can be reached from that state Include the parent and the cost elds Propose a heuristic function Ii for solving this problem CLO V Use the A algorithm to nd a solution path using your heuristic function D ls your solution path optimal Give a formal argument The game mm is played as follows Two players alternate in removing one two or three pennies from a stack initially containing ve pennies The player who picks up the last penny loses Show by drawing the game tree that the player who has the second move can always win Can you think of a simple characterization of the winning strategy ls it necessary to generate the whole tree to nd a winning strategy A partial search tree for a two player game is given below MAX 23590742156 a Find the best move for the MAX player using the minimax procedure b Using alpha beta pruning show which parts of the tree do not need to be searched lndicate where the cutoffs occur 8 A simple version of the MM game is played as follows Two players alternate in removing H H H H to stones from three piles initially containing one one and ve stones respectively The player who picks up the last stone wins Each player can pick one or more stones from a single pile at least one stone has to be picked every time At every turn the players can pick from different piles a Show by drawing a game tree which player can always win You may use either DFS or BFS method to generate nodes b ls it necessary to generate the whole tree to nd a winning strategy Explain why or why not ls it possible to use the alpha beta pruning on this game tree Write a recursive lisp function that takes a list as an argument and returns the number of atoms on any level of the list For instance list A B C D E contains six atoms ABC DE and NIL Write a lisp function shuffle that takes a list of 52 different symbols and returns a list in which the original 52 elements are mixed in random order Hint Use functions random and remove Write a lisp function last5 that takes a list A as its argument and returns a list B consisting of the last ve elements of A You are not allowed to use the built in function last last5 A B 0 should return A B C last5 A B C D EF G should return D E F G H A simple version of a Grundy s game77 is played as follows Two players have in front of them a single pile of objects say a stack of 7 pennies The rst player divides the original stack into two stacks that must be unequal Each player alternatively thereafter does the same to some single stack when it is his turn to play The game proceeds until each stack has either just one penny or twoiat which point continuation becomes impossible The player who rst cannot play is the loser Show by drawing a game tree whether any of the players can always win The 8 puzzle consists of eight numbered movable tiles set in a 3x3 frame One cell of the frame is always empty thus making it possible to move and adjacent numbered tile into the empty cellior we could say to move the empty cell Two con gurations of tiles are given Consider the problem of changing the initial con guration into the goal con guration 2 4 3 l 2 3 l 6 8 4 8 5 7 5 6 7 start goal Set up a state space search formulation for this puzzle a Specify the form of state descriptions the starting state and the goal state for this problem 14 H a b c d e Name the operators on states and describe what each operator does to a state description Propose a heuristic function I for solving this problem Use the 14 algorithm to nd a solution path ls your solution path optimal Give a formal argument Write a recursive function ip that takes a binary tree as input and returns a binary tree that it is its mirror image You can represent binary trees as nested structures Nested recursive representation ltr00tgt ltleft subtreegt ltright subtreegt Examples ip 71 2 3 should return 1 3 2 Hip 71 2 3 4 should return 1 2 4 3 Hip 71 2 3 4 5 10 11 12 6 7 should eturn 1 6 7 8 0 0 2 10 12 11 3 5 4 a Write a lisp function funny rst that takes a list of at lists and returns a new list composed of the rst elements of the original at lists b Write a lisp function funnyJust that takes a list of at lists as its argument and returns a new list composed of the last elements of the original at lists c Write a lisp function funnylen that takes a list of at lists as its argument and returns the sum of the lengths of the nested lists d Write a lisp function funnyjum that takes a list of at lists of numbers and returns the sum of the elements of the nested lists Examples funny rst 7A B C D E F G funnyJast 7A B C D E F G funnyJen 7A B C D E F G funnysum 71 2 3 4 5 10 20 30 should return A C D F should return B C E H should return 8 should return 75 A simple sliding tile puzzle consists of 4 numbered tiles and an empty space The puzzle has two legal moves with associate costs A tile may move into an adjacent empty location This has a cost of 1 ii A tile can move over one other tile into the empty position This has a cost of 2 The start and goal positions are given below Set up a state space search formulation for this puzzle a Specify the form of state descriptions7 the starting state7 and the goal state for this problem b Name the operators on states and describe what each operator does to a state description c Propose a heuristic function Ii for solving this problem d Use the A algorithm to nd a solution path e ls your solution path optimal Give a formal argument 17 The sliding tile puzzle consists of three black tiles7 three white tiles and an empty space in the con guration shown below HEE The puzzle has two legal moves with associate costs A tile may move into an adjacent empty location This has a cost of 1 A tile can move over one or two other tiles into the empty position This has a cost equal to the number of tiles jumped over The goal is to have all the white tiles to the left of all the black tiles with the blank in the middle a Choose a representation for this problem so that A algorithm can be applied to nd a solution b Propose two heuristics for solving this problem c Show all states that can be reached from the start and compute their 9 and h values for one of your heuristics state clearly which one you are using Mark the state that would be expanded next by A algorithm 7 you do not need to expand that state The 8 puzzle consists of eight numbered7 movable tiles set in a 3x3 frame One cell of the frame is always empty thus making it possible to move an adjacent numbered tile into the empty cellior7 we could say7 to move the empty cell Two con gurations of tiles are given Consider the problem of changing the start con guration into the goal con guration 5 6 7 5 7 start goal Set up a state space search formulation for this puzzle a Specify the form of state descriptions7 the starting state7 and the goal state for this problem b Name the operators on states and describe what each operator does to a state description Propose a heuristic function Ii for solving this problem d Use the A algorithm to nd a solution path e O ls your solution path optimal Give a formal argument 19 A simple version of a Kayles game77 is played as follows Two players have in front of them a single contiguous sequence of objects say 5 pennies which are placed next to each other so that the rst penny touches the second the second touches the third the third touches the fourth and the fourth touches the fth penny The rst player removes 1 or 2 pennies whose sides that are touching for example the rst player can remove any single penny or pennies 1 and 2 or pennies 2 and 3 or pennies 3 and 4 or pennies 4 and 5 Each player alternatively thereafter removes 1 penny or 2 pennies whose sides are touching Note If the rst player removes penny 2 the pennies 1 and 3 will have a gap between them and cannot be removed at the same time The last player to pick a penny or two loses Show by drawing a game tree whether any of the players can always win You can ignore symmetries and obvious losing plays if there is a winning play available such as picking both pennies when there are 2 pennies left 20 a Write a non recursive function that takes a list as its argument and reverses it Hint use the dolist statement b Write a recursive function that takes a list as its argument and reverses it Examples reverse 7A B C D E should return F D E C B A reverse 71 2 3 4 5 should return 4 5 6 3 2 1 21 What do these functions do defun xx lst if atom lst 0 if null lst 0 if member first lst rest lst 1 XX rest lSt xx rest lst defun yy lst if atom lst yy list lst mapcar lambda x if atom x list t x nil lst defun dd lst cond atom lst lst atom first lst cons first lst dd rest lst t append dd first lst dd rest lst defun zz lst cond null lst nil numberp first lst zz rest lst t append list first lst zz rest lst list first lst 22 Consider the following game tree a Find the best move for the MAX player using the minimax procedure b Perform a left to right alpha beta pruning on the tree lndicate where the cutoffs occur 23 c Perform a right to left alpha beta pruning on the tree Discuss why different pruning occurs In the water jug puzzle we are given a 2 liter jug and a 5 liter jug lnitially both jugs are empty Either jug can be lled with water from a tap and we can discard water from either jug down a drain Water may be poured from one jug into the other There is no additional measuring device We want to nd a set of operations that will leave precisely z liters of water in either one of the jugs A Set up a statespace search formulation of the water jug puzzle Give the initial state description as a data structure De ne the goal predicate as a function of a state Name the operators on states and give precise descriptions of what each operator does to a state E Find whether the goals z E 1 2 3 4 5 can be accomplished in 4 or fewer steps A simple version of the MM game is played as follows Two players alternate in removing stones from three piles initially containing two stones each The player who picks up the last stone wins Each player can pick one or more stones from a single pile at least one stone has to be picked every time At any turn the player can pick from any one pile Show by drawing the game tree whether a player can always win and if so which one ls it necessary to generate the whole tree to nd a winning strategy Write a lisp function that takes a at list as an argument and returns a list whose elements are those elements of the original list that are not numbers Write a lisp function that takes a at list as an argument and returns a sum of the numbers in the original list Your function should not add the non number elements of the original list Write a lisp function shu le that takes a list of 32 different symbols and returns a list in which the original 32 elements are mixed in random order Hint Use functions random and remove

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "I made $350 in just two days after posting my first study guide."

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.