Parameterized Algorithms - Week 0 Quiz Solutions

Question 1

Suppose we have a simple, undirected, connected graph G where all edges have non-negative weights, and in fact, the weight of each edge is either 1 or 20. Consider the following subgraph H of G --- the vertex set of H is the same as the vertex set of G and the edge set of H consists of all the edges from G whose weight is one. Suppose H has three connected components with 10, 15, and 30 vertices. Then the weight of any minimum spanning tree of G is:

Correct Answer: 92

Question 2

When an array is to be sorted, it may happen that some data values start out being in the same position where they should end up. For example, in the array which is originally: 45,-4,32,0 the 32 is right where it will be in the final sorted output: -4,0,32,45 But as a particular sorting algorithm operates, it might (depending on the algorithm) move such an element out of the position where it belongs and move it back eventually. Let's say that a sorting algorithm respects fixedpoints if it never moves an element that is in its proper position, on any input. Which of the following statements are true? In the options below, the implementation of selection sort is based on swapping the minimum element into it's proper place in the current iteration, and does not involve the use heaps. You may also assume that the input array has no duplicate elements.

A.Insertion sort does not respect fixedpoints but selection sort does

B.Selection sort does not respect fixedpoints but insertion sort does

C.Neither insertion sort nor selection sort respects fixed points

D.Both insertion sort and selection sort respect fixed points

Correct Answer: Insertion sort does not respect fixedpoints but selection sort does

Question 3

Mark the correct options.

A.The functions \{2\log n, n {\log n}, 2ⁿ, n!\} are listed in the increasing order of their asymptotic growth rate

B.The functions \{n {\log n}, 2\log n, 2ⁿ, n!\} are listed in the increasing order of their asymptotic growth rate

C.The functions \{n {\log n}, 2\log n, n!, 2ⁿ\} are listed in the increasing order of their asymptotic growth rate

D.f(n) = O(f(n²))

E.nk ∈ o(cⁿ) but nk ∉ ω(cⁿ)

F.nk ∉ o(cⁿ) but nk ∈ ω(cⁿ)

Correct Answers: The functions \{2\log n, n {\log n}, 2ⁿ, n!\} are listed in the increasing order of their asymptotic growth rate, nk ∈ o(cⁿ) but nk ∉ ω(cⁿ)

Question 4

Assuming P \neq NP, which of the following holds true?

A.NP-COMPLETE ∩ P = φ

B.Let X, Y be two decision problems such that X is NP-COMPLETE and Y is not known to be in NP . Then if X is polynomial time reducible to Y , then Y is NP-COMPLETE

C.Let X, Y be two decision problems such that X is NP-COMPLETE and Y is not known to be in NP . Then if X is polynomial time reducible to Y , then Y is NP-HARD

D.Let L be the language that contains all bipartite graphs. Then L ∈ P and L ∈ NP

E.Let L be the language that contains all bipartite graphs. Then L ∈ P and L ∉ NP

Correct Answers: NP-COMPLETE ∩ P = φ, Let X, Y be two decision problems such that X is NP-COMPLETE and Y is not known to be in NP . Then if X is polynomial time reducible to Y , then Y is NP-HARD, Let L be the language that contains all bipartite graphs. Then L ∈ P and L ∈ NP

Question 5

Which of the following holds true? Recall that chromatic number of a graph is the minimum number of colors required for vertex coloring such that no two adjacent vertices have the same color. A cut vertex of a connected graph G is a vertex whose deletion results in a disconnected graph. Similarly, a cut edge is an edge whose deletion results in a disconnected graph.

A.The chromatic number of a graph which does not contain any odd length cycle is 2

B.In a simple graph G , at least one of the edges incident on a cut vertex is a cut edge

C.An edge e ∈ E(G) is a cut edge in the graph G , if and only if e does not appear in any cycle

D.A connected graph is a tree if and only if every edge is a cut edge

E.Every vertex of a tree is a cut vertex

Correct Answers: The chromatic number of a graph which does not contain any odd length cycle is 2, An edge e ∈ E(G) is a cut edge in the graph G , if and only if e does not appear in any cycle, A connected graph is a tree if and only if every edge is a cut edge

Question 6

Given a graph G with edge-weights, question is to find the minimum weight path between any pair of vertices. Choose the correct options from the following.

A.Dijkstra's Algorithm returns an optimal solution on graphs with negative edge weights

