Advanced Algorithms Quiz 1: 16 July 2023 (May 2023 term)

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?

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?

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 Hi. 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 .

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?

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 }

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?

$Lateness = \sum_{id=0}^{3} L(i)$

$L(i) = \left\{\begin{matrix} if\ TimeDelivered(i) > TimeDue(i),\ TimeDelivered(i) - TimeDue(i) \\ else, 0 \end{matrix}\right\}$

Consider the following tree:

What is the size of the maximum-size independent set for this tree?

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:

Is assignment X-A, Y-B, Z-C stable?

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:

Consider the following matching: M = (X-C), (Y-B), (Z-A). Which of the following forms a blocking pair in the matching above?

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)?

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)?

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.

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.

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?

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).