Description

Total Marks : 100 Marks Weightage: 10%
Instructions:
1. Assignments are to be attempted individually.
2. Submit the assignment as a single zipped folder (Search ⟨RollNumber⟩.zip) containing a pdf file for all the theory questions and a python file (code ⟨RollNumber⟩.py) for programming questions.
4. A part of the assignment evaluation involves automatic testing of your submitted code on private test cases. Please make sure that you do not change the structure of the methods provided in the boilerplate code.
5. All the TAs will strictly follow the rubric provided below. No requests will be entertained related to scoring strategy.
6. The use of generative tools (such as ChatGPT, Gemini, etc.) is strictly prohibited. Failure to comply may result in severe consequences related to plagiarism.
7. Extension and Penalty clause: • Even a 1 minute late submission on google classroom will be considered as late.
• Not explaining the answers properly will lead to zero marks.
1. Consider the search space below where an edge from node x to node y means that y can be generated from x by an operator. The edges are labeled with the actual path cost and the estimated costs to a goal (h-values) are provided inside the nodes.
You are required to find the shortest path from S to goal G1 using the following algorithms:
(a) A* (5)
(b) Uniform cost search (5)
(c) Iterative deepening A* (5)
List the order of nodes expanded (not generated) by these algorithms together with the f-values and total path costs. Show detailed steps of each algorithm in a table with node expansions, frontier nodes, explored nodes (where applicable) for each algorithm. Note: Explore nodes in counter clock-wise direction (left to right) when no other criterion is specified. Also, if two nodes are at the same cost, pick nodes alphabetically for tiebreaking.

2. Consider the following game tree. Note that each square signifies a Max node and each circle is a Min node.

(a) Part A
• Use min-max algorithm to determine best play for both players, i.e. best moves at all levels of the tree for both players. Use arrows to represent the best moves.
Show all legitimate moves. (2)
• Alpha-beta pruning is a directional search algorithm, i.e. it explores children from left to right. Apply alpha-beta pruning to the given game tree. Cross-out the branches where pruning can be done and mark them with alpha or beta depending on its type. (3)
(b) Part B
• Best case: Rearrange the leaf nodes (and internal nodes if necessary) of the given tree so that the maximum pruning is achieved by alpha-beta pruning that explores branches from left to right. Justify your answer. (4)
• Worst case: Rearrange the leaf nodes again to make the worst case for alphabeta pruning. Justify your answer. (4)
(c) Part C
Based on your best case, briefly explain why the best-case complexity is O(bd/2) , where b and d are the branching factor and look-ahead depth, respectively. (2)
3. Consider a graph G = (V,E) representing our institute (Fig 1), where V is the set of nodes and E is the set of edges. Each node u ∈ V represents a unique geographical location and each edge euv ∈ E represents a road connecting the locations u and v. The graph G is given in the form of an n × n adjacency matrix A, where Auv > 0 indicates the travel cost between locations u and v along edge euv, whereas Auv = 0 means that locations u and v are not directly connected, implying an infinite cost for direct travel between them. The locations are named as {0,···,n−1} and all the nodes in the graph are attributed with (x,y) denoting the latitude and longitude of the corresponding location. The dataset and the boilerplate code can be downloaded from this link.
The primary objective of this programming question is to find a path (sequence of nodes traversed including u and v) from a source node u to destination v for a given graph G = (V,E) using various algorithms and compare them. The output of a few ‘public’ test cases is provided in the shared code. The final scoring will be done automatically using ‘multiple private’ test cases. For this purpose, you must not change the method definitions provided in the boilerplate code; otherwise, your submission will not be graded.
(a) Implement the following uninformed search algorithms: (10 + 10 = 20)
• Iterative Deepening Search
• Bidirectional Breadth-First Search
(b) For each public test case, analyze whether the path obtained to travel from source u to destination v using both algorithms is the same. If you find that the path obtained is identical (or different), comment whether it will always be identical (or different) for any pair of nodes in the given graph G. (2.5 + 2.5 = 5)
(c) Obtain the path between all pairs of nodes using both algorithms. Compare the memory usage and time of execution for both algorithms. (2.5 + 2.5 = 5)
(d) Let dist(u,v) be a function that calculates the Euclidean distance between two nodes u and v using the node attributes (x,y). Use the heuristic function given

Figure 1: A graph representing IIIT Delhi
below to implement the following informed search algorithms. (10 + 10 = 20)
h(w) = dist(u,w) + dist(w,v)
• A* Search
• Bidirectional A* Search
(e) Repeat the exercises (b) and (c) using both these informed search algorithms. (2.5+ 2.5 + 2.5 + 2.5 = 10)
(f) Analyze the results obtained using all the uninformed and informed search algorithms. Using scatter plots, compare and contrast the efficiency (in terms of space and time) and optimality (in terms of cost of traveling) of all the algorithms. Explain how the metric to generate the scatter plots was obtained. Also, comment on the benefits and drawbacks of using informed search algorithms over uninformed ones, supported via the empirical analysis. (5 + 5 = 10)
via roads. In order to reduce the vulnerability of such road networks, the minister of road transport and highways wants to construct new roads within our country. For this purpose, the ministry has asked you to develop an algorithm that can be used to identify all vulnerable roads. Specifically, for the given graph G, identify all the edges whose removal would increase the number of disconnected components.
(10)