CS1370 Discrete Mathematics and Its Applications II Summer 2022

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

CS1370 B

Standard Examination: Summer 2022

Discrete Mathematics and Its Applications II

Section A Answer TWO questions

1. (a) Solve the following recurrences. In each case, assume that T(c) = Θ(1) for all constants c > 0. Justify your answers.

i. T(n) = 2 · T(n/3) + Θ(n). [3]

ii. T(n) = 16 · T(n/4) + Θ(n 2 ). [3]

iii. T(n) = 4 · T(n/2) + Θ(n). [3]

iv. T(n) = 2 · T(n/2) + Θ(n log n). [3]

(b) We are given as input:

• An array A[1 . . . n] whose entries are real numbers.

We have to output YES if there exist distinct indices i, j, k ∈ [n] such that A[i] + A[j] = A[k], and we have to output NO otherwise. Design an algorithm for this problem, and analyse its worst case asymptotic running time. Try to ensure that this running time is as small as possible. [6]

(c) We are given as input:

• A n × n matrix M ∈ Rn×n whose entries are distinct real numbers. We denote the entry in the i th row and j th column of M as Mi,j . For each j ∈ [n], let ij ∈ [n] be the index such that Mij ,j is the minimum entry in the j th column of M (i.e., we have Mij ,j < Mi,j for all i ∈ [n] \ {ij}). The matrix M satisfifies the property that ij < ij 0 for all j, j0 ∈ [n] with j < j0 .

Design an algorithm for computing mini∈[n],j∈[n] Mi,j and analyse its worst case asymp-totic running time. Try to ensure that this running time is as small as possible. [7]

2.    (a)  Consider the following graphs: G1  = (V, E1 ), G2  = (V, E2 ), G3  = (V, E3 ), where V = nv1 , v2 , v3 , v4 , v5 }, E1  = n(v1 , v2 ), (v1 , v4 ), (v2 , v3 ), (v2 , v4 ), (v2 , v5 ), (v4 , v5 )}, E2   = n(v1 , v4 ), (v1 , v5 ), (v2 , v5 ), (v3 , v4 ), (v3 , v5 ), (v4 , v5 )}, and furthermore, E3   = E2 U n(v2 , v3 )} \ n(v2 , v5 )}. For each of the following statements, explain whether it is true or false. Justify your answers.

i. The graphs G1 and G2 are isomorphic. [3]

ii.  The graphs G1 and G3 are isomorphic.                                                                [3]

iii.  The graphs G2 and G3 are isomorphic.                                                                [3]

iv.  The size of minimum vertex cover in G1 is 3.                                                     [3]

(b)  Consider a bipartite graph G = (L U R, E) where each edge e e E has one endpoint in L and the other endpoint in R. For any set of nodes X C L, define N﹐ (X) := nv e R :  there is an edge (u, v) e E for some u e X}. The graph G has the property that |N﹐ (A)| > |A|/3 for all A C L. Is the following statement true or false?

•  There is a subset of edges H C E, of size |H| = |L|, such that every node u e L is incident upon exactly one edge from H and every node v e R is incident upon at most 3 edges from H.

Justify your answer.                                                                                                      [6]

(c)  Consider a graph G = (V, E) where every node v  e V has degree at most 3, and there is an integer t > 0 such that d(u, v) < t for all u, v e V. Here, d(u, v) denotes the distance (the length of the shortest path) between u and v in G. Is the following statement true or false?

•  It must be the case that |V | < 3 . 2t .

Justify your answer.                                                                                                      [7]

3.    (a)  Consider the graph G = (V, E), with node-set V = nv1 , v2 , v3 , v4 , v5 } and edge-set E  = n(v1 , v2 ), (v1 , v4 ), (v2 , v3 ), (v2 , v4 ), (v2 , v5 ), (v4 , v5 )}.  For any subgraph G\  of G, let d﹐ \ (u, v) denote the distance between nodes u, v e V in G\ . For each of the following statements, explain whether it is true or false. Justify your answers.

i. There exists a spanning tree T of G where maxu,v∈V dT (u, v) = 2. [3]

ii.  There exists a spanning tree T of G where minunveTnuv dG (u, v) = 2.            [3]

iii.  The graph G admits an Euler walk.                                                                     [3]

iv.  The graph G is bipartite.                                                                                       [3]

(b)  Consider any simple graph G = (V, E) where every node v e V has degree = d, for some integer 1 < d < |V | - 1. For each of the following statements, explain whether it is true or false. In each case, justify your answers.

i.  There must exist a partition of the set E into d mutually disjoint matchings.  [3]

ii.  If G is bipartite, then there must exist a partition of the set E into d mutually disjoint matchings.                  [5]

(c)  Suppose that a set system A1 , A2 , . . . , A是 satisfies |nj(k)=1 Aij | >  k + 1 for every

or false?

• This set system has a system of distinct representatives in which x represents Ai . Justify your answer.            [5]

Section B Answer TWO questions

4.    (a)

For a positive integer d, a d-regular graph is a graph such that every node has degree exactly d. Prove that if d is odd and G is a d-regular graph, then the number of nodes

of G must be even.                                                 [9]

(b)

Suppose we shuffle a standard deck of cards (4 suits of 13 cards each) in such a way that every possible ordering of the cards is equally likely to be the outcome. What is the expected number of instances of consecutive pairs of cards of the same suit?   [8]

(c)

Let E, F, G be non-empty events in a discrete probability space. State whether the following is true or false:

• If E and F are independent, F and G are independent, and E and F ∩ G are independent, then the events G and E ∩ F are independent.

Justify your answer.                     [8]

5.    (a)

Recall that a forest is a graph in which every connected component is a tree. Consider a forest on n nodes and k edges. How many connected components does it have? Justify your answer.                      [9]

(b)

What is the expected number of tosses of a fair coin until 3 consecutive Heads appear? [8]

(c)

Let E, F, G be non-empty events in a discrete probability space. Is the following statement true or false? If E and F are independent and E and G are independent,

then the events E and F U G are also independent. Justify your answer.                [8]


6.    (a)  For every X, k e N, let R(X, k) e N denote the smallest value such that every graph with at least R(X, k) nodes contains either an X-clique or an independent set on k nodes as an induced subgraph. Fix k, X e N. Give the values of the following:

ii.  R(X, 2).                                                                                                                   [6]

Justify both your answers.

(b)  An elevator operates in a building with 10 floors.  One day, n people get into the

elevator on the ground floor (Floor 0), and each of them chooses to go to a floor selected uniformly at random from 1 to 10. What is the expected number of floors in which exactly one person gets out? Justify your answer.         [8]

(c)  Let E, F, G be non-empty events in a discrete probability space.  State whether the following is true or false:

•  If E and F are independent, E and G are independent, and F ∩ G = 0, then the events E and F U G are independent.

Justify your answer.                                                                                                      [8]


2023-06-09