MauryaHub PYQ Practice

cs4021_2023T2_Q1_NA.pdf

Advanced Algorithms · Quiz 1 · May 2023

← 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 168 MCQ · 4.0 marks

Which of the following is/are true about the given code snippet?
  1. Both Inverse Transform and Accept-Reject algorithms are implemented.
  2. Only one of Inverse Transform and Accept-Reject algorithms are implemented.
  3. The given implemented Accept-Reject is correct as the support of function g is the same as that of function f.
  4. The given implemented Accept-Reject is incorrect for the given function f and g.
  5. The given implemented Inverse Transform algorithm is correct as the cumulative distribution function of f is invertible.       **Advanced Algorithms** **Section Id :** 64065339133 **Section Number :** 9 **Section type :** Online **Mandatory or Optional :** Mandatory **Number of Questions :** 12 **Number of Questions to be attempted :** 12 **Section Marks :** 50 **Display Number Panel :** Yes **Group All Questions :** No **Enable Mark as Answered Mark for Review and** Yes **Clear Response :** **Maximum Instruction Time :** 0

A published solution is not available for this question yet.

Question 170 MCQ · 3.0 marks

[[IMAGE:8b5bbe70ef841dab_3_3]]
Source diagram or notation
  1. **S**i ≤ **F**j
  2. **S**j ≤ **F**i
  3. **S**i ≥ **F**j or **S**j ≥ **F**i
  4. **S**i ≤ **F**j and **S**j ≥ **F**i

A published solution is not available for this question yet.

Question 171 MCQ · 3.0 marks

A circuit in a matroid is a minimal dependent set. In other words, a subset **S** of the universe **U** is a circuit if **S** is not an independent set, but every proper subset of **S** is an independent set. Which of the following would be a circuit for the graphic matroid?
  1. A cycle on any number of vertices
  2. A path on any number of vertices
  3. A star with at least three leaves
  4. A complete subgraph on 4 or more vertices

A published solution is not available for this question yet.

Question 172 MCQ · 3.0 marks

Consider the following set system: ● The universe is the set of edges of a graph G ● A subset S of U is an independent set if the subgraph induced by S is such that every vertex has even degree. Is this set system hereditary?
  1. Yes
  2. No

A published solution is not available for this question yet.

Question 173 MCQ · 3.0 marks

Suppose there are **M** mice out on a field and there are **H** holes scattered across the ground that the mice can hide in. Each hole 1 ≤ i ≤ H has a capacity **H**i. You are given the locations of the mice at time t = 0 and the holes (the locations of the holes are fixed). Each mouse runs at the same velocity **v** and remains vulnerable if it does not reach a hole within **s** seconds when hungry owls arrive and instantaneously catch all the mice that are not in hiding. Consider the following approach to determine the maximum number of mice that can be safe: ● We design a flow network, which consists of a bipartite graph with **M** “mice nodes”, one representing each mouse, and **H** “hole nodes”, one representing each hole. ● If a mouse can reach a particular hole, as determined by the distance between the initial position of the mouse and the given position of the hole , then place an edge between the mouse and the hole with capacity = 1. ● Connect a source node with all the Mice nodes with edge capacities = 1. ● Connect all the Hole nodes with a sink node via edges of capacities = capacity of the particular holes . ● Run Ford−Fulkerson max flow algorithm and the most Mice that are safe equal to the maxFlow obtained .
  1. Cannot say! Depends on the velocity v, time s seconds, hole locations and other factors.
  2. Yes, this approach will always work.
  3. This approach will work if the edges from the source to mice nodes have infinite capacity.
  4. This approach will work under some scenarios but not always.

A published solution is not available for this question yet.

Question 174 MCQ · 5.0 marks

Let **L** be an array of **n** integers. Our array indices start from 0. Let maxSum[i] denote the largest contiguous sum possible in the subarray of **L** ending at the i\(^{th}\) element. Note that maxSum[0] = L[0]. Which of the following recurrences are true?
  1. maxSum[i] = max(maxSum[i - 1] + L[i], L[i])
  2. maxSum[i] = max(maxSum[i - 1], L[i])
  3. maxSum[i] = max(maxSum[i - 1], maxSum[i - 1] + L[i])
  4. maxSum[i] = max(maxSum[i - 1] - L[i], L[i])

A published solution is not available for this question yet.

Question 175 MSQ · 3.0 marks

