cs4021_2026T1_Q2_NA.pdf

Consider the statements about randomized quicksort and answer the given subquestions if they are true or false.

The worst-case running time and expected running time are equal to within constant factors for any randomized algorithm.

Consider the statements about randomized quicksort and answer the given subquestions if they are true or false.

An adversary can provide randomized quicksort with an input array of length [[IMAGE:753fc3671e35dbfc_2_2]] that forces the algorithm to run in [[IMAGE:753fc3671e35dbfc_2_3]] time on that input. (If you are not familiar with the [[IMAGE:753fc3671e35dbfc_2_4]] asymptotic notation, it roughly translates as “at least”. For example, we can say that it is possible to come up with an input that forces insertion sort to run for [[IMAGE:753fc3671e35dbfc_2_5]] steps.)

In RANDOMIZED-QUICKSORT, consider two distinct elements [[IMAGE:753fc3671e35dbfc_3_6]] and [[IMAGE:753fc3671e35dbfc_3_7]] with [[IMAGE:753fc3671e35dbfc_3_8]] . What is the probability that these two elements are compared during execution?

**Generating UAR Sequences** The goal of this exercise is to compute a uniformly random permutation of [[IMAGE:753fc3671e35dbfc_3_13]] . Assume we have a generator that produces independent uniform real numbers in [[IMAGE:753fc3671e35dbfc_3_14]] . Consider the following algorithm: • Generate random numbers [[IMAGE:753fc3671e35dbfc_3_15]] independently from [[IMAGE:753fc3671e35dbfc_3_16]] • Pair them as [[IMAGE:753fc3671e35dbfc_3_17]] • Sort the pairs in **decreasing order** of [[IMAGE:753fc3671e35dbfc_3_18]] • Output the permutation based on sorted indices Does this procedure generate a uniformly random permutation of [[IMAGE:753fc3671e35dbfc_3_19]] ?

Consider the following approximation algorithm for the weighted vertex cover problem: 1. Solve the relaxed linear program corresponding to the given problem: **Minimize** [[IMAGE:753fc3671e35dbfc_4_20]] **Subject to** [[IMAGE:753fc3671e35dbfc_4_21]] 2. [[IMAGE:753fc3671e35dbfc_4_22]] 3. return [[IMAGE:753fc3671e35dbfc_4_23]] Based on the above data, answer the given subquestions.

Suppose that instead of putting a vertex [[IMAGE:753fc3671e35dbfc_4_24]] into the cover when [[IMAGE:753fc3671e35dbfc_4_25]] , we put [[IMAGE:753fc3671e35dbfc_4_26]] into the cover when [[IMAGE:753fc3671e35dbfc_4_27]] . What happens?

Consider the following approximation algorithm for the weighted vertex cover problem: 1. Solve the relaxed linear program corresponding to the given problem: **Minimize** [[IMAGE:753fc3671e35dbfc_4_20]] **Subject to** [[IMAGE:753fc3671e35dbfc_4_21]] 2. [[IMAGE:753fc3671e35dbfc_4_22]] 3. return [[IMAGE:753fc3671e35dbfc_4_23]] Based on the above data, answer the given subquestions.

Suppose that instead of putting a vertex [[IMAGE:753fc3671e35dbfc_5_28]] into the cover when [[IMAGE:753fc3671e35dbfc_5_29]] , we put [[IMAGE:753fc3671e35dbfc_5_30]] into the cover when [[IMAGE:753fc3671e35dbfc_5_31]] . What happens?

Consider the following approximation algorithm for the weighted vertex cover problem: 1. Solve the relaxed linear program corresponding to the given problem: **Minimize** [[IMAGE:753fc3671e35dbfc_4_20]] **Subject to** [[IMAGE:753fc3671e35dbfc_4_21]] 2. [[IMAGE:753fc3671e35dbfc_4_22]] 3. return [[IMAGE:753fc3671e35dbfc_4_23]] Based on the above data, answer the given subquestions.

Suppose that we modify the algorithm to include vertex [[IMAGE:753fc3671e35dbfc_5_33]] in the cover only when [[IMAGE:753fc3671e35dbfc_5_34]] . What happens?

Consider the following approximation algorithm for the weighted vertex cover problem: 1. Solve the relaxed linear program corresponding to the given problem: **Minimize** [[IMAGE:753fc3671e35dbfc_4_20]] **Subject to** [[IMAGE:753fc3671e35dbfc_4_21]] 2. [[IMAGE:753fc3671e35dbfc_4_22]] 3. return [[IMAGE:753fc3671e35dbfc_4_23]] Based on the above data, answer the given subquestions.

Suppose that we include vertex [[IMAGE:753fc3671e35dbfc_5_35]] in the cover when [[IMAGE:753fc3671e35dbfc_5_36]] . What happens?