B.Dijkstra's Algorithm may not return optimal solution on graphs with negative edge weights, but the negative edge weight instance can be converted to an equivalent non-negative edge weight instance by adding a sufficiently large weight to all the edges. This modification preserves all the shortest paths in the graph

C.Dijkstra's Algorithm for finding All Pairs Shortest Paths in a graph with n vertices and m edges runs in time O(nm \log n)

D.Dijkstra's Algorithm for finding All Pairs Shortest Paths, in a graph with n vertices and m edges, runs in time O(m \log n)

E.Dijkstra's, Prim's, Kruskal's are greedy algorithms but Bellman Ford is not a greedy algorithm

Correct Answers: Dijkstra's Algorithm for finding All Pairs Shortest Paths in a graph with n vertices and m edges runs in time O(nm \log n), Dijkstra's, Prim's, Kruskal's are greedy algorithms but Bellman Ford is not a greedy algorithm

Question 7

Which of the following is a stable sorting algorithm that takes the least time when applied to an almost sorted array ? (Recall that a sorting algorithm is stable if two objects with equal keys appear in the same order in sorted output as they appear in the input array to be sorted).

A.Quick Sort

B.Insertion Sort

C.Selection Sort

D.Merge Sort

Correct Answer: Merge Sort

Question 8

Which of the following holds true?

A.Let G be any arbitrary flow network, with a source s , a sink t , and positive integer capacities cₑ on every edge. if f is the maximum s-t flow in G , then f saturates every edge out of s (i.e. for all edges out of s , f(e)=cₑ )

B.For every graph G , and every maximum flow on G , there always exists an edge such that increasing the capacity on that edge will increase the maximum flow that’s possible in the graph

C.Suppose the maximum (s,t) -flow of some graph has value f . If we increase the capacity of every edge by 1, then the maximum (s,t) -flow in this modified graph will have value at most f + 1

D.Every k -regular bipartite graph where every vertex has exactly k neighbors, contains a perfect matching

Correct Answer: Every k -regular bipartite graph where every vertex has exactly k neighbors, contains a perfect matching

Question 9

In a party consisting of 5 couples, people who new each other shook hands (pre-covid era) while who did not know each other just greeted each other. One of them, X, observed: "If you don't count me, then there are no two people present who shook hands the same number of times''. How many times did the wife of X shake hands ? (Nobody shook hands with himself or his spouse!)

A.3

B.4

C.0

D.Can't be determined

Correct Answer: 4

Q10

Question 10

