Artificial Intelligence Practice Final Exam May, 2022
We will go over this in May 9 final exam review, so best to do this in advance to prepare.
These are more than 100 points of questions (longer than the actual final will be). The point value serves to give an idea how much it might be worth.
Problem 1: 20 points
Copyright By PowCoder代写 加微信 powcoder
Suppose that you have a training set T with 10,000 instances. The classification attribute has 5 values A, B, C, D, and E, with frequencies 0.05, 0.3, 0.4, 0.2, 0.05. There is some fixed representation of the predictive attributes that we will ignore.
a. (1 pt) Ignoring frequencies, indicate how many bits a traditional fixed-width encoding would take for the classification attribute of this training set.
b. (4 pts) Indicate a prefix-free code for these values that would require the minimum number of bits to encode the classification attribute of this training set.
c. (5 pts) Record how many bits would be needed to encode the classification attribute of this training set using the code from b). Include a decoding table using a “.” separator as in class examples.
You have trained a classifier for this data with 80% accuracy. The classifier uses 128 bits to represent it. The classifier never produces a false negative for A or B; that is, you will never need to correct to A or B, but sometimes a produced {A,B,C,D,E} will need to get corrected to {C,D,E}
d. (5 pts) Design a prefix-free code to combine with this classifier and encode the classification attribute.
e. (5 pts) Record how many bits would be needed to encode the training set using the code from d). Include a decoding table using a “.” separator as in class examples, make sure to include empty for the elements that do not require a code.
Problem 2: 15 points
P ^ Q <=> C v D D => ¬H
C => ¬(P ^ ¬E) CvG
D => ¬(¬E ^ G)
a. (5 pts) Convert the above sentences into CNF. Show your work.
b. (10 pts) Trace an execution of DPLL on your CNF clauses with the following
modifications:
– For hard cases always guess the lowest alphabetical atom, true first.
– For easy cases, indicate all easy cases available, then apply the lowest
alphabetical
Problem 3: 15 points
a. Using Euclidean squared distance for D(p, q) = (px – qx)2 + (py – qy)2 Trace the execution of k-means on the table above using C1=<750,1500>, C2=<2200,500> C3=<1250,1250> as initial centroids, you do not need to show distance tables for each round. If a centroid has no clustered points, keep its coordinates unchanged into the next round.
b. Using the same data, trace the execution of hierarchical clustering down to 3 clusters using complete-linkage and manhattan distance of D(p, q) = abs(px – qx) + abs(py – qy) [Where abs is the absolute value function]
Extra Credit: (5 pts) Suppose that all points where x+y>3000 have the label ‘a’, and the other points are labeled ‘b’. Is the equation 3x+4y = 10000 a linear separator for this data? Is it a Support Vector Machine? Explain why or why not for both.
Problem 4: 20 points
You have a box with 2 coins:
– an “up” coin that comes heads 70% of the time, and
– a “down” coin that comes up tails 60% of the time.
a. (2 pts) You randomly select a coin and flip it. What is the probability that it comes up heads? Show your work.
b. (3 pts) You randomly select a coin and flip it: it comes up tails. What is the probability that it comes up heads when you flip the same coin again? Show your work.
You are offered a game (where x represents your winning payout):
– You randomly select a coin and flip it, noting the outcome
– You now choose to keep the same coin, or swap with the other one to flip again
– If you stay: your opponent automatically bets, winning $20 against losing ‘x’ to you that
another flip of the same coin has the same outcome
– If you switch coins: your opponent automatically bets, winning $20 against losing ‘x’ to
you on the opposite outcome (that is tails if you flipped heads the first time, and vice-versa)
c. (5 pts) Draw a decision tree for this game still using ‘x’ for the payout if you win ($20 if you lose). You may submit a separate pdf or image file of a hand drawing for this.
d. (10 pts) Solve for the smallest integral value of x that makes this game worth playing.
Explain your answer.
Extra Credit (5 pts): Suppose that in a higher stakes version of the same game, you win $105 and lose $100, and after the first free play you can pay $2 to replay the game an infinite number of times.
What is the expected value of such a game using discounted future rewards of .9 and what policy should you use. Use a tolerance of 0.001 and steps of 150 in any solver.
Problem 5: 15 points
Let D be the domain of people and languages. Let L be the first-order language over D with the following primitives:
● S(x, a) – person x can speak language a
● C(x, y) – person x can communicate with y
● T(u, v, w) – person u can act as interpreter between persons v, w
● Spanish, Japanese: languages
● Fred, Mary: people
A. (5 points) Represent the following sentences in L:
i. For any two languages, there is someone who speaks both.
ii. If someone can communicate with two people, then that person can act as an interpreter between them.
iii. If two people both speak the same language, they can communicate iv. Fred speaks Spanish
v. Mary speaks Japanese
vi. There is someone who can interpret between Fred and . (10 points) Using resolution theorem proving, show that vi. is a consequence of i.-v. You need to show the intermediate steps of conversion, and show your initial CNF clauses with Skolemization, and then each step of the resolution proof.
Problem 6: 15 points
Consider the following scheduling problem with N tasks and K processors. The time it takes to complete each task T depends on the processor it is assigned to where actual time = T.length / P.speed.
An example is given below: you have a set of tasks T1-T4 each with a length of time needed to complete. You also have a pair of processors P1 and P2 that offer different speeds. Although both processors can work in parallel, a single processor can only work on one task at a time, so if T1 and T2 are assigned to P1, that takes (24+84)/4 = 27.
The problem is to find an assignment of tasks to processors such that the total time taken is less than some D.
a. (5 pts) Represent this problem for a blind search. That is: what are the states, operators, as well as start, terminal and goal states? What is the branching factor for your representation?
b. (5 pts) Using your representation from a), Trace the execution of a depth first search on the above data for D=33. Use an ordering from lowest to highest number task and processor.
c. (5 pts) Also for D=33, trace the execution of a simple hill-climbing run (no-sideways motion) assuming the following:
i. A state is an assignment of all tasks to a processor
ii. The cost of a state is the max of computing the time needed on each processor –
D. E.g. P1={T1,T3,T4} P2={T2} = max(24+108+96/4, 24/6) = max(57,4)=57 – 33
iii. There are two actions available:
1. Move a task to another processor
2. Swap two tasks
iv. Start state is all tasks assigned to P1 and thus an initial cost of 45
v. The search may terminate if cost < 0
Problem 7: 15 points
A. (10 points) Using the above game tree with payoffs for max. Write out all the equations for minimax (as in class and homework 2): which branch would a root max player choose for what value?
B. (5 points) If run again with root playing as max but also with alpha-beta pruning, which nodes would be pruned?
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com