Discrete Mathematics Answers

4.      In Exercises i) and ii) determine whether the given graph has a Hamilton circuit. If it does, find such a circuit. If it does not, give an argument to show why no such circuit exists.

i)                    

ii)                 

3.      Proof that an undirected graph has an even number of vertices of odd degree.

2.      Describe at least one way to generate all the partitions of a positive integer n. (You can get idea from Exercise 49 in Section 5.3.)

1.      Discuss ways in which the current telephone numbering plan can be extended to accommodate the rapid demand for more telephone numbers. (See if you can find some of the proposals coming from the telecommunications industry.) For each new numbering plan you discuss, show how to find the number of different telephone numbers it supports.

Discuss ways in which the current telephone numbering plan can be extended to accommodate the rapid demand for more telephone numbers. (See if you can find some of the proposals coming from the telecommunications industry.) For each new numbering plan you discuss, show how to find the number of different telephone numbers it supports.

8 A bag of chocolates has 20 milk chocolates, 20 dark chocolates and 20 white chocolates. 

a) What is the minimum number of chocolates you must select at random from the bag to guarantee that you will get at least 5 of the same kind of chocolates?

b) What is the minimum number of chocolates you must select at random from the bag to guarantee that you will get at least 5 milk chocolates?

9 Usually, a person doesn’t drink more than 3000 mL of water per day.  On a regular day, there are 10,500 people on some university campus.  At least how many people on campus would drink the exact same amount of water (in mL) on that day?

5 a) Use merge sort to sort 6, 5, 17, 15, 16, 20, 18, 7 into increasing order.  Show all the steps in the algorithm (draw the trees as shown in class).

b) What is the number of comparisons used in the merge algorithm shown in class to merge the two lists: 5, 6, 7, 12, 15; and 1, 2, 9, 14,16.

c) In the merge algorithm, two lists in increasing order are merged into one (longer) list of increasing order.  Suppose two (sorted) lists are merged, one has 5 elements, the other has 6.  What is the least possible number of comparisons, and when does that occur?  What is the maximum possible number of comparisons?

7 a) Count the number of distinct phone numbers, if a valid phone number must have the format NXX-NXX-XXXX where N can be any integer between 3 and 8 inclusive, and X can be any integer between 0 and 9 inclusive.

b) How many bit strings of length 20 begin with 11 and end with 00?

1. a) Show or verify that 3 is a primitive root of the prime p=7.

b) Show that 2 is not a primitive root of 7.

c) Show the steps of the Diffie-Hellman key agreement protocol between Alice and Bob, assuming they use the prime 7 and its primitive root 3, and Alice’s secret integer is k1=5 and Bob’s secret integer is k2=4.

3 Consider the function f(n) = 2n2-5n+1.

a) What is the smallest value of n for which f(n)0 ?

b) Use mathematical induction to prove that f(n)0 for all n the value in part a). 

4 Write the pseudocode for a recursive algorithm to compute b3k, where b is a real number and k is a positive integer.  Use the fact that b3k+1=(b3k)3.

Suppose that G is a connected multigraph with 2k vertices of odd degree. Show that there exist k subgraphs that have G as their union, where each of these subgraphs has a Euler path and where no two of these subgraphs have an edge in common.

Which of the following pairs of statements are logically equivalent?

   I.   Statement 1: It is not true that both you have pneumonia and I got flu.

       Statement 2: Either you have no pneumonia or I have no flu.

   II.   Statement 1: It is not true that either I watched 'Crashlanding on You' or you watched 'Money Heist'.

       Statement 2: I did not watch 'Crashlanding on You' and you watched 'Money Heist'.

a) II only

b) I only

c) I and II

d) Neither I nor II