96年私立長庚大學資管所離散數學

Determine the coefficient of

1.

x⁸y⁵ in (3x − 4y)¹³

Determine the coefficient of

2.

xyz⁻³ in (2x − 3y + z⁻¹)⁵

3.

Letbe a boolean expression over the two-valued Boolean algebra. Write f(w, x, y, z) in both disjunctive and conjunctive normal forms.

4.

Prove that is an integer.

5.

Prove that log₂(n!) = Θ(n log n) .

Let T(n) = Θ(f(n)). Drive f(n) in the simplest formula for the following T(n).

6.

T(n) = 3T(n / 2) + n² log n

Let T(n) = Θ(f(n)). Drive f(n) in the simplest formula for the following T(n).

7.

8.

For each of the following relations, determine whether the relation is reflexive, symmetric, and transitive.
(a) R is the relation on Z where a R b if a | b.
(b) R is the relation on Z × Z where (a, b) R (c, d) if a ≤ c.
(c) R is the relation on Z+ where x R y if x³ + y² is even.

9.

Design a finite state machine with {0, 1, 2} as its input alphabets and show the remainder of sum divided by 4. You must also show the state diagram.

Calculate the value of the following arithmetic expression:

10.

+ − × 245 + / × 362 × −235 (prefix form)

Calculate the value of the following arithmetic expression:

11.

542 × −2 × 63 / 32 × + + (postfix form)

12.

Let G = (V, E) be a connected, weighted graph and let v be a vertex in G. Suppose that the weights of the edges incident on v are distinct. Let e be the edge of minimum weight incident on v. Prove e must be contained n every minimum spanning tree.

13.

Show that the Petersen graph has no Hamiltonian cycle but it has a Hamiltonian path.