0% found this document useful (0 votes)
83 views16 pagesCOL333 Minor
The document outlines the instructions and structure for a midterm exam in a course on search algorithms, detailing the rules for collaboration, exam format, and specific questions related to search strategies and algorithms. It includes questions on executing search algorithms, comparing their efficiencies, and solving the Hamiltonian cycle problem using genetic algorithms. Additionally, it presents a constraint satisfaction problem involving TAs assigned to exam questions and a game theory question related to the game of Two-Player Uno.
Uploaded by
meetpatil732Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF or read online on Scribd
0% found this document useful (0 votes)
83 views16 pagesCOL333 Minor
The document outlines the instructions and structure for a midterm exam in a course on search algorithms, detailing the rules for collaboration, exam format, and specific questions related to search strategies and algorithms. It includes questions on executing search algorithms, comparing their efficiencies, and solving the Hamiltonian cycle problem using genetic algorithms. Additionally, it presents a constraint satisfaction problem involving TAs assigned to exam questions and a game theory question related to the game of Two-Player Uno.
Uploaded by
meetpatil732Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF or read online on Scribd
/ 16
Entry number: 024C85 051 Name: KusWvaaea GUPTA
COL 333/671 Autumn 2023 Midterm
‘Welcome to midterm exam. The exam is for 2 hours and for 125 pts. Please use only pens
while answering questions. Do not use a pencil. Please do not write outside the margins —
that part may not get graded,
If we find any form of collaboration with any other person during the course of exam, it will
result in a straight zero on the exam —no exceptions.
Before starting the exam, close your eyes and take three deep breaths. Your performance in
the exam is not an accurate reflection of your understanding of the material. Nevertheless, if
you are relaxed, you will likely perform better.
[Question Number | Maximum Marks | _ Marks Obtained
1 18
etachcas 14 oh
13
18
17
i
18
16
20|~a} afer] |uo |r Hi ve
1. [18 points] Execute search algorithms through this undirected graph. Step costs are given next
to cach are, and heuristic values next to cach node. The successors of each node are indicated by
the arrows out of that node. a is the start node and z is the goal. Assume successors are returned in
reverse lexicographic order. In case of any ties, use lexicographic ordering for tie breaking.
For each search strategy below, indicate the order in which nodes are visited. Also, mention the
path returned by each strategy.
first search (no duplicate detection) @ b @& &
Cath eb > a wha toe
es
(6) Kterative-deepening®search (no duplicate detection)
aabLaweres
(@) Greedy be
ghee
(©) A* (full duplicate detection)
QbOe gulwere.
(q) Depth-first branch and bound (partial duplicate detection: only parent not re-expanded),
Let branch policy be g/n)-+h(n). Let lower bound of cost through a node n be g(n)+h(n).
a thao
asta Saez tht yee CE Wer
(©) Uniform cost search (no dup. detection). For this part assume that edge a-eis directed a-De.
aber fer dedvictinnce AFC
Cn ee te will bt
pebpiteed Stan fore 2. [14 points] We first list a few advantages and disadvantages of search algorithms that compare
any two algorithms X and Y. For each pair of algorithms in a row, suggest all comparisons that
are valid. Assume edge costs are positive but can be different for different edges. Also, generally
assume that d (depth at which a goal is found) << m (max depth of search tree).
1 ‘Theoretically, X takes less asymptotic space than Y.
I. Theoretically, X takes more asymptotic space than Y.
II. For large problems, X is generally computationally more efficient (in finding a good
solution) than Y, in practice. *
IV. For large problems, X is generally computationally less efficient (in finding a good
solution) than Y, in practice.
V. Xs (asymptotically) complete but Y is not.
VI. Y is (asymptotically) complete but X is not.
VII. X is (asymptotically) optimal but Y is not.
VIL. Y is (asymptotically) optimal but X is not,
IX, None of the above.
Settin; x y ‘Comparisons
No duplicate Uniform cost search| A* with zero heuristic | Py ( Beth He
Sand
detection
Depih first search with | Breadth first search (
Finite search space | ancesor-based (pig, no duplicate Ly,
on
duplicate detecti detection
Infinite search erative deepening | Depth first search =
space with very _| depth first search TL, TY mm
few goal states
“Admissible Weighted A* with | Best first search with
heuristic h. No w=5 fin) = 2(g(n)+h(n)) Lum, Va
duplicate detection uty 7
Exactly one goal
| state. Large fan in, | Uniform cost search in | Uniform cost search | TE (1.6 OD)
| Small fan out. forward direction in backward direction
Exactly one goal | Breadth first search | Bidirectional search
state. Fan in and with full duplicate with full duplicate LY,
| fan out are similar_| detection detection
Ignore choices III,
IV, V and VI Enforced hill climbing | Greedy hill climbing | T].,
i with random restarts
| Tgnore choices THI,
| TV, Vand VI Random Sampling | Stochastic Local AL
| Beam Search &S
bor
3. [13 points] You are interested in solving the Hamiltonian cycle problem using genetic
algorithms. Le., given a graph G=(V,E), you wish to find a minimum cost cycle visiting all nodes
in the graph exactly once. Let the nodes be numbered /..n. Let each pair of nodes be connected to
cach other, and the cost of following the edge from node i to node j (ey) be cy. All costs are positive,
(a) [3 points] Define a state (string) representation for any individual within a population, Describe
the correspondence between the string and the equivalent cycle in the graph.
Peale oh aig. Coneily ck nekt Mab
dandy ome tg be nni seo a CEE Y,
cyst Gp aprsaintede Ley lef ft,
7 Pe (ot, ni) & CInIs
sti Ge leety “lebe fo oot
Wheat, tae dy othe gag cm du und bo pov &
weg depen pray tS ce peices.
Sees Ut DBAE (mot S49*) 7. 49 a Byetin,
(b) a points] Define a fitness function for a given individual. Note that it should be possible to
take your fitness function and directly use it in the natural selection procedure discussed in class.
Bukreit farectin \— Che thweite cart cobeiferdy
fa ce ayes amapped dy * et .
~ 3 {342 : Se
. “4 arr C44 Che
§
= (01? points] Suggest mutation operator that makes a local change ina given sate
PX rrasbertion Opormet eputd Le bomapporg any L
Wwhtreny q veh Haig fy Ouvte &ruur
iditdudk proph bref fing dre poh Chareds s(t]-4
(@) [5 points] Suggest a crossing over operator that takes exactly two strings in your representation
and creates a new state that has solution components from both parent strings. Explain, how your
operator leads to a valid new solution, and how it has constituents of both parents,
for crntterg 900
a del Q prrriteting GR hegey woh
and conebuck a Aen perrmatetion, hay a“
5 fe 4
Hee 2 it lt $0 a
ot titet tBn CatP
oq fe (es 7 CG),
fe. toy WH Prumidn 294 ocr Co £2 3)
bt, Deb eh, 2H 2,
pe rn je *
iA eat Mie, ge FOR OT gut
bea ~(Gllor te bag,
fen’ fe otto. Pott Gt Ph ppae ) 4, [18 points] The exam of AI is coming up, and there will be a total of six questions in the exam,
QI on uninformed search, Q2 on informed search, Q3 on local search, Q4 on games, Q5 on CSPs
and Q6 on logic. There are seven TAs: Aayush (A), Dhuvil (D), Kausik (K), Prachi (P), Ragjita
(R), Saptarshi (S) and Vipul (V). Each TA will work on exactly one question, though each question
may have multiple TAs. However, TAs are students and have many constraints.
Dhruvil will not work with Prachi.
Raajita will only work on three search questions.
Saptarshi is really odd, and will only work on odd-numbered questions,
Vipul must work on a question that is numbered lower than Saptarshi’s question,
Raajita must work on a question that is numbered lower than Dhruvil’s question.
Aayush made the quiz for CSPs so he will only do the CSP question,
Prachi must work on a question that is numbered greater than Vipul’s question.
‘Aayush and Vipul compete as PhD students, and are not willing to work together on any question
Vipul will not work on logic.
Kausik will not work on games, CSP or logic.
Dhruvil will not work on CSPs
Dhruvil must work on a question that is numbered lower than Kausik’s question.
‘We will model this as a CSP, with TAs as variables and question numbers as values,
(a) [2 points] After applying unary constraints, what values remain for all variables?
Raapiin & £1794 Aap © {oh Prat © £234,
Vt 6 CSS wie & f4-22).
Vrs CLL, 2,346} Lafrrae Of 4353
(b) [2 points] Which variable will be assigned a value first based on heuristics discussed in class?
MRV rust + ay amu hay only one Verndrurg
value uk tee peor. .
Qeper yr te
(©) [4 points] Lets say, instead of assigning the variable you found in part (b), we assign Saptarshi
first. Using the value ordering heuristic discussed in class, find the ordering of values we will ry
for Saptarshi? Assume all unary constraints have been applied first, Show your work,
A aS hs contrary, : .
je hagilar’ Ran torn 1 TEC acoiny dora.
Conran: D2Pe,VSS,8 v
Realizing that it is tree-structured CSP, we decide not to run backtracking search anymore, and
instead run the specialized algorithm for tree-structured CSPs. We will run this after applying all
unary constraints. Let the topological sort gives us the following ordering of variables: Raajita,
Dhnuvil, Kausik, Prachi, Vipul, Aayush, Saptarshi
(4) [6 points] Compute the values remaining for each variable after doing the domain pruning step.
Copelopedl Sank» - RRIEA LY
6 me:
Late wal Prune the clerrnn por by bee are Corsa nty
dour) A sn value OS Cann wr value pn V™
ae nee G web Pea a ws s= £52
Kee jn ge ba Me feet
ke wove (F233 ZVaytere EF + tPov
Ge peta sit 4 oye fee
fa et de D ff et Ym KEL GIF.
We 0 D> Dg Dad pms pete of R te pont
Bray R CL2H vELIUZewa, DeLWIAEL Ses KE
(©) [2 points] Find the solution to the CSP. If multiple values are possible for any TA, choose the
highest numbered
pith. we haw tal” te CLE
nels) p-pas F
ar REL}
VE LKR i= {33
p e963
ene
fra)
LS it§, 5. [17 points] Consider the game of Two-Player Uno: For a set of colors C and a set of numbers
N, there is a deck of cards D = CxN. This deck is mixed and then partitioned into two hands Hi,
Hb with an equal number of cards, and the remaining cards are kept in a pile P. Players alternately
take turns to construct a stack $ of cards. The first player to finish their hand of cards wins.
Let the card at the top of S is (c., ns). When it is a player i's tum to play, they do the following:
«check if there is a card (c, n) € Hi such that the color or number matches the top of the
stack (¢ = ¢; OR n=n). If there is, play that card (add it to the top of the stack). If there
are multiple cards in Hi satisfying this condition, the player may choose any one.
© ifnot, draw a card from the pile P. If the drawn card’s color or number matches the top of
the stack, play the drawn card. Otherwise, continue to draw cards until the drawn card can
be played, or P becomes empty. IFP is empty, then they skip their turn.
If the stack is empty (i.e. the game has not yet started), the first player may play any card from
‘their hand.
(@) [2 points] Classify the game based on whether it is a deterministic game or a game of chance,
a apok q Chaney rbecene Uden ebr UL
TT Hy Po WHA ehh Ke) tag er
wait ee pe
aa a a
reo ak PE Se bene
on
For our game, let C= {Red, Green} and N= {1, 2,3}. We are player one and have been dealt the
hand Hi = {R1, G2}. We have no information about Hs. And player two has no information about
Hh, We make the first move.
(b) [2 points] Which is a better starting move, RI or G2? Justify your answer, (c) [5 points] For this part, we have the starting hand H) and also know the opponent's hand H2 =
{R3, G1}. Similarly, opponent also knows our hand. Draw a game tree. Use the notation discussed
in class. Le., draw upward triangle for our move, downward triangle for opponent's move, a
circular node for a chance node, and at the end a square node to represent a leaf. On each edge
indicate the player action: card name if it is played, or “pick” to indicate a card is picked, and
“pass” to indicate that pile is empty and no move is feasible. Moreover, on edges coming out of
chance nodes, indicate probability of occurrence. After completing the game tree, compute the
probability of win, (Note: if a player picks multiple cards from the pile, it may result in multiple
player moves before opponent gets their chance)
KH, > {RI1,5V
her gd & G13 =
62 Ky
MA
ae
62,
tek
RD a (@) [8 points] Now suppose we don’t know opponent’s hand, and opponent does not know ours,
‘We initially play R1, and opponent initially plays R3. Note that R3 may or may not be optimal
action for the opponent. Draw the game tree now. Using this compute the probability of winning
the game after opponent has already played R3.
tbe perk Irand can doe eanigthys, rh Loree ot Yo 6. [11 points] Several kinds of symmetries are exploited in constraint satisfaction problems to
reduce the size of the search space. This happens in two steps. First we recognize that two or more
states represent the same structure in the problem, and hence will behave similarly (i.e., will either
both have a solution or both won't have a solution). As an example, consider a 7-queens
representation of the problem where Xi represents the location of queen in the i" column. The
board configuration B=(X1,....X7) is symmetric to configuration Bv-(X7,....X1) because By is a
mirror image of B1 along the vertical axis
‘One way to break this symmetry we need to add constraint(s) so that only one of the symmetric
configurations will be explored by the algorithm. For example, in the previous example we can
‘add an additional “global” constraint X1<-X7. You may check that this constraint allows it to
break configurations symmetric along the vertical axis. In this question consider a similar
symmetry along the horizontal axis of the board.
(a) Give an algebraic representation of the configuration (Bh) that is symmetric along
. horizontal axis if B is (X1.....X7),
i & to
ats Bho {yxy e-Xr ~-- 8-Xad # Senn
b24m ly.
(b) Add constraint(s) so that only one of B and Bh are explored by the CSP algorithm.
be allow. a Br Bh we Cn tr Put es
pe bacon ot <8. %. BU pct ed
xis A aN eG 2 Ki 44 (ia yl (if $1 he da bs
‘© What other symmetties are present in 7-queens (list as ay, is ‘you $8 sna?
dhe ake the pow u Syne og
ue the diagonal er B29 BABA ifauert Ow
Heke" Conifegeriton 7 Yor rth cliagonay BC ee Bo #F
(d) Symmetries can also be dynamic. After a value assignment new symmetries may become
valid, Suppose the first queen we place is X1=1, Are there new symmetries present in the
problem? If so, which one(s)?
position webb, ove Oe
at ee Y dymonctiic tw this beard
potion bee KE Xe te Marte keat
(©) Are there new symmetries present if the first queen is X4=1? If so, which one(s)?
Ly i Pe ge spn wi
bee Kyps & Mg et mn xgelen, 7. [18 points] The following figure shows an adversarial search tree. Ifthe minimax search always
chooses the children from left to right, find the output of the search procedure, i.c., the value for
‘each node in the tree. Assume that the search procedure is using alpha-beta pruning. Ifa subtree is
pruned then label all nodes (including the leaves) of the subtree as pruned.
Og
a
+
OO
aD AE
(a) [2 points] What is the final value of A? What is the optimal path found by the search algorithm?
AZ, Path pundhy alyerltni- A +60 u-+Q
(b) [5 points] Mention all nodes that are pruned by the search procedure,
Sith Ut ppwrrd a