discrete math

1. Use decision trees to find a lower bound on the number of comparisons required to sort six items in the worst case.

The decision tree would be a binary tree.

It would contain n! leaves.

Equivalently it has at least 1+lg(n!) levels.

Worst case would be lg(n!).

n! = 6! = 720 = lg(720) = 9.49 = 10 comparisons

Give an algorithm that uses this number of comparisons to sort six items in the worst case.

2. Use Algorithm 10.2.4 to find a maximal flow in each network.

Algorithm 10.2.4 Finding a Maximal Flow in a Network

This algorithm finds a maximal flow in a network. The capacity of each edge is a nonnegative integer.

   Input:

A network with source a, sink z, capacity C, vertices a = v0, . . ., vn = z, and n

Output:

A maximal flow F

        max flow(a, z, C, v, n) {

            // v’s label is (predecessor(v), val(v))

            // start with zero flow

  1.       for each edge (i, j)

  2.           Fij = 0

  3.       while (true) {

               // remove all labels

  4.           for i = 0 to n {

  5.                predecessor(vi) = null

  6.                val(vi) = null

  7.           }

                // label a

  8.       predecessor(a) = —

  9.       val(a) = ∞

            // U is the set of unexamined, labeled vertices

10.     U = {a}

           // continue until z is labeled

11.     while (val(z) == null) {

12.          if (U == Ø) // flow is maximal

13.               return F

14.          choose v in U

15.           U = U −{v}

16.          Δ = val(v)

17.          for each edge (v, w) with val(w) == null

18.              if(Fvw < Cvw) {

19.                 predecessor(w) = v

20.                 val(w) = min{Δ, Cvw − Fvw}

21.                 U = U ∪ {w}

22.              }

23.          for each edge (w, v) with val(w) == null

24.              if(Fwv > 0) {

25.                 predecessor(w) = v

26.                 val(w) = min{Δ, Fwv}

27.                 U = U ∪ {w}

28.              }

29.     } // end while (val(z) == null) loop

          // find path P from a to z on which to revise flow

30.     w0 = z

31.     k = 0

32.     while (wk¬= a) {

33.          wk +1 = predecessor(wk)

34.          k = k + 1

35.     }

36.     P = (wk+ 1, wk, . . ., w1, w0)

37.     Δ= val(z)

38.     for i = 1 to k + 1 {

39.          e = (wi, wi −1)

40.          if (e is properly oriented in P)

41.               Fe = Fe + Δ

42.          else

43.               Fe = Fe − Δ

44.       }

45.    } // end while (true) loop

      }

3. Use Algorithm 10.2.4 to find a maximal flow in each network.

4. Refer to Figure 10.4.1, where we reverse the direction of the edges so that edges are directed from jobs to applicants. Show a maximal matching

5. Given Example 10.4.4 and Theorem 10.4.5 in the textbook, explain how you would transform the matching problem into a maximal flow problem.

6. Once you complete question 5 use the already known linear program that solves the maximal flow problem. Show all of your work and how you are doing the reduction.