MauryaHub PYQ Practice

cs4021_2024T2_Q1_NA.pdf

Advanced Algorithms · Quiz 1 · May 2024

← 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 183 NAT · 2.0 marks

[[IMAGE:d591f1b0b55d36b8_2_0]] Based on the above data answer the given subquestions.
What is the answer if the input is 1 1 2 1?
Source diagram or notation

    A published solution is not available for this question yet.

    Question 184 NAT · 2.0 marks

    [[IMAGE:d591f1b0b55d36b8_2_0]] Based on the above data answer the given subquestions.
    What is the answer if the input is 1 2 3 4 5 6 7 8 9 10?
    Source diagram or notation

      A published solution is not available for this question yet.

      Question 185 NAT · 2.0 marks

      [[IMAGE:d591f1b0b55d36b8_2_0]] Based on the above data answer the given subquestions.
      What is the answer if 2n = 50 and the input is the set of all even numbers between 1 and 100? (Hint: you might want to use the fact that the sum of the first n odd numbers is n\(^{2}\).)
      Source diagram or notation

        A published solution is not available for this question yet.

        Question 186 MSQ · 2.0 marks

        [[IMAGE:d591f1b0b55d36b8_2_0]] Based on the above data answer the given subquestions.
        What is the general strategy for solving this problem? Select all strategies that are correct.
        Source diagram or notation
        1. Pick the two smallest available numbers in every step.
        2. Pair the smallest and largest numbers in every step.
        3. Pair the smallest number with the median element in every step.
        4. Pair the largest number with the median element in every step.
        5. Pick the two largest available numbers in every step.

        A published solution is not available for this question yet.

        Question 187 MCQ · 2.0 marks

        [[IMAGE:d591f1b0b55d36b8_4_1]] To play optimally means to play to force a win whenever possible. Based on the above data answer the given subquestions.
        [[IMAGE:d591f1b0b55d36b8_4_2]]
        Source diagram or notationSource diagram or notation
        1. Alice
        2. Bob
        3. Draw

        A published solution is not available for this question yet.

        Question 188 MCQ · 2.0 marks

        [[IMAGE:d591f1b0b55d36b8_4_1]] To play optimally means to play to force a win whenever possible. Based on the above data answer the given subquestions.
        [[IMAGE:d591f1b0b55d36b8_5_3]]
        Source diagram or notationSource diagram or notation
        1. Alice
        2. Bob
        3. Draw

        A published solution is not available for this question yet.

        Question 189 MCQ · 2.0 marks

        [[IMAGE:d591f1b0b55d36b8_4_1]] To play optimally means to play to force a win whenever possible. Based on the above data answer the given subquestions.
        [[IMAGE:d591f1b0b55d36b8_5_4]]
        Source diagram or notationSource diagram or notation
        1. Alice
        2. Bob
        3. Draw

        A published solution is not available for this question yet.

        Question 190 MCQ · 2.0 marks

        [[IMAGE:d591f1b0b55d36b8_4_1]] To play optimally means to play to force a win whenever possible. Based on the above data answer the given subquestions.
        [[IMAGE:d591f1b0b55d36b8_5_5]]
        Source diagram or notationSource diagram or notation
        1. Alice
        2. Bob
        3. Draw

        A published solution is not available for this question yet.

        Question 191 MCQ · 2.0 marks

        [[IMAGE:d591f1b0b55d36b8_4_1]] To play optimally means to play to force a win whenever possible. Based on the above data answer the given subquestions.
        [[IMAGE:d591f1b0b55d36b8_5_6]]
        Source diagram or notationSource diagram or notation
        1. Alice
        2. Bob
        3. Draw

        A published solution is not available for this question yet.

        Question 192 MCQ · 2.0 marks

        [[IMAGE:d591f1b0b55d36b8_4_1]] To play optimally means to play to force a win whenever possible. Based on the above data answer the given subquestions.
        What is the general strategy for Alice?
        Source diagram or notation
        1. Pick the largest even number available.
        2. Pick the largest odd number available.
        3. Pick the largest number available.
        4. Pick the smallest even number available.
        5. Pick the smallest odd number available.
        6. Pick the smallest number available.

        A published solution is not available for this question yet.

        Question 193 MCQ · 1.0 marks

        [[IMAGE:d591f1b0b55d36b8_6_7]] Based on the above data answer the given subquestions.
        [[IMAGE:d591f1b0b55d36b8_6_8]]
        Source diagram or notationSource diagram or notation
        1. TRUE
        2. FALSE

        A published solution is not available for this question yet.

        Question 194 MCQ · 2.0 marks

        [[IMAGE:d591f1b0b55d36b8_6_7]] Based on the above data answer the given subquestions.
        [[IMAGE:d591f1b0b55d36b8_7_9]]
        Source diagram or notationSource diagram or notation
        1. TRUE
        2. FALSE

        A published solution is not available for this question yet.

        Question 195 MCQ · 2.0 marks

        [[IMAGE:d591f1b0b55d36b8_6_7]] Based on the above data answer the given subquestions.
        [[IMAGE:d591f1b0b55d36b8_7_10]]
        Source diagram or notationSource diagram or notation
        1. TRUE
        2. FALSE

        A published solution is not available for this question yet.

        Question 196 NAT · 2.0 marks

        [[IMAGE:d591f1b0b55d36b8_8_11]] Based on the above data answer the given subquestions.
        What is the answer if there are four flowers with heights 3, 1, 4, 2 and beauties 10, 20, 30, 40, respectively?
        Source diagram or notation

          A published solution is not available for this question yet.

          Question 197 NAT · 2.0 marks

          [[IMAGE:d591f1b0b55d36b8_8_11]] Based on the above data answer the given subquestions.
          What is the answer if there are four flowers with heights 4, 3, 2, 1 and beauties 10, 20, 30, 40, respectively?
          Source diagram or notation

            A published solution is not available for this question yet.

            Question 198 NAT · 3.0 marks

            [[IMAGE:d591f1b0b55d36b8_8_11]] Based on the above data answer the given subquestions.
            What is the answer if there are nine flowers with heights 4, 2, 5, 8, 3, 6, 1, 7, 9 and beauties 6, 8, 8, 4, 6, 3, 5, 7, 5, respectively?
            Source diagram or notation

              A published solution is not available for this question yet.

              Question 199 MCQ · 2.0 marks

              [[IMAGE:d591f1b0b55d36b8_8_11]] Based on the above data answer the given subquestions.
              Consider the following greedy algorithm for the problem: scan the flowers left to right. If the current flower violates the monotonicity condition with respect to the sequence we have so far, remove it. Otherwise, keep it. Is this algorithm correct?
              Source diagram or notation
              1. Yes
              2. No

              A published solution is not available for this question yet.

              Question 200 MCQ · 2.0 marks

              [[IMAGE:d591f1b0b55d36b8_8_11]] Based on the above data answer the given subquestions.
              Consider the following greedy algorithm for the problem: Phase 1. scan the flowers left to right. If the current flower violates the monotonicity condition (increasing heights) with respect to the sequence we have so far, remove it. Otherwise, keep it. At the end, suppose the total beauty of the remaining flowers is p. Phase 2. Starting with the original set of flowers again, scan them right to left. If the current flower violates the monotonicity condition (decreasing heights) with respect to the sequence we have so far, remove it. Otherwise, keep it. At the end, suppose the total beauty of the remaining flowers is q. Return max(p, q). Is this algorithm correct?
              Source diagram or notation
              1. Yes
              2. No

              A published solution is not available for this question yet.

              Question 201 MCQ · 2.0 marks

              [[IMAGE:d591f1b0b55d36b8_8_11]] Based on the above data answer the given subquestions.
              Consider the following greedy algorithm for the problem. Initially, all flowers are unmarked. Repeat until a monotonically increasing sequence is obtained: keep and mark the most beautiful unmarked flower, and remove all flowers taller than it to its left and shorter than it to its right. Is this algorithm correct?
              Source diagram or notation
              1. Yes
              2. No

              A published solution is not available for this question yet.

              Question 202 MCQ · 1.0 marks

              [[IMAGE:d591f1b0b55d36b8_8_11]] Based on the above data answer the given subquestions.
              [[IMAGE:d591f1b0b55d36b8_10_12]]
              Source diagram or notationSource diagram or notation
              1. [[IMAGE:d591f1b0b55d36b8_10_13]]
                Source diagram or notation
              2. [[IMAGE:d591f1b0b55d36b8_10_14]]
                Source diagram or notation
              3. [[IMAGE:d591f1b0b55d36b8_10_15]]
                Source diagram or notation
              4. [[IMAGE:d591f1b0b55d36b8_10_16]]
                Source diagram or notation

              A published solution is not available for this question yet.

              Question 203 MCQ · 1.0 marks

              [[IMAGE:d591f1b0b55d36b8_8_11]] Based on the above data answer the given subquestions.
              [[IMAGE:d591f1b0b55d36b8_10_17]]
              Source diagram or notationSource diagram or notation
              1. [[IMAGE:d591f1b0b55d36b8_10_18]]
                Source diagram or notation
              2. [[IMAGE:d591f1b0b55d36b8_10_19]]
                Source diagram or notation
              3. [[IMAGE:d591f1b0b55d36b8_10_20]]
                Source diagram or notation
              4. [[IMAGE:d591f1b0b55d36b8_11_21]]
                Source diagram or notation
              5. [[IMAGE:d591f1b0b55d36b8_11_22]]
                Source diagram or notation

              A published solution is not available for this question yet.

              Question 204 MCQ · 3.0 marks

              [[IMAGE:d591f1b0b55d36b8_8_11]] Based on the above data answer the given subquestions.
              [[IMAGE:d591f1b0b55d36b8_11_23]]
              Source diagram or notationSource diagram or notation
              1. [[IMAGE:d591f1b0b55d36b8_11_24]]
                Source diagram or notation
              2. [[IMAGE:d591f1b0b55d36b8_11_25]]
                Source diagram or notation
              3. [[IMAGE:d591f1b0b55d36b8_11_26]]
                Source diagram or notation
              4. [[IMAGE:d591f1b0b55d36b8_11_27]]
                Source diagram or notation
              5. [[IMAGE:d591f1b0b55d36b8_11_28]]
                Source diagram or notation

              A published solution is not available for this question yet.

              Question 205 NAT · 1.0 marks

              The notion of treewidth can be defined in several ways. One way to frame the definition of treewidth is by using the following game called the cops-and-robber game. The game consists of a set of cops trying to catch a robber. The robber lives in the graph and can move with infinite speed along the edges of the graph. He cannot, however, move through a vertex should a cop be guarding it. The cops move about in helicopters, the point being that they are not constrained to move along the edges of the graph, but they have finite speed. The game proceeds as follows. Initially, the robber occupies some vertex of the graph. The cops announce their positions (a set of vertices) and move towards them with finite speed. Seeing their positions, the robber announces his position (a vertex) and moves to that vertex instantaneously. Not all cops need land on vertices at once and not all cops need change positions, that is, if a cop occupies a vertex, it may continue occupying that vertex in the next move of the game. The cops catch the robber when one of them lands on a vertex occupied by him. For example, on a cycle of length more than three, the robber can always escape a single cop. We are interested in finding the smallest number of cops we need to deploy to ensure that the robber can be caught in a finite number of rounds of this game. Based on the above data answer the given subquestions.
              How many cops are necessary and sufficient to catch the robber on a path?

                A published solution is not available for this question yet.

                Question 206 NAT · 2.0 marks

                The notion of treewidth can be defined in several ways. One way to frame the definition of treewidth is by using the following game called the cops-and-robber game. The game consists of a set of cops trying to catch a robber. The robber lives in the graph and can move with infinite speed along the edges of the graph. He cannot, however, move through a vertex should a cop be guarding it. The cops move about in helicopters, the point being that they are not constrained to move along the edges of the graph, but they have finite speed. The game proceeds as follows. Initially, the robber occupies some vertex of the graph. The cops announce their positions (a set of vertices) and move towards them with finite speed. Seeing their positions, the robber announces his position (a vertex) and moves to that vertex instantaneously. Not all cops need land on vertices at once and not all cops need change positions, that is, if a cop occupies a vertex, it may continue occupying that vertex in the next move of the game. The cops catch the robber when one of them lands on a vertex occupied by him. For example, on a cycle of length more than three, the robber can always escape a single cop. We are interested in finding the smallest number of cops we need to deploy to ensure that the robber can be caught in a finite number of rounds of this game. Based on the above data answer the given subquestions.
                How many cops are necessary and sufficient to catch the robber on a tree?

                  A published solution is not available for this question yet.

                  Question 207 NAT · 2.0 marks

                  The notion of treewidth can be defined in several ways. One way to frame the definition of treewidth is by using the following game called the cops-and-robber game. The game consists of a set of cops trying to catch a robber. The robber lives in the graph and can move with infinite speed along the edges of the graph. He cannot, however, move through a vertex should a cop be guarding it. The cops move about in helicopters, the point being that they are not constrained to move along the edges of the graph, but they have finite speed. The game proceeds as follows. Initially, the robber occupies some vertex of the graph. The cops announce their positions (a set of vertices) and move towards them with finite speed. Seeing their positions, the robber announces his position (a vertex) and moves to that vertex instantaneously. Not all cops need land on vertices at once and not all cops need change positions, that is, if a cop occupies a vertex, it may continue occupying that vertex in the next move of the game. The cops catch the robber when one of them lands on a vertex occupied by him. For example, on a cycle of length more than three, the robber can always escape a single cop. We are interested in finding the smallest number of cops we need to deploy to ensure that the robber can be caught in a finite number of rounds of this game. Based on the above data answer the given subquestions.
                  How many cops are necessary and sufficient to catch the robber on a cycle?

                    A published solution is not available for this question yet.

                    Question 208 MCQ · 2.0 marks

                    The notion of treewidth can be defined in several ways. One way to frame the definition of treewidth is by using the following game called the cops-and-robber game. The game consists of a set of cops trying to catch a robber. The robber lives in the graph and can move with infinite speed along the edges of the graph. He cannot, however, move through a vertex should a cop be guarding it. The cops move about in helicopters, the point being that they are not constrained to move along the edges of the graph, but they have finite speed. The game proceeds as follows. Initially, the robber occupies some vertex of the graph. The cops announce their positions (a set of vertices) and move towards them with finite speed. Seeing their positions, the robber announces his position (a vertex) and moves to that vertex instantaneously. Not all cops need land on vertices at once and not all cops need change positions, that is, if a cop occupies a vertex, it may continue occupying that vertex in the next move of the game. The cops catch the robber when one of them lands on a vertex occupied by him. For example, on a cycle of length more than three, the robber can always escape a single cop. We are interested in finding the smallest number of cops we need to deploy to ensure that the robber can be caught in a finite number of rounds of this game. Based on the above data answer the given subquestions.
                    How many cops are definitely enough to catch the robber on a graph of treewidth k?
                    1. [[IMAGE:d591f1b0b55d36b8_13_29]]
                      Source diagram or notation
                    2. [[IMAGE:d591f1b0b55d36b8_13_30]]
                      Source diagram or notation
                    3. [[IMAGE:d591f1b0b55d36b8_13_31]]
                      Source diagram or notation
                    4. [[IMAGE:d591f1b0b55d36b8_13_32]]       **RL** **Section Id :** 64065359436 **Section Number :** 13 **Section type :** Online **Mandatory or Optional :** Mandatory **Number of Questions :** 8 **Number of Questions to be attempted :** 8 **Section Marks :** 40 **Display Number Panel :** Yes **Section Negative Marks :** 0 **Group All Questions :** No
                      Source diagram or notation

                    A published solution is not available for this question yet.