Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

EECS 376: Foundations of Computer Science

Fall 2025

Final Review Session 1

1 Poly-Time Mapping Reductions

1. For an undirected graph G = (V, E), a clique cover is a collection of cliques C = {C1, . . . , Ck} such that every vertex in the graph is included in at least one clique in C. In other words, the cliques in C “cover” all the vertices of G.

Consider the following language:

CLIQUE-COVER = {⟨G, k⟩ : G is an undirected graph that has a clique cover of size ≤ k}.

We emphasize that the size of a clique cover is the number of cliques in the collection, not the number of vertices in the cliques.

(a) Show that CLIQUE-COVER is NP-hard by defining a polynomial-time mapping reduction from COLORING. Recall that

COLORING = {⟨G, k⟩ : G is an undirected, k-colorable graph},

where a graph is k-colorable if each vertex can be colored with one of the k colors such that for any given edge (u, v), u and v have different colors.

Since COLORING is NP-hard, we can conclude that CLIQUE-COVER is also NP-hard.

Defer the correctness argument to the next part, but briefly argue that your reduction is efficient here.

(b) Prove that your reduction in Part a is correct.

2. Consider the language:

SUBGRAPH-ISOMORPHISM = {⟨G, H⟩ | G and H are undirected graphs, and G has a

subgraph G ′ such that G ′ is isomorphic to H}.

Recall that a subgraph G′ = (V ′ , E′ ) of G = (V, E) is a graph such that V ′ ⊆ V and E′ ⊆ E.

A graph G1 is isomorphic to G2 if they differ only in how their vertices are labeled. In other words, we can convert G1 to G2 just by changing labels on the vertices.

Briefly justify why SUBGRAPH-ISOMORPHISM is ∈ NP. Prove that SUBGRAPH-ISOMORPHISM is NP-Hard. Note that these imply that the language is NP-complete.

2 Randomness

1. The Bogosort algorithm is a randomized algorithm that attempts to sort an array A of n distinct integers by randomly rearranging the list and checking whether the resulting list is sorted. The algorithm repeats this procedure until the list is sorted.

Assuming that both generating a random permutation of the elements in A and checking whether A is sorted take O(n) time, derive the expected time complexity of Bogosort as a function of n.

2. Jett has started researching in biology, and is monitoring the weight of a mouse as part of his disease research. In his notebook he keeps track of the number of days that the weight of the mouse decreases from the previous day because it may be a sign of disease onset.

(a) If the change in weight from day to day of the mouse’s weight is a random variable that obeys a uniform distribution in the range (-1, 2), find the expected number of days that the weight of the mouse will decrease as a function of n, the total number of days in the experiment.

(b) If the change in weight of a healthy mouse obeys a uniform distribution from -1 to 2 grams and the change in weight of a diseased mouse obeys a uniform distribution from -3 to 1 grams, what is the expected value of the difference between the number of days that the weight of a diseased mouse decreases and the number of days that a healthy mouse decreases over a period of n days?

3. Recall that a triangle in an undirected graph G = (V, E) is a subset of vertices T = {u, v, w} ⊆ V of three (distinct) vertices where (u, v),(v, w),(w, u) ∈ E. A triangle is said to be colorful if its three vertices are assigned pairwise distinct colors.

The COLORFUL-TRIANGLE problem is: given a graph G, assign one of four available colors to each vertex so as to maximize the number of colorful triangles. In this problem, you will analyze a randomized algorithm that assigns a uniformly random and independent color from the four available colors to each vertex.

Note: Under a coloring with 4 colors, adjacent vertices may have the same color or different colors.

(a) Let XT be an indicator random variable for whether triangle T is colorful under the random assignment. Find Pr[XT = 1].

(b) Using the result from Part a, derive the approximation ratio the algorithm obtains for the COLORFUL-TRIANGLE problem, in expectation.

(c) Let Y be a random variable denoting the fraction of triangles that are colorful under the random coloring with 4 colors. Using Markov’s inequality, give a lower bound on the probability that Y ≥ 1/4.