(b)[7 points] Solve the time complexity of recurrence in the θ-notation without using Master method.

(a) [3 points! If ax ay (mod n), then x y (mod n).

(b) [3 points) If x  y (mod n), then ax  ay (mod n).

(c) [3 points) The set of integers and the set of prime nu umbers have the same cardinality.

(d) [3 points) If a relation is symmetric and transitive, then the relation is rellexive.

(e) [3 points] .

(f) [3 points] 5 dividesn5 - n whenever n is a positive integer.

(g) I points Given a,bent and gcdta, band gcd(a，b)≠ 1 , we cannot find an inverse of a modulo b in some cases.

(a) [6 points) Compute the expected number of vertices and edges that remain after the deletion process.

(b) I6 pointsI Based on Ca), ty to infer that for any graph with n vertices with nd/2 edges, there is an independent set with at least n/2d vertices.

3. A treed that never gave up on its dream to flourish. [10 points] Let T be a spanning tre n edge cost function c. T is defined to have the cycle property if for any edge the cycle generated by adding e' to T. Also, T is defined to have the cut property if for any edge for all e' in the cut defined by e. Show that the following three statements are equiva 1. T has the cycle property. 2. T has the cut property. 3. T is a minimun cost spanning tree.

110年 - 110台灣聯合大學系統_碩士班招生考試_電機類:離散數學#104950

110年 - 110 國立臺灣大學_碩士班招生考試_工程科學及海洋工程學研究所丁組:離散數學(A)#100758

109年 - 109 國立高雄大學_碩士班招生考試_資訊工程學系：離散數學#103285