CS6601 Final Exam
Professor Thomas Ploetz
Fall 2023
1. Before solving the exam, you should read the Ed exam posts for any updated information or clarifications on
the exam.
2. You should work on this pdf in parallel with the canvas exam to ensure your work is always backed up.
3. Enter your answers as specified into each questions’ provided solution space
4. When you submit the current working copy of your exam download a new copy of the pdf will include any
updates or clarifications made to the exam. So submit regularly
5. Make sure your answers follow the instructions given in the problem area.
6. Unless expressly instructed, round all your final answers to 6 decimal places. Do not round intermediate
results.
7. If you are asked to round to a different number of decimal places, do it or you will lose points.
8. We do this as many questions are auto grade based on regular expressions which have exponential
combinations of solutions. We cannot accommodate all possible combinations. So please help us by closely
reading the instructions.
9. Hint: E.g., For rounding to 6 decimals you can use the round(answer, 6) function in Python
10.This pdf is for your convenience and may be submitted through Fall 2023 Final Calculations. This pdf is not
graded and is not a substitute for the canvas exam. However, any regrades or requests for additional points
must be based on submitted calculations, and are at the discretion of the question author.
11.The exam is open-book, open-note, and open video lectures, with no time limit aside from the due date of the
exam. No internet use is allowed, except for e-text versions of the textbook, this semesters course materials,
Ed, and any links provided in the exam itself.
12.No resources outside this semesters class should be used. Do not discuss the exam with anyone except the
instructional staff. That means no posting on Ed, Slack, Discord, Groupme, or any social media platform. 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 directed in Ed by question subject and number.
13.Please make separate posts for each question area (e.g., Search, CSP, Patterns over time, Logic and
Planning), in general grouping question areas together will have no response from the staff as they focus on
responding to their question area
Points breakdown is provided in the canvas exam
Q 1. Search Part A
In the heart of Silicon Valley, a team of AI researchers at Alphabet-a has just
unveiled their latest creation: Gemini, a groundbreaking multimodal language
model with the ability to interpret and execute complex tasks. Unlike its
predecessors, Gemini is not just a master of words; its proficient in understanding
and generating actionable plans, and has been very popular since its global release.
Gemini has also been integrated into a new line of sophisticated household robots
which are in their beta testing phase. In the hands of one eager beta tester, there is
one of these robots about to face challenges that will put Geminis capabilities to
the test. Tasked with maintaining domestic tranquility, the robot is ready for its first
command. The beta tester, with high expectations, gives the directive: Make the
bathroom sparkle like never before.
In order to fulfill the command, Gemini evaluates several potential actions, some of
which are shown in Figure 1. These outputs were sampled via top-k sampling with k
= 2, meaning all but the 2 most probable words are ignored in the search tree.
Normalized probabilities are shown. To determine how Gemini will make decisions,
Alphabet-a engineers have decided to apply Uniform Cost Search, with a cost
function given by:
C = -ln(p)
Where C represents the cost, p represents the probability of a particular word being
chosen, and ln is the natural logarithm. For example, if p = 0.50, then C = ln(0.50) =
0.693147181.
Figure 1: Geminis search space for Uniform Cost Search.
2
1. What is the order in which the nodes are explored (Exclude the root node)
ou must indicate the search has ended by entering search ended. Ties
are broken by choosing the leftmost path (1 point)
2. What is Geminis final path (Exclude the root node)
ou must indicate the path has ended by entering path ended. Ties are
broken by choosing the leftmost path (1 point)
3. What is the total cost of the final path (1 point)
4. Which of the following describes a reason for using negative log
probabilities as costs in the search algorithm (1 point)
o To prioritize words with higher probabilities by assigning them lower
costs.
o To ensure that less probable words are chosen more frequently.
o To simplify the calculation of probabilities into whole numbers.
o To maximize the reward for the most efficient path.
5. Is Uniform Cost Search complete and optimal with respect to the
cost function for the tree in Figure 1 (1 point)
o It is both complete and optimal because it always finds the least
cost solution
o It is complete but not optimal because it doesnt consider a heuristic
o It is optimal but not complete because it can get stuck in loops
o It is neither complete nor optimal due to the absence of a heuristic
Figure 2: Geminis search space after applying F.
Q1. Part
After some initial testing, the AI safety team at Alphabet-a identifies potential
misinterpretations by Gemini. To address this, they introduce a heuristic h derived
via einforcement earning from uman Feedback (F), representing the
expected human satisfaction with the outcome. This heuristic is designed to guide
the search towards solutions that align more closely with human values and
expectations, and approaches zero as Gemini gets closer to the users goal. The
engineers decide to update their search strategy to include this heuristic, keeping
the same costs from before. They opt for the A search algorithm, using the
negative log probabilities for the cost as before and their new F heuristic to
estimate the remaining cost to reach the goal (Figure 2).
6. What is the order in which the nodes are explored (Exclude the root node). ou
must indicate the search has ended by the option search ended. Ties are broken
by choosing the leftmost path (1 point)
7. What is Geminis final path (Exclude the root node). ou must indicate the
search has ended by the option search ended. Ties are broken by choosing the
leftmost path (1 point)
8 What is the total cost of the final path (1 point)
o Predict future states beyond the current search horizon.
o Increase the probability of words being chosen by lowering their costs.
o Align the search more closely with human satisfaction.
o Eliminate the need for negative log probability costs in the search.
10 Which of the following statements is true (1 point)
o The F heuristic is consistent.
o The F heuristic is admissible.
o The F heuristic is consistent and admissible.
o The F heuristic is neither consistent nor admissible.
9 The addition of the F heuristic is intended to: (1 point)
Two players are playing a game which starts with an array populated with an even number of elements. Each
player takes turns removing an element from the left or right end of the array and adds it to their score. The
game start with both players having no points. The game ends when the array is empty. At the end of the game,
the player with the maximum score wins the game. As an example, lets say Sam and Tom are playing a game
that starts with the array 7, 2, 4, 9, and lets say that Sam takes the first move. The resulting tree would be:
Note: In this game tree with a branching factor of 2, a choice of left receives the leftmost value from the array,
and a choice of right receives the rightmost value from the array. Note that the chosen array elements are
restricted and not available for the next ply or layer.
Assume Sam has the first turn and the starting array is 3,4,5,2, to answer the following questions
Q2. Game Playing Part A
11 Sam has decided to build a tree to find the optimal way to play and win the game. Can you help Sam
complete his tree Please enter the scores for Sam and Tom at each of the steps queried. Enter as integers
(1.5 points)
A. Sam: , Tom:
. Sam: , Tom:
C. Sam: , Tom:
. Sam: , Tom:
12 Which of the following isare true (1 point)
o Given that both players play optimally and an initial array, the outcome of such a game is always
predictable
o If we apply the minimax algorithm with Sam as the maximum player then it will find the shortest path
in the above game tree
o The minimax algorithm will provide Sam with a better solution to play the game than alpha-beta
pruning for this particular game as it will explore all the nodes in the game tree
o oth alpha-beta pruning and minimax algorithm will provide Sam with the same solution to play the
games
et us say that we are rooting for Sam, and thus we hope she wins. y strictly looking at the scores and the
minimax tree, we obtain the following tree:
Q2. Game Playing Part
13 Complete the missing values in the minimax tree. (1.5 points)
14 If we apply alpha-beta pruning to the above tree with Sam as the maximum player, how
many leaf nodes are pruned?
(1 point)
15 If both players play optimally, who will win this game? (1 point)
o Sam
o Tom
A. Sam: ______, Tom: ______
B. Sam: ______, Tom: ______
C. Sam: ______, Tom: ______
Parent 1: NAS AT CT A SAV M
Parent 2: CT NAS AT SAV M A
Parent 3: CT M AT SAV A NAS
Parent 4: A NAS SAV M AT CT
We then evaluate their fitness with a custom fitness function. For a project such as this, the fitness of a path
would be affected by length, geography, building costs, zoning, noise ordinances, and legal costs. In this
problem, we will only use length, meaning the shorter the length the more fit the candidate is. To calculate
the fitness we will use this function, which is the inverse of the length:
f(fitness) = length-1
Now lets evaluate each candidate based on this function. ere are the distances:
AT SAV: 250 miles
AT NAS: 250 miles
AT CT: 245 miles
AT – A: 400 miles
AT M: 150 miles
SAV CT: 250 miles
NAS CT: 400 miles
NAS M: 185 miles
CT A: 170 miles
A SAV: 330 miles
M SAV: 350 miles
A M: 500 miles
CT M: 350 miles
A NAS: 450 miles
NTE: If the distance is not listed here, then the path between the cities is not possible for legal or
geographical reasons.
Q3 ptimization
A research grant has been funded by the US department of transportation to optimize a high-speed train
infrastructure between 6 key cities in the Southeast. ou are tasked with creating a Genetic Algorithm to
determine the best acyclic route. Ignore any infrastructure currently in place between these cities. The
cities are:
Atlanta (AT)
Savannah (SAV)
Nashville (NAS)
Charlotte (CT)
aleigh (A)
irmingham (M)
To do this, we will randomly generate a population of paths, to be parents. Each parent will be denoted as
a chromosome, composed of a set of genes, where each gene is named with a city abbreviation. The cities
are stitched together to create a path that the train can take. The parent population will be:
Q3.1 ptimization
Provide the fitness for each parent: (.75 points ea.)
16: Fitness of Parent 1:
17: Fitness of Parent 2:
18: Fitness of Parent 3:
19: Fitness of Parent 4:
Now we will perform crossovers1 from two pairs of existing parents to create a new generation of child paths.
We will then check to see if each new child path is a viable child. ur criteria for viability is that the train can
reach each city in the path exactly once. We will also check the fitness of each viable child. We have randomly
selected a crossover point at index 3 (zero-based indexing) for all the children. Parents 1 2 will partner to
create Child 1 (P1P2) and Child 2 (P2P1), and Parents 3 4 will partner to create Child 3 (P3P4) and Child 4 (P4
P3). What is the fitness of each child Please put -1 if the child is not viable, because a path does not exist or the
sequence does not go to every city exactly once:
1. See Evolutionary algorithms, AIMA 4th Ed., ussell Norvig, Chptr. 4.1.4, Figure 4.6 (4 Queens ex.)
(.75 points ea)
20: Fitness of Child 1:
21: Fitness of Child 2:
22: Fitness of Child 3:
23: Fitness of Child 4:
Q3.3 ptimization
We will now introduce mutations to the children and recheck viability and fitness. The possible mutations are:
Swap mutation: Two genes are swapped at random
Scramble mutation: A subset of genes in the chromosome are scrambled to a random order Inverse mutation:
The order of a random subset of genes in the chromosome is inverted
We have chosen to do a swap mutation next, at indices 2 and 5 (again, zero-based indexing). Swap the genes at
these indices and reevaluate the fitness of each child. Please put -1 if the child is not viable.
28. Normally we would do these steps for a few generations before selecting the most fit path. ut for this
question, we are now done. Please note which path was the most fit so far in our search, by ordering each city in
terms of what stop it would be from 1-6: (1 point)
Atlanta
irmingham
Charlotte
Nashville
aleigh
Savannah
(.75 points ea)
24: New fitness of Child 1:
25: New fitness of Child 2:
26: New fitness of Child 3:
27: New fitness of Child 4:
Q4 Constraint Satisfaction Problems (CSPs)
our friends have been training and preparing for SailGP all summer and the time has finally come for
registration. owever they are squabbling over what position each person should be in charge of and so
theyve turned to you to help them resolve the issue ecognizing that this is a CSP problem, youve decided to
take an algorithmic approach to assign everyone roles.
Variables: There are 6 variables, and they are your friends, Alice, ob, Carol, an, Elise, and Fred.
omains: There are 4 values that each variable can be assigned, and they are the positions that one can
take on the boat, river (), Flight Controller (FC), Wing Trimmer (WT), and Grinder (G).
It is important to note that there have to be 6 people on the boat at all times, and that each boat may only
have exactly 1 river, exactly 1 Flight Controller, and exactly 1 Wing Trimmer (there can be more than 1
Grinder). Well try to capture these requirements as constraints, but youll see that we wont be able to
capture them entirely.
elow in Figure 1. is the starting set of domains for the CSP problem before any domain reduction occurs.
We will refer to it as domain state zero.
Figure 1: Domain State Zero
Constraints: Youve talked to each of your friends individually and collected all the dierent wishes and
grievances they have and reduced them to a set of unary and binary constraints that are easy to implement
in the CSP algorithm. They are as follows:
Unary Constraints
1. Bob cannot be the FC or a G.
2. Carol cannot be the FC.
inary Constraints
1. If a person is assigned , no other person may be assigned .
2. If a person is assigned FC, no other person may be assigned FC.
3. If a person is assigned WT, no other person may be assigned WT.
4. If Alice is the FC, neither ob, an, nor Elise can be the WT.
5. If Alice is the FC, neither ob nor Fred can be the .
6. If Carol is a G, neither ob nor an can be the G.
7. Elise can be the or WT if and only if Carol is the FC.
8. an or Fred can be the FC if and only if Elise is either the or the WT.
Constraint Graph: Notice how unary constraints are not reflected in the constraint graph shown in Figure 2.
and that all binary constraints between two variables and are expressed in the form of one edge
between and . Also note that all edges that only contain the binary constraints 1, 2, or 3 from above are
represented using a dashed line and that all edges that contain at least one of the binary constraints 4, 5, 6,
7, 8 are represented using a solid line.
Figure 2: The Constraint Graph
Constraint Table: We also provide you with a nifty table with all of the allowed assignment tuples
represented by each edge in the constraint graph (what the algorithm will check when evaluating arc consistency
binary constraints).
Notation: The symbol means any. The symbol means not.
2
Edge Total Allowed Tuples
11
13
12
12
12
12
13
13
13
12
9
13
12
13
(Alice, ob)
(Alice, Carol)
(Alice, an)
(Alice, Elise)
(Alice, Fred)
(ob, Carol)
(ob, an)
(ob, Elise)
(ob, Fred)
(Carol, an)
(Carol, Elise)
(Carol, Fred)
(an, Elise)
(an, Fred)
(Elise, Fred) 12
(FC, G); (, ); (WT, WT); (G, )
(FC, FC); (, ); (WT, WT); (G, )
(FC, ); (FC, G); (, ); (WT, WT); (G, )
(FC, ); (FC, G); (, ); (WT, WT); (G, )
(FC, WT); (FC, G); (, ); (WT, WT); (G, )
(FC, FC); (, ); (WT, WT); (G, G)
(FC, FC); (, ); (WT, WT); (G, )
(FC, FC); (, ); (WT, WT); (G, )
(FC, FC); (, ); (WT, WT); (G, )
(FC, FC); (, ); (WT, WT); (G, G)
(FC, FC); (, FC); (, G); (WT, FC); (WT, G); (G, FC); (G, G)(FC, FC); (,
); (WT, WT); (G, )
(FC, ); (FC, WT); (, ); (WT, WT); (G, )
(FC, FC); (, ); (WT, WT); (G, )
(FC, FC); (, ); (WT, WT); (G, FC)
Table 1: The Constraint Table
Note: This table only applies to binary constraints and does not account for the unary constraints.
29. (2 points)
ow many complete assignments are there in total for this CSP problem For an assignment to be
complete, all variables must be assigned a single value and the assignment does not have to be consistent.
30. (2 points)
While using a backtracking search based algorithm, heuristics may be used at each step to choose what variable
to assign next and what value to assign it. ne such heuristic is the degree heuristic where we select the variable
that is involved in the largest number of constraints on other unassigned variables (binary constraints) 1.
eginning with domain state zero provided above, we will first perform the following steps:
educe all domains by applying node consistency. (3 values should get removed across all domains)
Assign the value of FC to the variable Alice. (All remaining values in Alices domain should get removed and Alices
domain is now fixed)
Apply arc-consistency on Alice only. (8 values should get removed across all domains)
After applying the above steps, we decide that we want to continue with the algorithm. If we use
the degree heuristic based only on the number of solid edges in the constraint graph provided above to select
the next variable for assignment, which variable(s) may we select for assignment next (select all that applies)
int: The node Fred is considered to have a node degree of 2.
1. AIMA, 4th Ed., ussell Norvig, Chptr.
6.3.1
o Alice
o ob
o Carol
o an
o Elise
o Fred
3
31. (2 points)
An alternative heuristic that we can use to pick a variable to assign a value to is the minimum remaining value
heuristic (MRV). MRV chooses the variable with the fewest legal values (values available in its domain) [1].
Beginning with domain state zero provided above, we will first perform the following steps:
Reduce all domains by applying node consistency. (3 values should get removed across all domains)
Assign the value of G to the variable Carol. (All remaining values in Carols domain should get removed and Carols
domain is now fixed)
Make the new state of domains arc-consistent. (5 values should get removed across all domains)
After applying the above steps, we decide that we want to continue with the algorithm. If we use the minimum
remaining value heuristic, which variable(s) may we select for assignment next?
1. AIMA, 4th Ed., Russell & Norvig, Chptr. 6.3.1
o Alice
o Bob
o Carol
o an
o Elise
o red
Figure 3: omain State ne
int: Note that we are applying CV to the set of domains without applying node consistency first. Also
note that G is missing from some of the domains.
32. (2 points)
The two heuristics mentioned above deal with picking variables to make assignments to at each step. ut what
about choosing the value to assign to the variable after the variable to be changed has been chosen A heuristic
that comes in handy for selecting a value is the least constraining value heuristic (CV). CV chooses the value
that rules out the fewest choices for the neighboring variables in the constraint graph1. eginning from the set
of domains provided below (domain state one), we choose the variable an to assign a value to. If we use the
least constraining value heuristic, which value(s) may we assign to variable an next
1. AIMA, 4th Ed., ussell Norvig, Chptr. 6.3.1
an:
o G
o FC
o
o WT
4
Q5 Probability
34. Picking ut of a ag (1 point)
A bag contains 30 pieces of paper marked from 1 to 30. Find the probability of drawing one
odd and one even in a single draw of two tickets.
35. Picking ut of a ag Part II (1 point)
ag 1 has four dimes and two nickels. ag 2 has three dimes and three nickels. A bag is
selected at random and a dime is drawn. What is the probability the dime came from bag
2
36. ogical Proofs (1 point)
Mark all that are True
o If P (A) = P (A) then P (A) = P ()
o If P (A, C) = P (CA, ) then P (AC) = P (C)
o If P (C) = P () then P (A, C) = P (A) P (AC)P (A)
37. Entering a affle (1 point)
There is a raffle with prizes. To enter the raffle you read and agree to the following rules:
1. uy a ticket for 2
2. Each ticket is numbered from 000 – 999, and is assigned at random, and is unique
3. After all of the tickets are sold a winning number from 0 to 999 is selected at random
4. If a ticket contains any of the numbers in the winning numbers in the same ordered
sequence (ones, tens, hundreds) as the winning number a monetary prize is awarded
5. The possible prizes are shown below
a. All 3 numbers the same: 1200
b. Two numbers the same: 100
c. ne number the same: 10
For example, if the winning number was 692 and you got ticket with the number 632 you would
get a prize of 100 for having two of the numbers in the same ordered sequence as the winning
number
Note: ou can only win the highest possible prize that applies to your ticket. If you get 2
numbers correct you only receive 100 and not any of the 10 prize for getting 1 number
correct.
What is the expected profit (or loss) you would expect from a purchase of 3 tickets If a loss
please enter a negative number. (2 points)
(37.)
Q6. ayes Net
Sometimes, the outputs from ayes Networks can seem counter-intuitive. To
understand this, consider the following example: Earthquakes and burglaries
are independent events. Either of them happens with a probability of 0.01, as
shown in Table 1 and 2. Either can possibly cause an alarm to go off. The
probability graph is shown in Figure 1. The joint probability distribution
should be calculated as:
def
Pr( = b, E = e, A = a) = p(b) p(e) p(ab, e)
e p(e)
1 0.01
0 0.99
Table 1: The probability of an earthquake happened. The value of 1 represents
the occurrence of an event, and the value of 0 represents the non-occurrence.
b p(b)
1 0.01
0 0.99
Table 2: The probability of a burglary happened. The value of 1 represents the
occurrence of an event, and the value of 0 represents the non-occurrence.
The conditional probability of P (a b, e) is provided in the Table 3. For
example, P (a = 1 b = 0, e = 1) = 1.0000 denotes the probability that if there is an
earthquake and no burglary, the alarm will go off.
Figure 1: The probability graph of an alarm (A) goes off.
b e a P (a | b, e)
0 0 0 1.0000
0 0 1 0.0000
0 1 0 0.0000
0 1 1 1.0000
1 0 0 0.0000
1 0 1 1.0000
1 1 0 0.0000
1 1 1 1.0000
Table 3: Conditional probability table for P (a | b, e)
b e a P (A = a, = b, E = e)
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
39. (2 points)
Given that the alarm has sounded, what is the probability of a burglary having
occurred, without knowing about an earthquake
Probability:
40. (2 points)
Calculate the probability P ( = 1 A = 1, E = 1). ound your answer to 2 decimal
places.
3. Given all the information above, please fill in the oint probability distribution table. Round your
answers to 4 decimal places (2.5 points)
Probability:
41. oes hearing that theres an earthquake increase, decrease, or keep constant
the probability of a burglary (1.5 points)
o Increase
o ecrease
o eep constant
Q7. Machine earning
Model complexity
In the realm of machine learning, the choice of an appropriate level of model complexity is crucial for achieving
the best performance on a task. While a complex model is prone to overfitting, an overly simplistic model
may not have enough representational power to capture the relationships between the input variables and
desired outputs. et us study this concept in the context of binary classification tasks based on the logical
circuits shown below.
Each circuit has three binary inputs x1, x2 and x3, which can be 0 or 1. et us train one of the simplest
models, a linear classifier, to predict the outputs of logical circuits (separately). The linear classifier is given
by,
F (x1, x2, x3) = w1x1 w2x2 w3x3 b
Where, w1, w2 and w3 are weights and b is the bias. w1, w2, w3 and b are real numbers. The model predicts 1 if F
(x1, x2, x3) 0 and 0 otherwise.
1
42. n which of the provided logic circuits, is it possible for the linear classifier F to attain 100 test
accuracy (int: you may find building truth tables and the notion of separability useful.) (1 point)
o Circuit A
o Circuit
o Circuit C
o Circuit
7.2 Machine earning
ecision Trees
ou are an M engineer at a major music streaming service. To analyze trends in music and improving the
quality of music recommendations, you collected a dataset analyzing musical characteristics of 10 songs,
shown in Table 1. The features you focused on were, Tempo, which is measured in beats per minute;
Instrumentalness (0 to 1), which measures how instrumental (1) or vocal (0) the song content is; Energy (0 to
1), which is the average energy level of the song based on its frequency spectrum and anceability (0 to 1),
which measure of favorability of a song for dancing.
Song Tempo Instrumentality Energy Danceability Genre
1 120 0.05 0.85 0.75 Rock
2 140 0.10 0.80 0.70 Pop
3 100 0.80 0.40 0.60 Jazz
4 90 0.95 0.30 0.50 Jazz
5 160 0.20 0.90 0.80 Rock
6 110 0.70 0.50 0.65 Jazz
7 130 0.15 0.75 0.70 Pop
8 105 0.90 0.35 0.55 Jazz
9 150 0.30 0.95 0.85 Rock
10 125 0.60 0.55 0.65 Pop
Table 1: Song dataset
What is the Gini gain corresponding to the following features in the dataset, assuming that the split is
performed at the mean of the feature values (eport 6 digits) (1.5 points ea)
43: Tempo:
44: Instrumentality:
7.3 Machine earning
NNs and Feature pre-processing
3P, an upcoming artist, just released a song on your streaming platform. ou wanted to add it to a
genre relevant playlist. owever, it is not possible for you to manually listen to the song and determine the
genre, as you have thousands of other songs to classify. aving written code to analyze musical features, you
determine that 3Ps song has a tempo of 125 bpm, instrumentality of 0.85, energy of 0.4 and danceability of
0.5.
45: etermine the 5 most similar songs to 3Ps song based on the euclidean distance metric. The euclidean
distance metric is given as,
d(p, q) =
vuut
Xn
i=0
(pi