If the running time of an algorithm can be represented by the following recurrence, then what is the time complexity of the algorithm? T(n)=\left\{\begin{matrix} 1 & \text{ if } & n = 1 \\ T(n-1)+ n(n-1) & \text{otherwise}& \end{matrix}\right.

A.θ(n³)

B.θ(n²)

C.θ(n \log n)

D.θ(n² \log n)

Correct Answer: θ(n³)

Q11

Question 11

Let \{0,1\}^{\star} denote the set of all strings over the alphabet \{0,1\}. Let A,B\subseteq \{0,1\}^{\star}. For every L\subseteq\{0,1\}^{\star}, let L^{c}:= \Big\{x\in\{0,1\}^{\star}~\big|~x\not\in L\Big\}. Let f:\{0,1\}^{\star}\rightarrow \{0,1\}^{\star} be a polynomial-time computable function such that \forall x\in\{0,1\}^{\star}:~~\Bigg(\Big(x\in A\Big)\Leftrightarrow\Big(f(x)\in B\Big)\Bigg) Let C\subseteq\{0,1\}^{\star} such that C is hard for NP under polynomial-time many-one reductions. Which of the following statements is(are) true?

A.∀ x∈\{0,1\}\star:~~((x∈ Ac)⇔(f(x)∈ Bc))

B.If B∈ NP , then A∈ NP

C.If A\not∈ P , then B\not∈ P

D.If C∈ P , then P=NP

E.C is not hard for NP under polynomial-time Turing reductions

Correct Answers: ∀ x∈\{0,1\}\star:~~((x∈ Ac)⇔(f(x)∈ Bc)), If B∈ NP , then A∈ NP, If A\not∈ P , then B\not∈ P, If C∈ P , then P=NP

Q12

Question 12

Let G be a simple undirected finite graph such that |V(G)|\geq 3. Let f:E(G)\rightarrow\{0,1\} be a function. Which of the following statements is(are) true?

A.There exist u,v∈ V(G) such that u≠ v and |NG(u)|=|NG(v)|, i.e, there exist two distinct vertices that have teh same degree

B.If |E(G)|=15 and |V(G)|=6 , then there exists i∈\{0,1\} such that \{X∈ 2V(G)~|~(|X|=3)\bigwedge(∀ u,v∈ X:~((u≠ v)⇒(\{u,v\}∈ f⁻¹(i))))\}≠φ. In other words, if G is a graph on six vertices and fifteen edges, then G admits a triangle where all edges of the triangle are either mapped to 0 , or all edges of the triangle are mapped to 1 , under f

C.The number of vertices of G that have odd degree is odd, that is: |\{v∈ V(G)~|~|NG(v)|≡ 1~~(mod~2)\}|≡ 1~~(mod~2)

D.If the degree of every vertex in G is at least (|V(G)|)⁄(2) , then G has a Hamiltonian cycle

Correct Answers: There exist u,v∈ V(G) such that u≠ v and |NG(u)|=|NG(v)|, i.e, there exist two distinct vertices that have teh same degree, If |E(G)|=15 and |V(G)|=6 , then there exists i∈\{0,1\} such that \{X∈ 2V(G)~|~(|X|=3)\bigwedge(∀ u,v∈ X:~((u≠ v)⇒(\{u,v\}∈ f⁻¹(i))))\}≠φ. In other words, if G is a graph on six vertices and fifteen edges, then G admits a triangle where all edges of the triangle are either mapped to 0 , or all edges of the triangle are mapped to 1 , under f, If the degree of every vertex in G is at least (|V(G)|)⁄(2) , then G has a Hamiltonian cycle

Q13

Question 13

Let G be a simple undirected finite graph such that |V(G)|\geq 2. Let f: E(G)\rightarrow\mathbb{R}^{+} be a function. For any edge e in G, refer to the value of f(e) as the weight of the edge e. Let \Gamma denote the set of all spanning trees of G. Let \Gamma_{min} be defined as the set of all spanning trees that have the minimum possible total weight with respect to f, that is: \Gamma_{min}:=\Bigg\{T\in\Gamma~\Big|~\forall T'\in\Gamma:~\Bigg(\underset{e'\in E(T')}{\sum}f(e') \geq \underset{e\in E(T)}{\sum}f(e)\Bigg)\Bigg\} For every X\subseteq V(G), let cut(X) be defined as the subset of edges of G that have exactly one of their endpoints in X, that is: cut(X):= E(G)\cap \big\{\{x,y\}~\big|~\big(x\in X\big)\wedge\big(y\in V(G)\setminus X\big)\big\} Let X^{\star}\subseteq V(G). Let e^{\star}\in cut(X^{\star}) such that \forall e\in cut(X^{\star})\setminus\{e^{\star}\}: \big(f(e^*) < f(e)\big) Which of the following statements is(are) true?

A.If f is injective, then |Γₘᵢₙ|≤ 1

B.If G is connected, then |Γₘᵢₙ|≥ 1

C.If |Γₘᵢₙ|≥ 1 , then e\star∈\underset{T∈Γₘᵢₙ}{\bigcap}E(T)

D.There exists T∈Γₘᵢₙ such that |E(T)|≠ |V(G)|-1

Correct Answers: If f is injective, then |Γₘᵢₙ|≤ 1, If G is connected, then |Γₘᵢₙ|≥ 1, If |Γₘᵢₙ|≥ 1 , then e\star∈\underset{T∈Γₘᵢₙ}{\bigcap}E(T)

Q14

Question 14

Let N\in\mathbb{Z}^{+}. Let X and Y be integer valued random variables such that Pr\Big[0\leq X\leq N\Big] = Pr\Big[0\leq Y\leq N\Big] = 1 Let \mathbb{E}(X) and \mathbb{E}(X\cdot Y) denote the expected values of X and X\cdot Y respectively. Which of the following statements is(are) true?

A.\mathbb{E}(X)=∑ₙ₌₀N(n· Pr[X=n])

B.\mathbb{E}(X)< ∑ₙ₌₀N-1Pr[X > n]

C.\mathbb{E}(X· Y) = ∑ₙ₌₀N²(n· Pr[X· Y=n]) = ∑ₙ₌₀N(n·(∑ₘ₌₀N (m· Pr[X=n~and~Y=m])))

