MATH 311 (Discreet Math Questions)

mth_311.docx

Home >Mathematics homework help >MATH 311 (Discreet Math Questions)

1. How many ways are there to rearrange the letters in FUNCTION?

2. How many ways are there to rearrange the letters in INANENESS?

3. Refer to Example 4.40. An urn contains nine red balls, nine white balls, and nine blue balls, and sample of four balls is drawn at random without replacement. Compute the probability that all of the balls in the sample are the same color. (Round your answer to four decimal places.)

4. In a suitable font, the letters A, H, I, M, O, T, U, V, W, X, Y are all mirror images of themselves. A string made from these letters will be a mirror image of itself if it reads the same backward as forward: for example, MOM, YUMMUY, MOTHTOM. If a four-letter string in these letters is chosen at random, what is the probability that this string is a mirror image of itself? (Round your answer to four decimal places.)

5. An urn contains six red balls, five white balls, and four black balls. Three balls are drawn from the urn at random without replacement. For each red ball drawn, you win $4, and for each black ball drawn, you lose $6. Let X represent your net winnings. Compute E(X), your expected net winnings.

E(X) =

6. The following figure consists of 7 horizontal lines and 14 vertical lines. The goal of this problem is to count the number of rectangles (squares are a kind of rectangle, but line segments are not).

WebAssign Plot

Let V be the set of all sets of two vertical lines, and let H be the set of all sets of two horizontal lines. Let R be the set of all rectangles in the figure. Define a function

f : R → V × H

transform arrow

({AB, CD}, {AC, BD}).

Compute |R|, the number of rectangles in the figure.

7. Suppose you have ten squares of stained glass, all of different colors, and you would like to make a rectangular stained glass window in the shape of a 2 × 5 grid.

WebAssign Plot

How many different ways can you do this, taking symmetry into account? (Note that any pattern may be rotated 180°, flipped vertically, or flipped horizontally. You should count all the possible resulting patterns as the same window.)

8. Is it possible for a graph with 10 vertices and 55 edges to be simple?

YesNo

Explain:

9. Suppose that 100 lottery tickets are given out in sequence to the first 100 guests to arrive at a party. Of these 100 tickets, only 14 are winning tickets. The generalized pigeonhole principle guarantees that there must be a streak of at least l losing tickets in a row. Find l. l =

10. A multiple choice test consists of eight questions, each of which has four choices. Each question has exactly one correct answer. William guesses randomly at each answer. What is the probability that he gets six or fewer questions correct? (Round your answer to four decimal places.)

11. Consider the following algorithm.

for i {1, 2, 3, 4} do
	beep
	for j {1, 2, 3} do
		beep
	for k {1, 2, 3, 4} do
			for l {1, 2, 3, 4, 5, 6} do
				beep
			for m {1, 2, 3, 4, 5} do
				beep

1. How many times does a beep statement get executed?

12. Consider the following algorithm.

x ← 1
for i {1, 2, 3} do
	for j {1, 2, 3, 4, 5} do
		x ← x + x
	for k {1, 2, 3, 4} do
		x ← x + 1
		x ← x + 5

2. Count the number of + operations done by this algorithm.

13. An urn containing n balls can be represented by the set

U = {b1, b2, ... , bn}.

Interpret the following algorithm in the context of urn problems. Does it represent drawing with or without replacement? How many lines does it print?

for i {1, 2, ... , n} do
	for j {1, 2, ... , n} do
		for k {1, 2, ... , n} do
			print bi, bj, bk

The algorithm prints out all the possible ways to draw balls in sequence, replacement. It prints

1. lines.

14. For the algorithm below, compute the number of multiplications performed, as well as the final value of s.

p ← 1
s ← 0
for i {1, 2, 3, 4} do
	p ← p · 2
	s ← s + p
number of multiplications
final value of s	s =

15. Let x1, x2, ... , xn

be an array. Consider the following algorithm.

for i {1, 2, ... , ⌊ n/2 ⌋} do
		t ← xi
		xi ← xn − i + 1
		xn − i + 1← t

(a) How many "←" operations does this algorithm perform?

⌊ n/2 ⌋

3 · ⌊ n/2 ⌋

3n/2

(b) What does this algorithm do to the array?

It shifts the first element to the end of the array and every other element one place to the left.

It shifts the last element to the beginning of the array and every other element one place to the right.

It adds 1 to each element of the array.

