2021/7/22 Quiz: R/AA exam
R/AA exam
Started: 22 Jul at 13:00
Quiz instructions
1. Answer all questions.
2. DO NOT click submit until the end of the exam.
3. If you accidentally click submit, call the Online Exam Helpline.
Question 1 2 pts
Breadth first search (BFS) and depth first search (DFS) are two basic search algorithms. Give one advantage and one disadvantage of BFS and DFS respectively.
Edit View Insert Format Tools Table 12pt Paragraph
p
0 words
Subway Network
https://myuni.adelaide.edu.au/courses/67549/quizzes/110196/take
1/19
2021/7/22 Quiz: R/AA exam
The following diagrams shows the subway network of a city, where the points labelled with a letter represent stations, while the lines connecting points indicate the availability of connections between stations.
The time to travel (in minutes) between directly connected stations are given in the following matrix (blank cell indicates no direct connections):
ABCDEFGHIJKLMNOPQ 20
A
B
C
D 20 E
F 20 30 G
H
I
30 20
30 10 30 20
20
30 30
30
10 203010
30 20 20 20 20
J 30
K L M N O P Q
30 30
3030 20
20
20
10
10 10 10
2010 20 10
50 1010
50 10 10 10
https://myuni.adelaide.edu.au/courses/67549/quizzes/110196/take
2/19
2021/7/22 Quiz: R/AA exam
Question 2 1 pts
Give one fundamental property of the matrix introduced in Subway Network above.
Edit View Insert Format Tools Table 12pt Paragraph
p
0 words
Question 3 1 pts
Referring to Subway Network above:
Given a start station and an end station, you would like to write a program that can compute a sequence of connected stations that will allow you to travel between the start station and end station.
For example, given A (start station) and C (end station), a possible sequence is A- F-G-D-C.
https://myuni.adelaide.edu.au/courses/67549/quizzes/110196/take
3/19
2021/7/22 Quiz: R/AA exam
https://myuni.adelaide.edu.au/courses/67549/quizzes/110196/take
4/19
What is the branching factor of the search tree to accomplish this task?
Edit View Insert Format Tools Table 12pt Paragraph
p
0 words
Question 4 2 pts
Referring to Subway Network above:
In the program to compute the sequence of connected stations between a start station and an end station, you would also like to minimise the travel duration along the sequence.
Can BFS guarantee finding this sequence with shortest travel duration? Briefly explain your answer.
Assume that the time to transfer between different trains at each station to be zero (0) minutes.
Edit View Insert Format Tools Table 12pt Paragraph
2021/7/22
https://myuni.adelaide.edu.au/courses/67549/quizzes/110196/take
Quiz: R/AA exam
5/19
p 0 words
Question 5 4 pts
Referring to Subway Network above:
Say you would now like to use A* search to find the sequence with the shortest
travel duration between a start station and an end station.
Someone proposed that the Euclidean distance between stations on the subway map (say, obtained by using a ruler to measure the distance between any two points on the map) be used as the heuristic for A* search. Will this allow A* search to guarantee find the sequence with the shortest travel duration? Briefly explain your answer.
Again, assume that the time to transfer between different trains at each station to be zero (0) minutes.
Edit View Insert Format Tools Table 12pt Paragraph
2021/7/22
https://myuni.adelaide.edu.au/courses/67549/quizzes/110196/take
Quiz: R/AA exam
6/19
p 0 words
Question 6 8 pts
The following shows a partially completed tic-tac-toe game, which we call the Current State.
x oo
x
In Current State, the next move belongs to ‘x’.
You would like to write a program to decide on x’s move in Current State. Based on the minimax algorithm, one of the child states of Current State in the search tree is
xx oo
x
with a minimax value of -1.
List the remaining child states of Current State; and
For each child state, denote the minimax value of the child state.
Note: draw the board as a 3×3 table with 10px width and height.
Edit View Insert Format Tools Table 12pt Paragraph
2021/7/22
https://myuni.adelaide.edu.au/courses/67549/quizzes/110196/take 7/19
Quiz: R/AA exam
p 0 words
Question 7 6 pts
In practice, it is not possible to fully traverse the minimax search tree due to resource limits, and evaluation functions are required to approximate the utility of non-terminal states.
Design an evaluation function for tic-tac-toe;
Justify the design of your evaluation function; and
Approximate the utility of the following non-terminal states using your evaluation function.
xx o oox
ox o
x
x ox
o
2021/7/22 Quiz: R/AA exam
Edit View Insert Format Tools Table 12pt Paragraph
p
0 words
Go Outside
You wish to develop a program to predict whether a person is likely to go outside (G) or stay at home (S), based variations of three conditions:
Weather – either wet (W) or dry (D); Money – either rich (R) or poor (P); and Visitors – either yes (Y) or no (N).
The table below contains 16 examples of previous decisions taken by the person, and the conditions observed for those examples.
https://myuni.adelaide.edu.au/courses/67549/quizzes/110196/take
8/19
2021/7/22 Quiz: R/AA exam
https://myuni.adelaide.edu.au/courses/67549/quizzes/110196/take
9/19
You decide to use a decision tree classifier to construct the program…
Question 8 2 pts
Referring to Go Outside above:
Write the expression for the information content at the root node of the decision
tree.
You must put in specific numbers in the expression, but you need not evaluate it. To simplify formatting, please use
log2(n) to indicate the base-2 logarithm of the number n; and (p/q) to indicate the fraction .
Edit View Insert Format Tools Table 12pt Paragraph
𝑞 𝑝
2021/7/22
https://myuni.adelaide.edu.au/courses/67549/quizzes/110196/take
Quiz: R/AA exam
10/19
p 0 words
Question 9 4 pts
Referring to Go Outside above:
Consider now whether to split the root node based on attributes weather or visitor. Write the expression for the information gain of weather and visitor respectively. You must put in specific numbers in the expressions, but you need not evaluate it. To simplify formatting, please use
log2(n) to indicate the base-2 logarithm of the number n; and (p/q) to indicate the fraction .
Edit View Insert Format Tools Table 12pt Paragraph
𝑞 𝑝
2021/7/22
https://myuni.adelaide.edu.au/courses/67549/quizzes/110196/take
Quiz: R/AA exam
11/19
LeNet
The following figure shows the LeNet Convolutional Neural Network.
Each convolutional layer employs 5×5 convolutions and the max pooling
and subsampling layers pool over a 2×2 neighbourhood and reduces the size by a factor of 2 in each image dimension.
p 0 words
Question 10 4 pts
In this LeNet model (without padding) why is there a reduction in the size of the input image from 32×32 to 28×28 in the first feature map?
Edit View Insert Format Tools Table 12pt Paragraph
2021/7/22
https://myuni.adelaide.edu.au/courses/67549/quizzes/110196/take 12/19
Quiz: R/AA exam
Question 11 4 pts
Calculate the number of weights that need to be trained in the second convolutional layer (C3) of LeNet in the above figure.
Edit View Insert Format Tools Table 12pt Paragraph
p
0 words
p 0 words
2021/7/22 Quiz: R/AA exam
https://myuni.adelaide.edu.au/courses/67549/quizzes/110196/take
13/19
Question 12 6 pts
Describe how a perceptron is trained.
Edit View Insert Format Tools Table 12pt Paragraph
p
0 words
Question 13 3 pts
Define the role the activation function plays in a neural network.
Edit View Insert Format Tools Table 12pt Paragraph
2021/7/22
https://myuni.adelaide.edu.au/courses/67549/quizzes/110196/take 14/19
Quiz: R/AA exam
Bayesian Network
The following shows a Bayesian Network with 4 Boolean variables: Cloudy (C), Sprinkler (S), Rain (R) and Wet Grass (W).
p 0 words
Question 14 5 pts
Using Bayesian Network, please calculate P(w, s, r), i.e. the joint probability that the grass is wet, it did rain and the sprinkler was turned on. You may leave
your answer in the form of an arithmetic expression.
You can type your answers in the text box below, or upload an image of your handwritten solution using the ‘Embed Image’ button in the text box.
2021/7/22 Quiz: R/AA exam
Edit View Insert Format Tools Table 12pt Paragraph
p
0 words
Question 15 18 pts
Using Bayesian Network, conduct exact inference and approximate inference (via Likelihood weighting) to compute P(c|s,w) (i.e., P(Cloudy=True|Sprinkler=True, WetGrass = True)) .
For approximate inference, the sampling order is C->R->S->W. Assume you got 4 random values for the first sample: 0.6, 0.4, 0.76, 0.23. Other 4 random values for the second sample: 0.25,0.57,0.32,0.1. Please write the 2 samples and how their weights are calculated. Discuss what other samples are needed in order to estimate P(c|s,w), and why.
Exact inference takes 6 marks. Approximate inference takes 8 marks. The discussion has 4 Marks.
Edit View Insert Format Tools Table 12pt Paragraph
https://myuni.adelaide.edu.au/courses/67549/quizzes/110196/take
15/19
2021/7/22 Quiz: R/AA exam
https://myuni.adelaide.edu.au/courses/67549/quizzes/110196/take
16/19
p 0 words
Question 16 4 pts
Given Anaphoric Ambiguity is “A phrase or word refers to something previously mentioned, but there is more than one antecedent”, please explain whether the following two sentences have anaphoric ambiguity and why.
1. Marcy got the bath ready for her daughter wearing a pink tutu.
2. Henry chatted with another passenger on the train. He turned out to be a
professional hockey player.
Edit View Insert Format Tools Table 12pt Paragraph
2021/7/22
https://myuni.adelaide.edu.au/courses/67549/quizzes/110196/take 17/19
Quiz: R/AA exam
Question 17 4 pts
Given the following Context-Free Grammar, please draw the syntax tree for the sentence “the dog walked with a man”.
Please upload an image of your handwritten solution using the ‘Embed Image’ button in the text box.
Edit View Insert Format Tools Table 12pt Paragraph
p
0 words
p 0 words
2021/7/22 Quiz: R/AA exam
Hidden Markov Model
Consider the Hidden Markov Model defined by the transition and observation probabilities. The hidden variables are X1, X2, …,Xt…, and the observations are O1,O2,…,Ot,….
The hidden variables Xi can take one of 2 values {s1, s2}. The
observations Ot are in {a, b, c}. Assume the hidden sequence starts in a state denoted as X0 with P(X0=s1) = 0.8 and P(X0=s2) = 0.2. The transition probabilities are as represented in the following transition diagram:
For example, P(Xt+1=s1|Xt=s1) = 0.6, P(Xt+1=s2|Xt=s1) =
0.4
The observation probabilities are as follows:
For example, P(Ot=c|Xt=s2) = 0.1.
Question 18 12 pts
For the Hidden Markov Model above, use the method taught in the lecture for Filtering to compute the probability distribution
P(X2|O1=a, O2=b). (Both intermediate steps and results will get marks: each of P(X1|O1=a) and P(X2|O1=a, O2=b) will get 6 marks.)
Show your work here. You can type your answers in the text box below, or upload an image of your handwritten solution using the ‘Embed Image’ button in the text box.
Edit View Insert Format Tools Table
https://myuni.adelaide.edu.au/courses/67549/quizzes/110196/take
18/19
2021/7/22 Quiz: R/AA exam
12pt Paragraph
p
0 words
Not saved
Submit quiz
https://myuni.adelaide.edu.au/courses/67549/quizzes/110196/take
19/19