discrete f3

If there is any reason why you do not want to answer the question (problem with attachment, bid price, ect.) please let me know.

Double Eulerian Tour

Use words to describe the solution process. No programming. 4. Suppose G is a graph. We define a double Eulerian tour as a walk that crosses each edge of G twice in different directions and that starts and ends at the same vertex. Show that every connected graph has a double Eulerian tour.

Composition Description of the Relation 'Less'

Given the relation "less" over the natural numbers N, describe the compositions as a set of the form {(x,y) | property}.

Give an example of a binary relation R such that R is irreflexive but R^2 (R squared) is not irreflexive, and give an example of a binary relation R such that R is antisymmetric but R^2 is not antisymmetric.

For each of the following properties, find a binary relation R such that R has that property but R^2 (R squared) does not: (a) irreflexive (b) antisymmetric

Use induction to prove finite set with n elements has 2^n subsets.

Use induction to prove that a finite set with n elements has 2^n subsets.

Equivalence Classes for Relation on N

5b. Describe the equivalence classes for the following relations on N. x~y iif x mod 2 = y mod 2 and x mod 4 = y mod 4

Prove that R is reflexive.

8. Let R be a relation on a set S such that R is symmetric and transitive and for each x ε S there is an element y ε S such that x R y. Prove that R is an equivalence relation (i.e. prove that R is reflexive)

Analyzing an Algorithm

For the following algorithm find the number of times the addition operation (+) is executed during the running of the program. Answer the question by giving a formula in terms of n: for i := 1 to n do for j := 1 to i do x := x + f(x) od; x := x + g(x) od

Analyzing an Algorithm

For the following algorithm find the number of times the assignment statement (:=) is executed during the running of the program. Answer the question by giving a formula in terms of n: i := 1; while i < n + 1 do i := i + 2; for j := 1 to i do S od od

Permutations and Combinations

We wish to form a committee of 7 people chosen from 5 democrats, 4 republicans, and 6 independents. The committee will contain 2 democrats, 2 republicans, and 3 independents. In how many ways can we choose the committee?