99年國立成功大學電機所電通所離散數學

//the recursive algorithm finds the largest and smallest elements in a sequence.
Input: s_i, …, s_j, i and j
Output: large (the largest element in the sequence), small (the smallest element in the sequence)

.

Let b_n be the number of comparisons (lines 10 and 14) required for an input of size n.
Please answer the following questions.

1.

Establish the recurrence relation of b_n.

//the recursive algorithm finds the largest and smallest elements in a sequence.
Input: s_i, …, s_j, i and j
Output: large (the largest element in the sequence), small (the smallest element in the sequence)

.

Let b_n be the number of comparisons (lines 10 and 14) required for an input of size n.
Please answer the following questions.

2.

Find b₁ and b₂.

//the recursive algorithm finds the largest and smallest elements in a sequence.
Input: s_i, …, s_j, i and j
Output: large (the largest element in the sequence), small (the smallest element in the sequence)

.

Let b_n be the number of comparisons (lines 10 and 14) required for an input of size n.
Please answer the following questions.

3.

Solve the recurrence relation in case n is a power of 2 to obtain b_n = 2n − 2, n = 1, 2, 4, ….

4.

Prove

Figure 1 gives a graph with six nodes and thirteen edges. Each edge is associated with a weight. Please answer the questions in the following:

5.

Decide whether the graph has an Euler cycle. If the graph has an Euler cycle, exhibit one; otherwise, briefly explain why it does not.

Figure 1 gives a graph with six nodes and thirteen edges. Each edge is associated with a weight. Please answer the questions in the following:

6.

Determine whether the graph is planar. If the graph is planar, redraw it so that no edges cross; otherwise, show why it is not planar.

Figure 1 gives a graph with six nodes and thirteen edges. Each edge is associated with a weight. Please answer the questions in the following:

7.

Find a minimal spanning tree using Prim's algorithm (suppose the source node is a).

Given a transport network, the source is a and the sink is z.

8.

Fill in the missing edge flows so that the result is a flow in the network.

Given a transport network, the source is a and the sink is z.

9.

Find the maximum flow and show the resulting edge flows.

Given a transport network, the source is a and the sink is z.

10.

Find the minimum cut cut(P, P') by showing the nodes in P.

A = B = {1, 2, 3}; R = {(1, 1), (1, 2), (2, 3), (3, 1)}; S = {(2, 1), (3, 1), (3, 2), (3, 3)}. Let R and S be relation from a set A to a set B. Compute

11.

A = B = {1, 2, 3}; R = {(1, 1), (1, 2), (2, 3), (3, 1)}; S = {(2, 1), (3, 1), (3, 2), (3, 3)}. Let R and S be relation from a set A to a set B. Compute

12.

S⁻¹

A = R and ≤ denotes the usual partial order B = {x | x is a real number and 5 ≤ x < 6}.Find, if it exists,

13.

all lower bounds of B;

A = R and ≤ denotes the usual partial order B = {x | x is a real number and 5 ≤ x < 6}.Find, if it exists,

14.

the least upper bound of B.

15.

Using Karnaugh-map to simplify the Boolean function F = A'B'C' + B'CD + A'BC'D'; + AB'C'

16.

Simplify the following Boolean function into product of sums form F(A, B, C, D) = Σ(0, 1, 2, 5, 8, 9, 10)

17.

Consider the encoding function f defined below. How many errors will f detect?
f(000) = 00000000
f(001) = 10111000
f(010) = 00101101
f(011) = 10010101
f(100) = 10100100
f(101) = 10001001
f(110) = 00011100
f(111) = 00110001