Answer to Question #272589 in Discrete Mathematics for dv13

Question

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?

Answer 1

7.

a)

number of ways for N:

$n_1=6^2=36$

number of ways for X:

$n_2=10^8$

total number of ways:

$n=n_1n_2=36\cdot10^8$

b)

$n=2^{20-4}=65536$

5.

a)

Merge sort is a recursive algorithm that continually splits a list in half. If the list is empty or has one item, it is sorted by definition (the base case). If the list has more than one item, we split the list and recursively invoke a merge sort on both halves. Once the two halves are sorted, the fundamental operation, called a merge, is performed. Merging is the process of taking two smaller sorted lists and combining them together into a single, sorted, new list.

Divide the unsorted list into n sublists, each comprising 1 element (a list of 1 element is supposed sorted).

Now, we combine them in exactly the same manner as they were broken down. We first compare the element for each list and then combine them into another list in a sorted manner.

b)

Number of total comparison in merge sort:

$n\lceil lgn \rceil -2^{\lceil lgn \rceil}+1$

Number of total comparison for n = 10:

$10\lceil lg10 \rceil -2^{\lceil lg10 \rceil}+1=10\cdot4-2^4+1=25$

c)

The minimum number of comparisons for the merge sort occurs, assuming a sane implementation once one of the lists has been fully traversed:

$nlgn-n+1$

for n= 11:

$11lg11-11+1=11\cdot 3.46-11+1=28.06\approx 28$ comparisions

maximum possible number of comparisons:

$nlgn+n+O(lgn)$

Merge sort's best case takes about half as many iterations as its worst case

so, maximum possible number:

$28\cdot2=56$ comparisions