CSE312-Foundations of Computing II Solved

CSE 312: Foundations of Computing II

Assignment #1

 
Three families want to line up for a photo. Family A has 4 people, family B has 5 people, and family C has 2 people. In how many ways can they be arranged in a single line if ......there are no restrictions on the order?
...the members of each family must all be together (for instance, there cannot be a member of B between two members of A)?
...the members of family A must be together, but the others can be arranged in any order?
...the members of family C cannot be together, and the others can be arranged in any order?
Suppose you remove rJ, ♣Q, ♣J, qK, and qQ from a Schnapsen deck and arrange the remaining 15 cards in a single stack. How many arrangements of the cards are there in the stack if ...
...only the rank matters? For example, swapping the positions of two aces is considered the same arrangement.
...only the suit matters? For example, swapping the positions of two clubs is considered the same arrangement.
A piano octave consists of 12 notes in ascending order. Five of them are black key notes and seven are white key notes. (See http://www.smackmypitchup.com/smpu/content/ img/MT/mtp01.gif for a picture; the notes are ascending from left to right.) A composer is experimenting with the idea that a melody must be a sequence of 6 notes from this single octave, 2 of them black and 4 of them white. The notes of a melody need not be distinct:
you can use the same note 2 or more times. How many possible melodies are there if ...

...there are no further restrictions?
...the 4 white notes cannot all be adjacent in the melody?
...no note is allowed to be repeated?
...no note is allowed to be repeated and the white notes must be ascending in the melody?
(a) How many paths in the plane are there from point (0,0) to point (8,5) if every step increments one coordinate and leaves the other unchanged? (That is, from (i, j) you must go to either (i + 1, j) or (i, j + 1).)How many paths in the plane are there from point (8,5) to point (13,8) if every step increments one coordinate and leaves the other unchanged?
How many paths in the plane are there from point (0,0) to point (13,8) if every step increments one coordinate and leaves the other unchanged, and the path must go through the point (8,5)?
How many paths in the plane are there from point (0,0) to point (13,8) if every step increments one coordinate and leaves the other unchanged, and the path is not permitted to go through the point (8,5)?
You have 5 quarters left until graduation, and you want to take each of the following 10 courses, two per quarter: CSE 333, CSE 351, CSE 421, CSE 427, CSE 431, CSE 440, CSE 451, CSE 454, CSE 455, and CSE 461. Each course is offered every quarter, but you must obey the following prerequisite requirements:CSE 351 must be taken before CSE 333.
CSE 333 must be taken before CSE 451.
CSE 333 must be taken before CSE 455.
CSE 333 must be taken before CSE 461.
How many possible schedules are there?

A Quidditch team (three Chasers, two Beaters, one Keeper, and one Seeker) is to be chosen from a class of 12 wizards and 9 witches. (Every student is either a wizard or a witch, but cannot be both.) The Quidditch team must be composed of 4 wizards and 3 witches. If you choose a particular 7 students, changing their team positions is considered to change the team. But a Chaser is a Chaser and a Beater is a Beater, so swapping the two Beaters, for example, does not change the team.How many different teams are possible if each student can play any position?
How many different teams are possible if 2 of the 12 wizards only know how to be Seekers, but every other student can play any position?
How many different teams are possible if each student can play any position, but Harry, Hermione, Angelina, and Ron cannot all be chosen because, you know, it just wouldn’t be fair. (For this exercise, Harry and Hermione are wizards, and Angelina and Ron are witches.)
On a Friday, 14 students show up for Schnapsen. The Maestro wants to pair the 14 students into 7 pairs to play Schnapsen. The order of the pairs does not matter. How many ways are there to pair the students if ......there are no further restrictions?
...7 of the 14 are CSE 312 TAs, and the Maestro wants to pair each TA with a non-TA for teaching purposes?
...3 of the 14 are TAs, and the Maestro doesn’t want to pair any two TAs together?
...there are no TAs, but Harry and Hermione are among the 14 and they cannot be paired together, because they really don’t get along?
You sit down to a game of Schnapsen with the Maestro, who deals you the following hand:
♠ A r A

♣ —

q ATK

The face-up trump showing on the table is qJ and you are on lead at the very first trick. With this beautiful hand, you decide to close the stock immediately. You then lead your qA followed by your other 4 cards in a random order.

Are you guaranteed to take all the tricks?
What is the total number of possible starting hands for the Maestro in this deal?
Explain why you will lose this deal (that is, you will fail to accumulate at least 66 trick points in your tricks) if and only if the Maestro’s starting hand contains 18 or fewer trick points.
How many of the Maestro’s possible starting hands will cause you to lose this deal? (Do not enumerate all of them. Instead, use counting ideas in order to arrive at a simple way to solve this.)
What is the probability that you will lose this deal, evaluated to 3 significant digits?
Consider the following equation: a1+a2+a3+a4+a5+a6 = 70. A solution to this equation over the nonnegative integers is a choice of a nonnegative integer for each of the variables a1,a2,a3,a4,a5,a6 that satisfies the equation. For example, a1 = 15,a2 = 3,a3 = 15,a4 = 0,a5 = 7,a6 = 30 is a solution. To be different, two solutions have to differ on the value assigned to some ai. How many different solutions are there to the equation? (Hint: Think about splitting a sequence of 70 1’s into 6 blocks, each block consisting of consecutive 1’s in the sequence. The number of 1’s in the i-th block corresponds to the value of ai. Note that the i-th block is allowed to be empty, corresponding to ai = 0.)