Final Exam List all the functions from the three element set {1, 2, 3} to the set {a, b}
Final Exam
List all the functions from the three element set {1, 2, 3} to the set {a, b}. Which functions, if any, are one-to-one? Which functions, if any, are onto?How many base 10 numbers have 3 digits? How many three-digits numbers have no two consecutive digits equal? How many have at least one pair of consecutive digits equal?Suppose you are choosing participants for a panel discussion on allowing alcohol in campus. You must choose four administrators from a group of 10 and four students from a group of 20. In how many ways can this be done?Define a binary relation S from R to R as follows: for all (x, y) Î R x R, x S y Û x |y.Is (2, 4) Î S? Is (4, 2) Î S? Is (2, 2) ÎS? Is (–2) S (-8).Find the set of all elements u with the property that (2, u) Î S.Find the set of all elements v with the property that (1, v) Î S.In how many ways can you pass out k identical apples to n children if each child must get at least one apple?Write a negation, the contrapositive, the converse and inverse for the following statement:Determine if the statements (r Ú p) Ù ((~ r Ú (p Ù q)) Ù ( r Ú q) and p Ù q are logically equivalent. Justify your answer using truth table below (You may not need to use all of the columns in the skeleton table.)
| p | q | r | ||||||||
| T | T | T | ||||||||
| T | T | F | ||||||||
| T | F | T | ||||||||
| T | F | F | ||||||||
| F | T | T | ||||||||
| F | T | F | ||||||||
| F | F | T | ||||||||
| F | F | F |
- Use truth tables to show that the following forms of argument are invalid:
- The statements (p ®q) and q are both true, thus, it follows p is true as well (converse error).
- The statements (p ®q) and (~p) are both true, thus, it follows ~q is true as well (inverse error).
- Rewrite the statement The product of odd integers is odd. with all quantifiers (including any in the definition of odd integers) explicitly stated as “for all” or ”there exist.”
- Prove that for any integers m and n, if m is odd and n is odd, then mn is odd.
- Prove by induction that for all integers 13 + 23 + 33 + … + n3 = n2(n+1)2/4
- When paying off a loan with initial amount A and monthly payment M at an interest rate of p percent, the total amount T(n) of the loan after n months is computed by adding p/12 percent to the amount due after n-1 months and then subtracting the monthly payment M. Convert the description into a recurrence for the amount owed after n months. Solve the recurrence derived.
- Are there graphs with v vertices and v-1 edges that are no trees? Give a proof or justify your answer with a counterexample.
- The diagram below is a rooted tree; the root is indicated.
- What is the level of the vertex indicated by the circle?
- What is the height of the tree?
- Draw a binary tree, height 4, with 17 terminal vertices or explain why no such a tree exists.
- How many vertices does a complete binary tree of height n have? Prove it. Hint: Starting from height 1, 2, and 3, derive a relation (h(n)) of the height (h) depending on the number of nodes (n) and prove it by induction.
- How many Binary Search Trees can be constructed given 3 keys (say 1, 2 and 3)? Draw them (or explain the parent-child relationship for each; or provide the preorder traversal for each).
Given the graph:Which vertices are adjacent to vertex G?Which edges are adjacent to EG?Is there any Eulerian circuit in the graph? Find one or explain why not.List 3 loops that start at A.Find a spanning tree starting at node AFind all minimal spanning trees of the graph below.For the graph below, find:
An elementary path;
A simple path;
A path which is not simple;
A simple path which is not elementary;
A simple circuit;
A circuit which is not simple.
- For the graph below, find if it has an Eulerian circuit. If not, explain why. If yes, find one.
Looking for a Similar Assignment? Order now and Get 10% Discount! Use Coupon Code "Newclient"