Recall the task scheduling problem: suppose you have **n** tasks to complete in **n** days; each task requires your attention for a full day. Each task comes with a deadline, the last day by which the job should be completed. A collection of tasks is called realistic if there is a way to schedule all of them in a manner that all of them finish within their deadlines. Given job IDs and deadlines as below, which of the following subsets of jobs is/are realistic? { J1: 5, J2: 1, J3: 1, J4: 2, J5: 4, J6: 3, J7: 4, J8: 4, J9: 5, J10: 3 }
  1. {J1, J9, J2, J4, J8}
  2. {J1, J9, J2, J3, J4, J8}
  3. {J1, J4, J5, J6, J7, J8, J9}
  4. {J2, J4, J10, J7, J1}

A published solution is not available for this question yet.

Question 176 NAT · 4.0 marks

We have a set of jobs to be performed, and we are given the following information about each job: a job ID, the duration required to complete the job, and the time by which the job is due. All jobs have to be performed on a single machine, which can perform one job at a time. Given a schedule for the jobs, the lateness of a job is defined as 0 if it is completed before it is due, and is defined as the difference between the completion time and the time it is due otherwise. This machine has to rest for an hour mandatorily after every 5 hours of continuous work but the machine can take rest for one hour even before 5 hours. If the jobs are executed in an optimal sequence, what is the total lateness? [[IMAGE:8b5bbe70ef841dab_8_4]]
Source diagram or notation

    A published solution is not available for this question yet.

    Question 177 NAT · 3.0 marks

    Consider the following tree: [[IMAGE:8b5bbe70ef841dab_9_5]] What is the size of the maximum-size independent set for this tree?
    Source diagram or notation

      A published solution is not available for this question yet.

      Question 178 MCQ · 3.0 marks

      Consider the following instance of the stable matching problem. Suppose there are 3 women (A, B, C) and 3 men (X, Y, Z), and their preferences as given below and answer the subquestions: [[IMAGE:8b5bbe70ef841dab_10_6]]
      Is assignment X-A, Y-B, Z-C stable?
      Source diagram or notation
      1. Yes
      2. No

      A published solution is not available for this question yet.

      Question 179 MCQ · 3.0 marks

      Consider the following instance of the stable matching problem. Suppose there are 3 women (A, B, C) and 3 men (X, Y, Z), and their preferences as given below and answer the subquestions: [[IMAGE:8b5bbe70ef841dab_10_6]]
      Consider the following matching: M = (X-C), (Y-B), (Z-A). Which of the following forms a blocking pair in the matching above?
      Source diagram or notation
      1. (Y-A)
      2. (X-B)
      3. (Y-C)
      4. (Z-B)

      A published solution is not available for this question yet.

      Question 180 NAT · 4.0 marks

      There is a row of n chairs and two types of people attending a party: C for chess players and S for comedians. You want to assign one person to each seat but you can never seat two chess players together or they will start talking about strategy and everyone else in the room will get bored. For example, if n = 3, the following are some valid seating arrangements: SSS, CSC, and SSC. However, the following is an invalid seating: CCS. Let f(n) denote the number of valid seating arrangements when n chairs are available. Note that f(1) = 2, since both S and C count as valid seating arrangements; while f(2) = 3, since SS, SC, CS are valid seating arrangements but CC is not. Note that we do not need to count the arrangement SS more than once to account for the actual people seated swapping places, we are only interested in the “form” of the seating arrangement. Based on this, you can check that of the eight possible seating arrangements of three chairs, we have five that are valid: CSC, SSC, SSS, SCS, CSS, so f(3) = 5. Based on the above data, answer the given subquestions.
      What is the value of f(6)?

        A published solution is not available for this question yet.

        Question 181 MCQ · 4.0 marks

        There is a row of n chairs and two types of people attending a party: C for chess players and S for comedians. You want to assign one person to each seat but you can never seat two chess players together or they will start talking about strategy and everyone else in the room will get bored. For example, if n = 3, the following are some valid seating arrangements: SSS, CSC, and SSC. However, the following is an invalid seating: CCS. Let f(n) denote the number of valid seating arrangements when n chairs are available. Note that f(1) = 2, since both S and C count as valid seating arrangements; while f(2) = 3, since SS, SC, CS are valid seating arrangements but CC is not. Note that we do not need to count the arrangement SS more than once to account for the actual people seated swapping places, we are only interested in the “form” of the seating arrangement. Based on this, you can check that of the eight possible seating arrangements of three chairs, we have five that are valid: CSC, SSC, SSS, SCS, CSS, so f(3) = 5. Based on the above data, answer the given subquestions.
        Which of the following is a valid recurrence for f(n)?
        1. f(n) = f(n - 1) - f(n - 2)
        2. f(n) = f(n - 1) + f(n - 2)
        3. f(n) = 2 * f(n - 1) - 1
        4. f(n) = 2 * f(n - 1) + 1

        A published solution is not available for this question yet.

        Question 182 MCQ · 2.0 marks

        You have a collection of n elements with weights, which may be positive or negative numbers (but never zero). You want to choose a subset of these elements such that their total weight is maximized. There are constraints to make your life difficult, which are of the form: “If you include element X in your subset, then you must include element Y too.” Let’s abbreviate that X → Y . The total weight of the empty subset of elements is zero and note that weights may be negative. For instance, if your elements are A with a weight of 1 and B with a weight of -1 and no constraints, you may pick A, with the constraint that A → B, you can either pick both elements or neither with the same outcome (note that picking only B is suboptimal and picking only A is not valid), while with the constraint that B → A, you can pick only A and that would be optimal. We will build a flow network to help us find an answer. First, choose a number bigger than the maximum positive value among the given input weights. Call that number **B**. We will have, as usual, a source node **S** and a sink node **T**. Additionally, introduce a vertex for every element in the set. You have an edge from **S** to each node, whose capacity is **B**, and you have an edge from each node to **T**. For the edge from a node **v** representing an element whose weight is w(v), the edge from **v** to the sink node has capacity B - w(v). For each constraint of the form X → Y , you will have an edge from nodes representing elements X to Y with infinite capacity. For the given subquestions, we call an element positive if its weight is positive, and an element is called negative if its weight is negative.
        Consider the edges (S, v) and (v, T), where **v** is a vertex representing some element. If **f** is a maximum flow in the network described in the main question, then is it possible that both of these edges are saturated? For this question, recall that all weights are non-zero.
        1. Yes, provided that **v** has an infinite-capacity edge incident on it (either incoming or outgoing).
        2. Yes, provided that either **v** has positive weight and has an infinite-capacity edge going out of **v** or that **v** has negative weight and has an infinite-capacity edge coming into it.
        3. Yes, provided that either **v** has negative weight and has an infinite-capacity edge going out of **v** or that **v** has positive weight and has an infinite-capacity edge coming into it.
        4. No, this is always impossible.

        A published solution is not available for this question yet.

        Question 183 MCQ · 2.0 marks

        You have a collection of n elements with weights, which may be positive or negative numbers (but never zero). You want to choose a subset of these elements such that their total weight is maximized. There are constraints to make your life difficult, which are of the form: “If you include element X in your subset, then you must include element Y too.” Let’s abbreviate that X → Y . The total weight of the empty subset of elements is zero and note that weights may be negative. For instance, if your elements are A with a weight of 1 and B with a weight of -1 and no constraints, you may pick A, with the constraint that A → B, you can either pick both elements or neither with the same outcome (note that picking only B is suboptimal and picking only A is not valid), while with the constraint that B → A, you can pick only A and that would be optimal. We will build a flow network to help us find an answer. First, choose a number bigger than the maximum positive value among the given input weights. Call that number **B**. We will have, as usual, a source node **S** and a sink node **T**. Additionally, introduce a vertex for every element in the set. You have an edge from **S** to each node, whose capacity is **B**, and you have an edge from each node to **T**. For the edge from a node **v** representing an element whose weight is w(v), the edge from **v** to the sink node has capacity B - w(v). For each constraint of the form X → Y , you will have an edge from nodes representing elements X to Y with infinite capacity. For the given subquestions, we call an element positive if its weight is positive, and an element is called negative if its weight is negative.
        If the input has no constraints (i.e, there are no infinite-capacity edges in the flow network), and the total weight of all the positive elements in **P**, and the absolute value of the sum of the weights of negative elements is **Q**, what is the value of the maximum flow in the network that we have built? Recall that **n** is the total number of elements.
        1. nB - Q
        2. nB - P
        3. nB - (P + Q)
        4. P + Q
        5. P - Q

        A published solution is not available for this question yet.

        Question 184 MSQ · 2.0 marks

        You have a collection of n elements with weights, which may be positive or negative numbers (but never zero). You want to choose a subset of these elements such that their total weight is maximized. There are constraints to make your life difficult, which are of the form: “If you include element X in your subset, then you must include element Y too.” Let’s abbreviate that X → Y . The total weight of the empty subset of elements is zero and note that weights may be negative. For instance, if your elements are A with a weight of 1 and B with a weight of -1 and no constraints, you may pick A, with the constraint that A → B, you can either pick both elements or neither with the same outcome (note that picking only B is suboptimal and picking only A is not valid), while with the constraint that B → A, you can pick only A and that would be optimal. We will build a flow network to help us find an answer. First, choose a number bigger than the maximum positive value among the given input weights. Call that number **B**. We will have, as usual, a source node **S** and a sink node **T**. Additionally, introduce a vertex for every element in the set. You have an edge from **S** to each node, whose capacity is **B**, and you have an edge from each node to **T**. For the edge from a node **v** representing an element whose weight is w(v), the edge from **v** to the sink node has capacity B - w(v). For each constraint of the form X → Y , you will have an edge from nodes representing elements X to Y with infinite capacity. For the given subquestions, we call an element positive if its weight is positive, and an element is called negative if its weight is negative.
        Consider the case when we have two elements **X** and **Y** , with weights w(X) = p and w(Y) = -q, where **p** and **q** are positive integers. In other words, **X** has a positive weight **p** and **Y** has a negative weight whose absolute value is **q**. Suppose we have the constraint X → Y . Let B = p + 1. Also let the label of the vertex representing **X** be **x** and the label of the vertex representing **Y** be **y**. If q > p, then which of the following is/are true?
        1. There is a flow saturating both the edges (S, x) and (S, y).
        2. There is no flow that saturates both the edges (S, x) and (S, y).
        3. There is a flow saturating both the edges (x, T) and (y, T).
        4. There is no flow that saturates both the edges (x, T) and (y, T).

        A published solution is not available for this question yet.

        Question 185 MSQ · 3.0 marks

        You have a collection of n elements with weights, which may be positive or negative numbers (but never zero). You want to choose a subset of these elements such that their total weight is maximized. There are constraints to make your life difficult, which are of the form: “If you include element X in your subset, then you must include element Y too.” Let’s abbreviate that X → Y . The total weight of the empty subset of elements is zero and note that weights may be negative. For instance, if your elements are A with a weight of 1 and B with a weight of -1 and no constraints, you may pick A, with the constraint that A → B, you can either pick both elements or neither with the same outcome (note that picking only B is suboptimal and picking only A is not valid), while with the constraint that B → A, you can pick only A and that would be optimal. We will build a flow network to help us find an answer. First, choose a number bigger than the maximum positive value among the given input weights. Call that number **B**. We will have, as usual, a source node **S** and a sink node **T**. Additionally, introduce a vertex for every element in the set. You have an edge from **S** to each node, whose capacity is **B**, and you have an edge from each node to **T**. For the edge from a node **v** representing an element whose weight is w(v), the edge from **v** to the sink node has capacity B - w(v). For each constraint of the form X → Y , you will have an edge from nodes representing elements X to Y with infinite capacity. For the given subquestions, we call an element positive if its weight is positive, and an element is called negative if its weight is negative.
        Consider the case when we have two elements **X** and **Y**, with weights w(X) = p and w(Y) = -q, where **p** and **q** are positive integers. In other words, **X** has a positive weight **p** and **B** has a negative weight whose absolute value is q. Suppose we have the constraint X → Y. Let B = p + 1. Also let the label of the vertex representing **X** be **x** and the label of the vertex representing **Y** be **y**. Consider the residual graph with respect to some maximum flow **f**. Which of the following is true if q < p? Note that if a directed edge (u, v) has infinite capacity in the flow network, then with respect to any flow that uses this edge, the residual graph will have edges (u, v) with infinite residual capacity and (v, u) as an edge with the same residual capacity as f(u, v).
        1. Both **x** and **y** are always reachable from **S** in the residual graph.
        2. It is possible that both (S, x) and (S, y) are saturated with respect to **f**.
        3. Both (x, T) and (y, T) are saturated with respect to **f**.
        4. At most one of (x, T) and (y, T) can be saturated with respect to **f**.       **Data Viz** **Section Id :** 64065339134 **Section Number :** 10 **Section type :** Online **Mandatory or Optional :** Mandatory **Number of Questions :** 5 **Number of Questions to be attempted :** 5 **Section Marks :** 100 **Display Number Panel :** Yes **Group All Questions :** No **Enable Mark as Answered Mark for Review and** Yes **Clear Response :** **Maximum Instruction Time :** 0

        A published solution is not available for this question yet.