[[IMAGE:753fc3671e35dbfc_6_37]] Based on the above data, answer the given subquestions.

A graph G is a cluster graph if and only if it does not have an induced path on 3 vertices.

[[IMAGE:753fc3671e35dbfc_6_37]] Based on the above data, answer the given subquestions.

In the DISJOINT CLUSTER VERTEX DELETION problem, if the subgraph induced on S is not a cluster graph, we can immediately return YES.

[[IMAGE:753fc3671e35dbfc_6_37]] Based on the above data, answer the given subquestions.

In the DISJOINT CLUSTER VERTEX DELETION problem, if the subgraph induced on the vertices of S is not a cluster graph, we can immediately return NO.

[[IMAGE:753fc3671e35dbfc_6_37]] Based on the above data, answer the given subquestions.

If the subgraph induced on the vertices of S is a cluster graph and a vertex in V (G) \ S is adjacent to at least two vertices in S which are in different cliques, then we can delete it and leave the parameter unchanged.

[[IMAGE:753fc3671e35dbfc_6_37]] Based on the above data, answer the given subquestions.

If the subgraph induced on the vertices of S is a cluster graph and a vertex in V (G) \ S is adjacent to at least two vertices in S which are in different cliques, then we can delete it and decrease the parameter by 1.

[[IMAGE:753fc3671e35dbfc_6_37]] Based on the above data, answer the given subquestions.

If the subgraph induced on the vertices of S is a cluster graph and a vertex in V (G) \ S is adjacent to some but not all vertices in a clique of G[S], then we can delete it and leave the parameter unchanged.

[[IMAGE:753fc3671e35dbfc_6_37]] Based on the above data, answer the given subquestions.

If the subgraph induced on the vertices of S is a cluster graph and a vertex in V (G) \ S is adjacent to some but not all vertices in a clique of G[S], then we can delete it and decrease the parameter by 1.

Consider a graph [[IMAGE:753fc3671e35dbfc_8_38]] and let [[IMAGE:753fc3671e35dbfc_8_39]] denote its chromatic number. Let [[IMAGE:753fc3671e35dbfc_8_40]] . Select all true statements:

Let [[IMAGE:753fc3671e35dbfc_8_47]] be a maximal independent set in graph [[IMAGE:753fc3671e35dbfc_8_48]] . Select all true statements:

[[IMAGE:753fc3671e35dbfc_9_58]] In the above figure, we have a graph G and a **Feedback Vertex Set (FVS)** of size 3, which is given by the boxed vertices: S := {a, c, e} We need to find a **DISJOINT FVS** of size 2. For each of the given statements, determine whether it is **True** or **False**. Based on the above data, answer the given subquestions.

According to the reduction rules for **DFVS**, the following figure shows a valid intermediate instance in the reduction with [[IMAGE:753fc3671e35dbfc_9_59]] . [[IMAGE:753fc3671e35dbfc_10_60]]

[[IMAGE:753fc3671e35dbfc_9_58]] In the above figure, we have a graph G and a **Feedback Vertex Set (FVS)** of size 3, which is given by the boxed vertices: S := {a, c, e} We need to find a **DISJOINT FVS** of size 2. For each of the given statements, determine whether it is **True** or **False**. Based on the above data, answer the given subquestions.

According to the reduction rules for **DFVS**, the following figure shows a valid intermediate instance in the reduction with [[IMAGE:753fc3671e35dbfc_10_61]] . [[IMAGE:753fc3671e35dbfc_10_62]]

[[IMAGE:753fc3671e35dbfc_9_58]] In the above figure, we have a graph G and a **Feedback Vertex Set (FVS)** of size 3, which is given by the boxed vertices: S := {a, c, e} We need to find a **DISJOINT FVS** of size 2. For each of the given statements, determine whether it is **True** or **False**. Based on the above data, answer the given subquestions.

According to the reduction rules for **DFVS**, the following figure shows a valid intermediate instance in the reduction with [[IMAGE:753fc3671e35dbfc_10_63]] . [[IMAGE:753fc3671e35dbfc_10_64]]

[[IMAGE:753fc3671e35dbfc_9_58]] In the above figure, we have a graph G and a **Feedback Vertex Set (FVS)** of size 3, which is given by the boxed vertices: S := {a, c, e} We need to find a **DISJOINT FVS** of size 2. For each of the given statements, determine whether it is **True** or **False**. Based on the above data, answer the given subquestions.

According to the reduction rules for **DFVS**, the following figure shows a valid intermediate instance in the reduction with [[IMAGE:753fc3671e35dbfc_11_65]] . [[IMAGE:753fc3671e35dbfc_11_66]]