Description
Part 1 (theory):
Question 1: [25 marks, 5 marks each]
The search algorithms you have learnt in CS-331 can be used to traverse the graph shown in Fig 1.1. As
you may already know, traversal from each algorithm will result into a different tree. Figure 1.1 was
traversed using 7 different search algorithms, and the corresponding tree (R1 to R7) for each algorithm
has been given below. In each of the 7 diagrams, where applicable, the cost calculated by that algorithm
for each node visited is given next to it. Please note that the children of each node were traversed in an
alphabetical fashion.
A tabular depiction of the Heuristic functions used for some of the traversals is given in Fig 1.2. To help
you correctly interpret Fig 1.2, I will interpret the first row of the table for you. The first row means that
H1(A)=3 and H2(A)=3, where H1 and H2 are the two heuristic functions used.
Your job is to find out for each tree diagram (R1 to R7) the search algorithm that was used to generate it.
Mention whether or not the path generated is optimal (by showing that a path with lesser total cost exists
or not) and whether or not any heuristic function (H1 or H2 and why do you think so?) was used.
You are
required to select one of the following algorithms for each tree:
1. Depth FS
2. Uniform Cost Search
3. Best FS (greedy)
4. A*
5. Breadth FS
Fig 1.1 Fig 1.2
R1
R2
R3
R4 R5
R6 R7
Question 2: [20 marks, 5 marks each]
Use search algorithms #1, #3, #4 and #5 mentioned in Question 1 to write down the ordered list(s) of
visited nodes of the tree shown in Fig 2.1 for each of them.
Question 3: [20 marks, 4 marks each]
This question has several parts:
i. Briefly compare Breadth-First Search (BFS) and Depth First Search (DFS).
ii. What issue does Depth limited Search resolve?
iii. Precisely describe A* search Algorithm.
iv. How does uniform cost search differ from A* search?
v. Which of the four algorithms mentioned so far are complete? Which ones are optimal?
Part 2 (coding):
Question 1: [85 marks, 15 marks each for A* search and recursive algorithms, 10 marks
for each of the rest]
In this part, you are required to implement the famous game Pacman with the help of the search
algorithms you have learnt in class. All files for this part have been uploaded on LMS. You are required
to edit the skeleton-code given in “search.py” using any text-editor of your choice (Sublime is
recommended). An auto-grader for each question is given in “Pacman.ipynb”, which can be executed
using Jupyter. Please do not edit the code in any of the other files.
***
Z
The goal node is Z!
If the heuristic of a node is
not given, assume it is
zero!
Fig 2.1