MauryaHub PYQ Practice

cs3003_2026T2_Q2_NA.pdf

AI: Search Methods for Problem Solving · Quiz 2 · May 2026

← Course papers · Start practice / exam

Questions and published explanations below are available without starting a test. Some questions may not have a published solution yet.

Question 2 MSQ · 0.0 marks

[[IMAGE:1a11924b296aa1a7_2_2]]
Source diagram or notation
  1. Printed graph sheets were provided on time.
  2. Printed graph sheets were provided late.
  3. Printed graph sheets were not provided.
  4. I used the graph sheets.
  5. I did not use graph sheets.

A published solution is not available for this question yet.

Question 3 SHORT_TEXT · 2.0 marks

**SEARCH** Consider a state space where each move is reversible and has 6 states (S,A,B,C,D,G) with S as start and G as goal. The heuristic function is: [[IMAGE:1a11924b296aa1a7_3_3]] **Wherever applicable use alphabetical order.** Branch-and-Bound (BnB) algorithm is in mid-flight, the search tree as of the current moment is shown in the figure, where each node displays state and g-value. [[IMAGE:1a11924b296aa1a7_3_4]] Answer the sub-questions based on the information provided.
Make the necessary node refinements to complete the search tree like how Branch-and-Bound algorithm would have done before halting. How many times does each state occur in the final search tree? Enter the counts for S,A,B,C,D,G in the text box. Enter a comma separated list of integers. NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS.
Source diagram or notationSource diagram or notation

    A published solution is not available for this question yet.

    Question 4 SHORT_TEXT · 2.0 marks

    **SEARCH** Consider a state space where each move is reversible and has 6 states (S,A,B,C,D,G) with S as start and G as goal. The heuristic function is: [[IMAGE:1a11924b296aa1a7_3_3]] **Wherever applicable use alphabetical order.** Branch-and-Bound (BnB) algorithm is in mid-flight, the search tree as of the current moment is shown in the figure, where each node displays state and g-value. [[IMAGE:1a11924b296aa1a7_3_4]] Answer the sub-questions based on the information provided.
    What is the path found by A\(^{*}\) for the given state space? Enter the path as a comma separated list, or enter NIL. NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS.
    Source diagram or notationSource diagram or notation

      A published solution is not available for this question yet.

      Question 5 SHORT_TEXT · 2.0 marks

      **SEARCH** Consider a state space where each move is reversible and has 6 states (S,A,B,C,D,G) with S as start and G as goal. The heuristic function is: [[IMAGE:1a11924b296aa1a7_3_3]] **Wherever applicable use alphabetical order.** Branch-and-Bound (BnB) algorithm is in mid-flight, the search tree as of the current moment is shown in the figure, where each node displays state and g-value. [[IMAGE:1a11924b296aa1a7_3_4]] Answer the sub-questions based on the information provided.
      For w=2, what is the path found by WA\(^{*}\) for the given state space? Enter the path as a comma separated list, or enter NIL. NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS.
      Source diagram or notationSource diagram or notation

        A published solution is not available for this question yet.

        Question 6 NAT · 1.0 marks

        **TSP** Answer the given subquestions.
        Consider 6 cities A to F, how many tours are represented by the TSP BnB node (S_0, ~AB, ~AC, BE, ~DB, ~DA)? Infer the permanent segments before counting the tours.

          A published solution is not available for this question yet.

          Question 7 MCQ · 2.0 marks

          **TSP** Answer the given subquestions.
          The TSP BnB procedure will return the optimal tour __________ .
          1. even if node refinement step disables segment inferencing
          2. only when node refinement step uses segment inferencing

          A published solution is not available for this question yet.

          Question 8 SHORT_TEXT · 2.0 marks

          **TSP** Answer the given subquestions.
          Let N be the number of cities. For the purpose of analysis, construct a relaxed (version of TSP BnB) tree in the following manner: expand S_0 by adding 2 children (one with XY and another with ~XY), similarly expand the children, and continue expanding until all branches are fully expanded, without ever applying cost estimates, tour constraints, or inferences. The number of leaf nodes in the relaxed tree will be of the order of __________ . Give your answer in Big-O notation.

            A published solution is not available for this question yet.

            Question 9 SHORT_TEXT · 2.0 marks

            **TSP** Answer the given subquestions.
            Consider the relaxed tree generated in the **PREVIOUS** question. If we prune all nodes that violate the tour condition, the number of leaf nodes in the pruned tree will be of the order of __________ . Give your answer in Big-O notation.

              A published solution is not available for this question yet.

              Question 10 SHORT_TEXT · 2.0 marks

              **GAMES** [[IMAGE:1a11924b296aa1a7_7_5]] Answer the given subquestions.
              Identify the horizon nodes pruned by beta-cuts. Enter their node labels in the text box. Enter a comma separated list of node labels. NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS.
              Source diagram or notation

                A published solution is not available for this question yet.

                Question 11 SHORT_TEXT · 2.0 marks

                **GAMES** [[IMAGE:1a11924b296aa1a7_7_5]] Answer the given subquestions.
                Solve the game tree using SSS\(^{*}\) algorithm. Identify the SOLVED horizon nodes that are removed from the queue by the pruning step. Not popped from the queue but pruned from the queue. Enter the node labels as a comma separated list in ASCENDING order. NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS.
                Source diagram or notation

                  A published solution is not available for this question yet.

                  Question 12 SUBJECTIVE · 2.0 marks

                  **GAMES** [[IMAGE:1a11924b296aa1a7_7_5]] Answer the given subquestions.
                  What is the horizon effect? Give a concise and clear answer. Stay on point. **NOTE:** Your answer should not exceed 100 words.
                  Source diagram or notation

                    A published solution is not available for this question yet.

                    Question 13 MCQ · 2.0 marks

                    **AUTOMATED PLANNING** Answer the given subquestions.
                    Can the Forward State Space Planning algorithm discussed in the lecture solve Sussman Anomaly?
                    1. Yes
                    2. No

                    A published solution is not available for this question yet.

                    Question 14 MCQ · 2.0 marks

                    **AUTOMATED PLANNING** Answer the given subquestions.
                    Can the Goal Stack Planning algorithm discussed in the lecture solve Sussman Anomaly?
                    1. Yes
                    2. No

                    A published solution is not available for this question yet.

                    Question 15 MSQ · 2.0 marks

                    **AUTOMATED PLANNING** Answer the given subquestions.
                    What is true about the Goal Stack Planning algorithm? (Note: a unit goal cannot be decomposed into subgoals.)
                    1. During the plan building phase, it will solve every unit goal exactly once.
                    2. It will never repeat the same action twice in the final plan.
                    3. It will build the plan in a linear fashion without backtracking.
                    4. None of these.

                    A published solution is not available for this question yet.