D.If X and Y are independent, then \mathbb{E}(X· Y) = ∑ₙ₌₀N-1(Pr[X>n]·(∑ₘ₌₀N-1 Pr[Y>m]))

E.\mathbb{E}(X)≥ max(\{a· Pr[X≥ a]~|~a∈[N]∪\{0\}\})

Correct Answers: \mathbb{E}(X)=∑ₙ₌₀N(n· Pr[X=n]), \mathbb{E}(X· Y) = ∑ₙ₌₀N²(n· Pr[X· Y=n]) = ∑ₙ₌₀N(n·(∑ₘ₌₀N (m· Pr[X=n~and~Y=m]))), If X and Y are independent, then \mathbb{E}(X· Y) = ∑ₙ₌₀N-1(Pr[X>n]·(∑ₘ₌₀N-1 Pr[Y>m])), \mathbb{E}(X)≥ max(\{a· Pr[X≥ a]~|~a∈[N]∪\{0\}\})

Q15

Question 15

Let \Gamma denote the set of all functions from \mathbb{Z}^{+} to \mathbb{R}^{+}. Let f_1,f_2,f_3\in\Gamma. For every function g\in\Gamma, let \mathcal{O}(g), \Omega(g), o(g) and \omega(g) be defined as follows: \mathcal{O}(g):=\Bigg\{f\in\Gamma~\Big|~\exists (c,M)\in\mathbb{R}^{+}\times\mathbb{Z}^{+}:\Bigg(\forall n\in\mathbb{Z}^{+}:\Big(\big(n\geq M\big)\Rightarrow\big(f(n)\leq c\cdot g(n)\big)\Big)\Bigg)\Bigg\} \Omega(g):=\Bigg\{f\in\Gamma~\Big|~\exists (c,M)\in\mathbb{R}^{+}\times\mathbb{Z}^{+}:\Bigg(\forall n\in\mathbb{Z}^{+}:\Big(\big(n\geq M\big)\Rightarrow\big(f(n)\geq c\cdot g(n)\big)\Big)\Bigg)\Bigg\} o(g):=\Bigg\{f\in\Gamma~\Big|~\forall c\in\mathbb{R}^{+}:\Bigg(\exists M\in\mathbb{Z}^{+}:\Big(\forall n\in\mathbb{Z}^{+}:\Big(\big(n\geq M\big)\Rightarrow\big(f(n)< c\cdot g(n)\big)\Big)\Big)\Bigg)\Bigg\} \omega(g):=\Bigg\{f\in\Gamma~\Big|~\forall c\in\mathbb{R}^{+}:\Bigg(\exists M\in\mathbb{Z}^{+}:\Big(\forall n\in\mathbb{Z}^{+}:\Big(\big(n\geq M\big)\Rightarrow\big(f(n)>c\cdot g(n)\big)\Big)\Big)\Bigg)\Bigg\} Which of the following statements is(are) true?

A.If f₁∈\mathcal{O}(f₂) , then f₂∈Ω(f₁)

B.If f₁∈\mathcal{O}(f₂)∩Ω(f₂) , then f₂∈\mathcal{O}(f₁)∩Ω(f₁)

C.If f₁∈ o(f₂) , then f₂∈ω(f₁)

D.o(f₁)\not⊆\mathcal{O}(f₁) and ω(f₁)\not⊆Ω(f₁)

E.If f₁∈\mathcal{O}(f₂) and f₂∈\mathcal{O}(f₃) , then f₁∈\mathcal{O}(f₃)

F.If f₁∈Ω(f₂) and f₂∈Ω(f₃) , then f₁∈Ω(f₃)

G.f₁∈ o(f₁)∪ω(f₁)

H.f₁\not∈\mathcal{O}(f₁)∩Ω(f₁)

I.ω(f₁)∩ o(f₁)≠φ

Correct Answers: If f₁∈\mathcal{O}(f₂) , then f₂∈Ω(f₁), If f₁∈\mathcal{O}(f₂)∩Ω(f₂) , then f₂∈\mathcal{O}(f₁)∩Ω(f₁), If f₁∈ o(f₂) , then f₂∈ω(f₁), If f₁∈\mathcal{O}(f₂) and f₂∈\mathcal{O}(f₃) , then f₁∈\mathcal{O}(f₃), If f₁∈Ω(f₂) and f₂∈Ω(f₃) , then f₁∈Ω(f₃)

Practice: Week 0 : Assignment (Non Graded)