1. (20 points) Use Merge Sort to sort the sequence{f,d, c, h, a, i, b, e, g into
ID: 3185129 • Letter: 1
Question
1. (20 points) Use Merge Sort to sort the sequence{f,d, c, h, a, i, b, e, g into increasing (alphabetical) order. Show how the list is divided at each level of recursion all the way down to the maximum recursion level, and then indicate which lists are merged, and the result of each merge. Use Figure 2 in Section 5.4 of the textbook (p. 367) as a general guide; you may draw a similar figure, or answer in text form, as long as it's clear where the splits and merges occur 2. (a) (10 points) On a shelf there are 5 different Japanese books, 6 different Swahili books, and 8 different Sanskrit books. How many different ways are there to pick two books which are not both in the same language? (b) (10 points) How many different rectangles can be drawn on an 8 × 8 chessboard? Each rectangle can have height and width (which may differ) of 1 through 8 squares, and two rectangles are different if the subsets of chessboard squares that they each contain are not exactly the same 3. (a) (10 points) Suppose the numbers 1 through 10 are randomly positioned around a circle. Show that there are 3 consecutive numbers around the circle whose sum is at least 17 (b) (10 points) Show that in any set of seven distinct integers, there must exist two integers who sum or difference is a multiple of 10 4. A committee is to be formed from a set of 7 professors and 4 students. How many ways are there to form the committee if (a) (4 points) The committee consists of 3 professors and 2 students? b) (4 points) The committee can be of any non-zero size, but must have equal num bers of professors and students? c) (4 points) The committee has 4 members, and one must be Professor Plum? d) (4 points) The committee has 4 members, and at least 2 are professors? (e) (4 points) The committee has 4 members, and both Professor Plum and student Ms. Scarlett cannot both be on the committee 5. Ten different people walk into a delicatessen to buy sandwiches. Four of these people always order a Rueben sandwich, two always order a pastrami sandwich, two always (a) (7 points) How many different sequences of sandwich purchases are possible for b) (7 points) How many different unordered collections of sandwich purchases are 6. (6 points) How many different sequences of nine decimal digits exists that have exactly order a grilled cheese, and two pick randomly from the three types of sandwich this group, when the order of purchases matters? possible for this group? twice as many odd digits as even digits?Explanation / Answer
2.a) We can pick one Japanese book and one Swahili book in (5C1*6C1) ways ,i.e., 30 ways.
We can pick one Japanese book and one Sansjrit book in (5C1*8C1) ways ,i.e., 40 ways.
We can pick one Sanskrit book and one Swahili book in (8C1*6C1) ways ,i.e., 48 ways.
Therefore, there are (30+40+48) ways ,i.e., 118 ways to pick two books which are not both in the same language.
b) Given, each rectangle can have height and width of 1 through 8 squares which may differ.
Then, we can make rectangle in 2 ways. (2x4 and 4x2)
There are (64/8) = 8 rectangles in a chess board.
Therefore, (8*2) = 16 different rectangles can be drawn on an 8x8 chess board.
4) a) The required way to form the committee if it consists of 3 professors and 2 students is = 7C3*4C2 = 210.
b) The required way to form the committee if it consists of any non-zero size, but must have equal numbers of professors and students is = 7C1*4C1+7C2*4C2+7C3*4C3+7C4*4C4 = 329.
c) The required way to form the committee if it consists of 4 members and one must be professor plum is =
6C3*4C0+6C2*4C1+6C1*4C2+6C0*4C3 = 120.
d) The required way to form the committee if it consists of 4 members and at least 2 are professors is =
7C2*4C2+7C3*4C1+7C4*4C0 = 301.
e) The required way to form the committee if it consists of 4 members and both professor plum and student Ms. Scarlett cannot both be on the committee is = (6C3*3C0+6C2*3C1+6C1*3C2+6C0*3C3)*2 = 168.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.