CS 6601 Artificial Intelligence Fall Semester 2022 Final Examination Paper
Duration of Exam: 5 December 2022, 8:00 AM (EDT) – 12 December 2022, 8:00 AM (EDT)
Weight: 20% No. pages: 60 No. Questions: 10 Total marks: 103
Instructions:
• Before solving the exam, you should read the Ed post titled “Final Exam Next Week”.
• You should fill out this PDF and submit it on BOTH Gradescope and Canvas. We reserve the right to deduct points if you don’t submit on both platforms.
• You have an unlimited number of submissions until the deadline. You can either type directly into the PDF or you can print, hand-write, and scan your solutions. If you decide to type into the PDF, we strongly recommend using Adobe Acrobat Reader DC. If you are on MacOS, please do not use Preview, as we have seen major issues with it in the past. Other programs may not save your answers. Thus, always make sure to keep a backup of your answers.
• You should submit only a single PDF. Also, make sure your typed answers appear clearly in the Gradescope Preview. After each question, a blank page is provided if you wish to highlight some of your calculations. However, you should not expect any points to be awarded for your calculations (only your final answers will be considered). The TAs reserve the right to assign partial credits based on your calculations. Make sure to submit ALL the pages of the exam, not only the completed ones.
• You must fill out the checklist at the end of the exam. The exam may not be graded if it is left blank.
• Theexamisopen-book,open-note,andopenvideolectures,withnotimelimitasidefromtheduration of the exam. No internet use is allowed, except for e-text versions of the textbook, this semester’s CS6601 course materials, Ed, and any links provided in the PDF itself. No resources outside this semester’s 6601 class should be used. Do not discuss the exam on Ed, Slack, or any other platform. In particular, do not post publicly about the exam. If there is a question for the teaching staff, please make it private on Ed and tag it as Final Exam with the question number in the subject line (for example, a question on Search would be “Final Exam #2”). Please make different posts for different questions.
• Global Rounding Rule: Please round all your final answers to 6 decimal places. Don’t round intermediate results. You can use round(answer, 6) function in Python for help. You may not receive full credit if your answers are not given to the specified precision.
• Points breakdown is provided below.
Question No.
Problem 1: Game Playing [7 points]
Harry is a struggling sophomore and loves playing games. Often, this habit affects his progress in college as he is unable to turn in assignments on time as he is caught up in completing game missions instead.
This semester Harry took a CS course called Game Playing and Artificial Intelligence where he is learn- ing about how two player and zero-sum games use adversarial search to apply AI and how modern algorithms and machines use these algorithms in everyday applications. Surprisingly, Harry loves this course and has decided to focus on his studies this semester but is unable to solve and understand some questions about the concept of Iterative Deepening. Therefore, he needs a peer to explain to him and solve such questions.
Help Harry gain interest in studies and his potential to be a shining student again by solving the following questions.
(a) (1.5 points) Which of the following is (are) the best ordering of the nodes A, B, C, and D (best ordering is the ordering that produces the most pruning) for alpha-beta pruning evaluation up to depth 2 with Iterative Deepening in an attempt to improve the effectiveness of alpha-beta pruning when running up to depth 3 (see Figure 1). Assume that the procedure uses the information it has acquired up to a given depth to try to improve the order of evaluations later. The static values for nodes A, B, C, and D are given with the definition of S and the depths for the tree are given with definition of D.
ABCD CDBA DCAB CDAB
Figure 1: Game Tree
(b) (1.5 points) Which of the following is (are) the best ordering of the nodes A, B, C, and D (best ordering is the ordering that produces the most pruning) for alpha-beta pruning evaluation up to depth 2 with Iterative Deepening in an attempt to improve the effectiveness of alpha-beta pruning when running up to depth 3 (see Figure 2). Again, assume the procedure uses the information it has acquired up to a given depth to try to improve the order of evaluations later. The static values for nodes A, B, C, and D are given with the definition of S and the depths for the tree are given with the definition of D.
ABCD CDBA BADC CDAB
Figure 2: Game Tree
(c) (1.5 points) Solve the given game tree in Figure 3 using minimax:
Figure 3: Game Tree Enter the final propagated value at the top:
Type Your Answer Here:
Enter the number of leaf nodes pruned if alpha-beta pruning is applied from left to right to solve
the game tree in Figure 3 (we are only counting leaf (terminal) nodes and not branches) Type Your Answer Here:
(d) (2.5 points) For Figure 1 and Figure 2, assume that we run the alpha-beta pruning to depth 3 and ignore the static values assigned at depth 2 previously used for iterative deepening.
How many more leaf nodes (compared to without reordering and using the left-to-right evalua- tion rule) will be pruned if the correct reordering (from the answer to question (a)) at depth 2 is applied (see Figure 1 and ignore the static values assigned at depth 2 previously used for iterative deepening.)?
Type Your Answer Here:
How many more leaf nodes (compared to without reordering and using the left-to-right evaluation rule) will be pruned if the correct reordering (from the answer to question (b)) at depth 2 is ap- plied (see Figure 2 and ignore the static values assigned at depth 2 previously used for iterative deepening.)?
Type Your Answer Here:
You can add your notes on this page (if any)
Problem 2: Search [5 points] Part 1:
It is 10-28-22, and you are eager to recover your own password to treasurydirect.gov, so you could purchase and secure 9.62% annual interest of Series I bonds for the next six months. You remember that the password is 7 to 13 characters long, the first 7 characters are Now, it is time to figure out the rest of the password by formulating a search problem:
1. The password starts with
2. The rest of the password will only contain characters “X”, “Y” or “Z”.
3. All ties are broken alphabetically. For example, if there is a tie, expand “X” first, then “Y”, and then “Z”.
4. The password will be expanded by appending one node (“X”, “Y”, or “Z”) at a time like what you have done in the first assignment.
5. The goal is to find the correct password among the six passwords you had written down before forgetting: and
6. Since you don’t want to test all these passwords and get locked out from your account, you will try to repeat the thinking process of how the password was selected.
(a) (0.5 points) You vaguely remember that you have picked the password that returned first when using Breadth First Search (BFS), which one of the following is that password?
(b) (0.5 points) You tried that password and it didn’t work, now you wonder whether the correct pass- word is the one returned first by iterative deepening Depth First Search (ID-DFS), which one of the following could be that password?
(c) (0.5 points) Apparently, that is not the right password, so maybe the one you selected is the one returned first by Depth First Search (DFS). If so, which one of the following could be that password?
(d) (0.5 points) Unfortunately, that password didn’t work as well. Now you know you must have used Uniform Cost Search (UCS) when choosing the password. Since you like simple things, you must have set the cost of X, Y, and Z to 1, 2, and 3 respectively. Since you like to make simple things complicated, you must have chosen the Last password returned by UCS, which one could be that password?
Consider a graph search problem where:
1. There is only one goal node.
2. Cost function cost (m, n) equals the cost from node m to node n, all cost (m, n) > 0. 3. Ties will be broken based on alphabetical order.
(e) (1 point) Now, you want to implement a new cost function cost_new(m, n), such that UCS based on this new cost function will always expand the same nodes in the same order as performing DFS on the same graph. Mark all the possible cost_new(m, n) below:
cost_new(m, n) = 1
cost_new(m, n) = α, α > 0
cost_new(m, n) = −1
cost_new(m, n) = α, α < 0
cost_new(m, n) = α * cost(m, n) + β , α > 0, β > 0 cost_new(m, n) = α * cost(m, n), α > 0 cost_new(m, n) = α * cost(m, n), α < 0
none exists
(f) (1 point) Now, you want to implement a new cost function cost_new(m, n), such that UCS based on this new cost function will always expand the same nodes in the same order as BFS. Mark all the possible cost_new(m, n) below:
cost_new(m, n) = 1
cost_new(m, n) = α, α > 0
cost_new(m, n) = −1
cost_new(m, n) = α, α < 0
cost_new(m, n) = α * cost(m, n) + β , α > 0, β > 0 cost_new(m, n) = α * cost(m, n), α > 0 cost_new(m, n) = α * cost(m, n), α < 0
none exists
(g) (1 point) Now, you want to implement a new cost function cost_new(m, n), such that UCS based on this new cost function will always expand the same nodes in the same order as UCS using the previous cost(m,n) as cost function. Mark all the possible cost_new(m, n) below:
cost_new(m, n) = 1
cost_new(m, n) = α, α > 0
cost_new(m, n) = −1
cost_new(m, n) = α, α < 0
cost_new(m, n) = α * cost(m, n) + β , α > 0, β > 0 cost_new(m, n) = α * cost(m, n), α > 0 cost_new(m, n) = α * cost(m, n), α < 0
none exists
You can add your notes on this page (if any)
Programming Help
Problem 3: Optimization Algorithms [6 points]
In this problem, we try to solve the minimum vertex cover problem using simulated annealing. The minimum vertex cover problem can be formulated as follows: Let G be an undirected graph with a set of vertices V and an edge set E. Every edge in E is denoted as (u, v), where u and v are vertices in the set V. A vertex cover is a set of vertices S such that the following property holds:
(1) For all (u,v) in E, either u or v (or both) are in S.
To find the minimum vertex cover, we want to find the smallest set S such that (1) holds. We refer
to (1) as the invariant property. You’ll see why as we describe the simulated annealing algorithm.
For our graph G, let the set of vertices V = {a,b,c,d,e, f,g} and the edge set be E = {(a,b),(a,c),(a,d),(a, f),(b,e),(b,g),(c,b),(c, f),(c,e),(d,e),(d,g),(e,g)}. A picture of G is shown in Figure 4:
Figure 4: Graph G
We perform simulated annealing as follows.
State Space: Our state space consists of all possible vertex covers for the graph G.
Transitions: When transitioning from one state to another (say from S to T ), we randomly pick a vertex v from the graph G. If v is in S , let T = S \ v (S \ v means remove v from S ). If T is a valid vertex cover, we keep T since we have now found a smaller-sized vertex cover. If T is invalid, we discard the change and keep S . If v is not in S , let T = S ∪ v (S ∪ v means include v in S ). We accept T with probability p = e(f(S)−f(T))/K (e is the exponential equation), where S,T ⊂ V (S and T are subsets of V) and K is the temperature. Define f as follows:
f(S) = deg(v) v∈S
where deg(v) represents the degree of a vertex v. The degree of a vertex is the number of edges connected to that vertex.
(a) (1 point) As a warm-up question, compute f (S ) for S = {a, c, d, e, g} Type Your Answer Here:
程序代写 CS代考 加QQ: 749389476
(b) (1 point) Now, given the starting state S = {b, c, d, f , e}, compute the probability of removing c from S for K = 8.54. If you reject or accept the change with certainty, write 0 or 1 respectively.
Type Your Answer Here:
(c) (3 points) Fill out the following table shown in Figure 5 starting from state S = {b, c, d, f , g}. Every time you successfully add a node to the vertex cover, reduce the temperature, K by a factor of 0.5 (so that Knext = 0.5 ∗ Kcurrent). Begin with K = 7.45. For any add transitions, if the Random Number is less than the acceptance probability you compute, accept the new state. Otherwise, reject it. Write the new state produced by applying the transition on the next row (you don’t need to do this for the last row). Finally, write down the acceptance probability for each transition. If you reject or accept a transition with certainty, write 0 or 1 respectively.
Figure 5: Table
Enter the value of A1 here: Enter the value of A3 here: Enter the value of A4 here: Enter the value of A5 here: Enter the value of A6 here: Enter the value of A8 here: Enter the value of A9 here: Enter the value of A10 here:
Enter the value of A11 here:
(d) (1 point) How many vertices are in a minimum vertex cover of G?
Type Your Answer Here:
You can add your notes on this page (if any)
Problem 4: Constraint Satisfaction Problem [6 points]
The Ninja Turtles are at it having their adventures again. In today’s episode, Leo, Mikey, Donny, Ralph are accompanied by Casey and April to defeat Shredder, Krang, Rocksteady and Bebop.
Heroes: Mikey, Donny, Casey, Leo, Ralph, April Villains: Bebop, Krang, Shredder, Rocksteady
This time, the villains have decided to deploy a bomb in the sewers that will potentially flood a major part of New York City, including one of the turtle’s favorite pizza restaurant. The heroes cannot let that happen. When the turtles arrive at the location of the sewers, the turtles find themselves having to deal with many things at the same time, and then have to solve a constraint satisfaction problem, where each of the turtles need to handle one thing or a villain.
• Someone needs to fight Krang
• Someone needs to fight Shredder
• Someone needs to fight Bebop
• Someone needs to fight Rocksteady
• There’s a computer that needs to be hacked in order to diffuse the bomb. For that, they need someone who has a tech background.
• Donny has a lot of knowledge in tech. April is a scientist, so they also have a lot of
• knowledge in tech. The others aren’t very good with tech.
• Krang and Bebop decided to pair up to fight two people at the same time. Therefore, the heroes who pair up to fight Krang and Bebop must work well together.
• Shredder and Rocksteady decided to pair up to fight two people at the same time. Therefore, the heroes who pair up to fight Shredder and Rocksteady must work well together.
• There is a rope that needs to be cut in order to close a gate, protecting Manhattan if the bomb is to go off. But in order to cut the rope, one needs a metal weapon.
• Mikey, Donny, Casey, and April use nunchucks, a bo-staff, a hockey stick, and a baseball bat, respectively, which none are made of metal
• Ralph and Leo use sais and katannas, which are made of metal.
• Leo and Mikey have trained a lot together, so they fight well together
• Leo and Ralph are often fighting about leadership of the team, so they don’t work well together. While they argue, Donny and Mikey train together, so they fight well together.
• Ralph and Casey scout the streets together a lot at night, so they work well together
• April and Donny work well together, since they chat a lot about science.
• TheShredderisaformidablefighter,therefore,whoeverisfightingShredderandRocksteadyneeds to make sure that their cumulative (i.e. summed) strength points are higher than 12.
Strength Points
You are now in charge of assigning our heroes to deal with:
• The computer • The rope
• Shredder
• Rocksteady
Example for Answers: Below, you will be asked questions with regards to whether there exists a solution that satisfies given CSPs and if so, what would be all of the possible heroes that could be on each of the listed tasks. This section is to provide you with an example of how to answer. So let’s say that, for example, for this CSP, there are multiple solutions that are listed below:
In this case, there are four solutions that satisfy some CSP, and the first part of the question should be “Yes”. Now, to list the all possible heroes who could be on each of the tasks:
• Computer: Mikey
• Rope: Ralph
• Shredder: April, Leo
• Krang: April, Leo
• Bebop: Casey, Donny
• Rocksteady: Casey, Donny
(a) (2 points) Given those constraints, will the heroes succeed in saving their favorite pizzeria? (I.e. Is it possible to find a solution which satisfies this CSP?) If so, who are all of the possible heroes who can be on each of the problems? List the names in alphabetical order, and separated by a comma and a space (e.g. Casey, Donny, Leo). If there are no possibilities, leave the text fields blank.
Fight Krang
Fight Shredder
Hack Computer
Fight Bebop
Fight Rocksteady
Programming Help, Add QQ: 749389476
Computer: Rope: Shredder: Krang: Bebop: Rocksteady:
(b) (2 points) Our heroes have fought very well, and greatly damaged Shredder, so he ordered to ex- change the pairs. Now, Shredder and Rocksteady are no longer paired, and Krang and Bebop are no longer paired up. Instead, you must satisfy the following constraints:
• KrangandShredderarenowpaired,soyoumustchoosetheheroesthatcanworkwelltogether to fight them.
• Bebop and Rocksteady are now paired, so you must choose the heroes that can work well together to fight them.
• Now,thepairthatfightsKrangandtheShreddermusthaveacumulativesumofstrengthpoints greater than 12.
The constraints from the previous question should remain the same:
• Someone well versed with tech will deal with the computer to diffuse the bomb • Someone with a metal weapon will help cut the rope
Given those constraints, will the heroes succeed in saving their favorite pizzeria? (I.e. Is it possible to find a solution which satisfies this CSP?) If so, who are all of the possible heroes who can be on each of the problems? List the names in alphabetical order, and separated by a comma and a space (e.g. Casey, Donny, Leo). If there are no possibilities, leave the text fields blank.
Yes No Computer: Rope: Shredder: Krang: Bebop: Rocksteady:
(c) (2points) AtthispointtheygreatlydamagedShredder’sarmor,soourheroesdonothavetohavea cumulative sum of strength points greater than some number anymore. Instead, whoever is working on the computer needs to help whoever is fighting Krang, given that Krang uses an android body. Therefore,
• You must make sure that whoever is fighting Krang must work well with whoever is working on the computer.
All of the other constraint satisfactions from the previous questions remain:
• Krang and Shredder are paired, so you must choose the heroes that can work well together to fight them.
• Bebop and Rocksteady are paired, so you must choose the heroes that can work well together to fight them.
• Someone well versed with tech will deal with the computer to diffuse the bomb
• Someone with a metal weapon will help cut the rope
Given those constraints, will the heroes succeed in saving their favorite pizzeria? (I.e. Is it possible to find a solution which satisfies this CSP?) If so, what are all of the possible heroes who can be on each of the problems? List the names in alphabetical order, and separated by a comma and a space (e.g. Casey, Donny, Leo). If there are no possibilities, leave the text fields blank.
Yes No Computer: Rope: Shredder: Krang: Bebop: Rocksteady:
You can add your notes on this page (if any)
Problem 5: Probability: Life of your TAs [6 points]
Note: During A3, we shared an Ed post titled “Assignment 3 Helpful Probability Formulas”. Feel free to use it while solving this section.
Working as a TA for CS 6601 is a very interesting job. Each TA in the team is assigned specific re- sponsibilities. We will now look at some of the tasks we do as a TA and the challenges involved in them. We are hoping to receive your help in addressing those challenges!
Challenge Questions:
Each week, we aim to release multiple “challenge questions” on Ed. These questions are designed based on the content covered in the class. Each semester, a TA is assigned to design new challenge questions, and release the existing ones to the students via Ed posts. We expect that the students will attempt these questions and have a discussion with each other on the ways to solve them, as we have witnessed this practice improving the ability of students to perform well in the exams.
For the TA assigned to handle these challenge questions, the job is to engage in discussion with students who comment on those challenge questions Ed posts. After studying the data corresponding to the responsiveness of the students to these Ed posts, you come up with an interesting observation:
Let us say you have a challenge question Ed post “P”. We would denote the comments made by students under “P” as “C1”, “C2”, and so on. You observe that if there is at least one comment made by students under P in a given hour, then the probability of them making at least one comment under P in the next hour increases by 0.1. This is because, when a student puts a comment describing their solutions, the others usually take note of it, verify if it is correct or not, and reply to that comment with their feedback (which is why there is an increase in the probability mentioned above). Note that this increase can go up to 1 (as it is the maximum probability for any event). In this case, eventually, the comments will keep on coming on that Ed post every hour, till the end of time. Similarly, you also observe that if there is not a single comment made by students under P in a given hour, then the probability of them making at least one comment under P in the next hour decreases by 0.1. This is because fewer comments will result in fewer interactions. Note that this decrease can go down to 0 (as it is the minimum probability for any event). In this case, eventually, no comments will be added by students each hour on that Ed post, till the end of time. Based on the information provided above, answer the following question.
(a) (2points) Atagivenhour,youaretoldthattheprobabilityofstudentsmakingatleastonecomment under P is 0.3. What is the probability that, eventually, there will be at least one comment made each hour by students under the Ed post, till the end of time?
Type your answer here:
Exam Performance:
After each exam, the TAs analyze the performance of the students to see where the students went wrong so that those concepts could be reinforced later on. To perform this task, three TAs are assigned: David, Yali, and Paul. Suppose, you have a pool of 100 students {S 1, S 2, . . . , S 100} such that the student Si has scored “i” points out of 100 in the exam. For example, S 1 scored 1 out of 100, S 2 scored 2 out of 100, and so on. Out of this pool, each TA will select 6 students in order and at random.
David picked S4, S13, S14, S19, S43, and S87 in this order and he exclaimed: “Wow, I got my picks in an increasing order”. Yali, on the other hand, picked S 64, S 31, S 24, S 9, S 3, and S 2 in this order and she exclaimed: “Look guys, I got my picks in a decreasing order”. Paul said: “Let me try this as well” and he picked S 41, S 18, S 68, S 5, S 33, and S 52 in this order. Tough luck! His picks are neither in increasing
nor decreasing order. After hearing this discussion, Nick joins the party and says: “Now it’s my turn to have the picks!”
(b) (1 point) What is the probability that Nick will have a pick, which is either in an increasing or a decreasing order? Assume that Nick can have his picks from the entire pool of the 100 students.
Type your answer here:
Office Hours:
All the TAs in the CS 6601 team are responsible for holding office hours once a week. The main purpose of holding office hours is to help students with their programming as well as conceptual doubts. The number of students who join during office hours depends on how far the deadline is and how difficult the assignment is. Being curious about it, you decide to study the pattern using a probabilistic model.
You observe that at least one student joins the office hours in the duration of 3 minutes with a probability of 0.992. Assume that the probability of a student joining the office hours in a time interval T1 of length k is the same as well as independent of the probability of a student joining the office hours in a time interval T2 of length k.
(c) (1 point) What is the probability that at least one student joins the office hours in the duration of 1 minute?
Type your answer here:
Bot Fight Simulation:
For the Assignment 2 bonus part, the TAs ask the students to work on their most optimal game-playing bots, which are then pitted against each other. In any match between the 2 bots, a number of games are simulated, and the first bot, who defeats the other bot 10 times, wins the match. For the sake of this problem, assume that the extra credits of 10 points would be given to only the best submission, which will be ranked number 1 in the bot fight. When grading this extra credit part, you come across two sub- missions, which are equally strong in terms of their bot’s ability to win the game. These two submissions have defeated every other submission, and hence, they are facing each other in the finals. Let these two submissions be T1 and T2. These two submissions are so equally matched that the probability that either one of them wins against the other submission is 0.5.
Given this information, you start simulating games between T1 and T2. After the first 15 games, you observe that the score is 8-7 in favor of T1 i.e. T1 has won 8 games and T2 has won 7 games. What an intense match! Whoever reaches the magic figure of 10 wins will take home the extra credits! At this point, you start feeling sad that the losing submission, despite being so close to victory, would not get anything. Thus, you decide to change the grading policy of this extra credit section. The new grading policy is as follows: At this moment, 15 games have been played and T1 has won 8 games and T2 has won 7 games. You will NOT simulate any more games. Instead, you will split the extra credit of 10 points in such a way that the share each submission gets is proportional to the probability with which they have a chance to win the match (whoever would reach 10 wins first wins the match). Remember that the two submissions are so equally matched that the probability that either one of them wins against the other submission is 0.5.
(d) (2 points) If the submission T2 was made by you, how many extra credit points will you receive? Type your answer here:
You can add your notes on this page (if any)
Problem 6: Bayes Nets: There’s No Place Like Home [11 points]
Note: We have provided the structure of the Bayesian network along with the story. Also, calcula- tions are not necessary to answer the questions.
Dorothy and her dog Toto find themselves in a precarious position: their house, which was swept away from Kansas by a tornado, has landed on the Wicked Witch of the East. This involuntary manslaughter delights the locals, but not the deceased witch’s sister, the Wicked Witch of the West, who directs public, vengeful threats toward Dorothy and Toto.
A self-proclaimed “good” Witch of the North, named Glinda, sends them down a yellow brick road to find the mysterious Wizard of Oz, whom Glinda claims may be able to help them return home to Kansas. So Dorothy embarks down this path, wearing ruby slippers that belonged to the Wicked Witch of the East. Glinda tells her that these slippers must have magical powers.
Along the yellow brick road, Dorothy and Toto meet three new companions: the Scarecrow, who wants a brain; the Tin Man, who desires a heart; and the Cowardly Lion, who lacks courage. Despite intimidation and sabotage attempts from the Wicked Witch of the West, they arrive safely at the Emerald City. They speak with the Wizard of Oz, who appears as a ghastly head above smoke and flames. He tells them that he will grant their wishes, including returning Dorothy to Kansas, only if they bring him the Witch of the West’s broomstick. Easier said than done! And to make matters worse, the Wicked Witch has released flying monkeys, which will certainly capture her!
Dorothy, an aspiring AI researcher, decides to build a Bayesian Network to calculate the probability of successfully making it home. This isn’t a Hollywood script after all; this is real life, and nothing is certain! The Bayesian Network shown in Figure 6 is built from the description of prior and conditional probabilities in the description below: After Dorothy is captured by the monkeys and brought to the
Figure 6: Dorothy’s Bayesian Network
witch, her ruby slippers may protect her (call this “protect”). She’s not convinced they are magic; it depends on whether Glinda is a liar!
If Glinda is a liar (call this “liar”), then there is a 0.1 probability the slippers are magic and can protect her. But if Glinda is not a liar, there is a 0.8 probability the slipper