## Description

Question 1: Language Generation

We would like to design a simple language generation system which can generate sensible and grammatically correct

sentences of English of up to length six. The system is able to generate these five words: the, cat, sat, on, mat.

Thus, the sentences that we would want the system to generate are (we ignore capitalization and punctuation issues):

the cat sat

the cat on the mat sat

the cat sat on the mat

The system also incurs a cost for generating each word, equal to the number of consonants the word contains.

a) Formulate the sentence generation process as a (constructive) search problem, stating each of the parts of the

search problem as shown in class. How large is the state space of this problem? Assume that sentences must

contain at least one and no more than six words.

b) Draw the search graph of this problem. If the graph turns out to be too large, draw a portion of it and indicate

how the graph will be extended using some prose and notation. How is it different from the search tree?

c) Trace the run of the search process using the following algorithms for up to 10 steps of the algorithm. Given

multiple states to explore that are otherwise equivalent in priority, the algorithm should prefer to generate the

word that comes first alphabetically.

i. Breadth first search

ii. Uniform cost search

iii. Depth first search

iv. Iterative deepening

d) Describe a scheme that uses local search for this problem, such that given enough running time, the algorithm

would find a goal state. Be sure to state each of the parts of the local search algorithm as shown in class.

Question 2: Search algorithms

(Adapted from Russell & Norvig)

a) Describe a state space in which iterative deepening search performs much worse than depth-first search (for

example, 𝑂(𝑛

2

) vs 𝑂(𝑛)).

Prove each of the following statements, or give a counterexample:

b) Breadth-first search is a special case of uniform-cost search.

c) Uniform-cost search is a special case of A* search.

d) A* search is optimal in the case where negative edge weights are allowed.

e) Best-first search is optimal in the case where we have a perfect heuristic (i.e., ℎ(𝑛) = ℎ

∗

(𝑛), the true cost to

the closest goal state).

f) Suppose there is a unique optimal solution. Then, A* search with a perfect heuristic will never expand nodes

that are not in the path of the optimal solution.

Question 3: Optimization

You should write some code to solve this question. Consider the following functions:

𝑓1

(𝑥, 𝑦) = sin(2𝑥) + cos (

𝑦

2

)

𝑓2

(𝑥, 𝑦) = |𝑥 − 2| + |0.5𝑦 + 1| − 4

We would like to maximize these functions within the range of 0 ≤ 𝑥, 𝑦 ≤ 10. For each part below and each setting,

report the mean and standard deviation of the number of steps to convergence and of the final value 𝑓1

∗

, 𝑓2

∗

for each

case. Use plots and/or tables to report your results in an organized manner.

a) For each function, apply hill climbing, starting from 100 random points in the range. Repeat this procedure

for each choice of step size in [0.01, 0.05, 0.1, 0.2]. A neighbour is a point where x and/or y has increased or

decreased by the stepsize; i.e., there are up to 8 neighbours from any given point. What patterns do you see?

b) Repeat using local beam search with beam width in [2, 4, 8, 16], performing 100 runs of each. Were you able

to improve performance over hill climbing for each function, as measured by the mean and standard deviation

of the number of iterations and/or final objective function value?