It reverses the order of the elements in the array.

It subtracts 1 from each element of the array.

16. Write a pseudocode algorithm to compute the product of the first n positive integers. How many multiplications does your algorithm perform?

17. Give a postcondition for the following algorithm that completely describes how the final value of i is related to x.

Precondition: x is a positive odd integer.

i ← 0

while

i < x

i ← i + 2

i =

18. Consider the following pseudocode function.

function Crunch(x R)
	if x ≥ 100 then
		return x/100
	else
		return x + Crunch(10 · x)

(a) Compute Crunch(5). Crunch(5) = (b) What happens if you try to compute Crunch(−22)? What does this suggest about an appropriate precondition for this function?

19. Write a recursive function in pseudocode that computes the value of the following recurrence relation:

H(n) =

1	if n = 1
H(n − 1) + 6n − 6	if n > 1.

Give descriptive preconditions and postconditions.

precondition

postcondition

H(n) =

20. Consider the following pseudocode function.

function W(n Z)
	if n > 0 then
			if n is odd then
				return 2n
			else
				return n + 1
	else
		return n − 1

Compute the values returned by the following function calls.

(a) W(12) = (b) W(−19) = (c) W(7) =

How many ways are there to rearrange the letters in FUNCTION?

How many ways are there to rearrange the letters in INANENESS?

Refer to Example 4.40. An urn contains

nine

red balls,

nine

white balls, and

nine

blue balls,

and sample of

four

balls is drawn a

t random without replacement.

Compute the probability that all of the balls in the sample are the same color. (Round your

answer to four decimal places.)

In a suitable font, the letters A, H, I, M, O, T, U, V, W, X, Y are all mirror images of

themselves.

A string made from these letters will be a mirror image of itself if it reads the

same backward as forward: for example, MOM, YUMMUY, MOTHTOM. If a four

letter string

in these letters is chosen at random, what is the probability that this string is a mirro

image of itself? (Round your answer to four decimal places.)

An urn contains

six

red balls,

five

white balls, and

four

black balls.

Three

balls are drawn

from the urn at random without replacement. For each red ball drawn, you win

, and

for each black

ball drawn, you lose

. Let

represent your net winnings.

Compute

(

), your expected net winnings.

(

) =

The following figure consists of

horizontal lines and

vertical lines. The goal of this

problem is to co

unt the number of rectangles (squares are a kind of rectangle, but line

segments are not).

Let

be the set of all sets of two vertical lines, and let

be the set of all sets of two

horizontal lines. Let

be the set of all rectangles in the figure. Def

ine a function

({

}, {

}).

Compute |

|, the number of rectangles in the figure.

Suppose you have

ten

squares of stained glass, all of different colors, and you would like to

make

a rectangular stained glass window in the shape of a

grid.

1. How many ways are there to rearrange the letters in FUNCTION?

2. How many ways are there to rearrange the letters in INANENESS?

3. Refer to Example 4.40. An urn contains nine red balls, nine white balls, and nine blue balls,

and sample of four balls is drawn at random without replacement.

Compute the probability that all of the balls in the sample are the same color. (Round your

answer to four decimal places.)

4. In a suitable font, the letters A, H, I, M, O, T, U, V, W, X, Y are all mirror images of

themselves. A string made from these letters will be a mirror image of itself if it reads the

same backward as forward: for example, MOM, YUMMUY, MOTHTOM. If a four-letter string

in these letters is chosen at random, what is the probability that this string is a mirror

image of itself? (Round your answer to four decimal places.)

5. An urn contains six red balls, five white balls, and four black balls. Three balls are drawn

from the urn at random without replacement. For each red ball drawn, you win $4, and

for each black ball drawn, you lose $6. Let X represent your net winnings.

Compute E(X), your expected net winnings.

E(X) =

6. The following figure consists of 7 horizontal lines and 14 vertical lines. The goal of this

problem is to count the number of rectangles (squares are a kind of rectangle, but line

segments are not).

Let V be the set of all sets of two vertical lines, and let H be the set of all sets of two

horizontal lines. Let R be the set of all rectangles in the figure. Define a function

f : R ? V × H

({AB, CD}, {AC, BD}).

Compute |R|, the number of rectangles in the figure.

7. Suppose you have ten squares of stained glass, all of different colors, and you would like to

make a rectangular stained glass window in the shape of a 2 × 5 grid.