1035 Words5 Pages

Math 471
Problem 1.
Group Work #8
Fall 2011
(a): Find a recurrence relation for the number tn of bit strings of length n that contain three consecutive zeros. SOLUTION: We break up all of the bit strings of length n according to the following nonoverlapping cases: • Bit Strings Beginning with “1”: In this case, the three consecutive zeros must appear in the last n − 1 slots, and there are tn−1 bit strings that will have three consecutive zeros there. • Bit Strings Beginning with “01”: In this case, the three consecutive zeros must appear in the last n − 2 slots, and there are tn−2 bit strings that will have three consecutive zeros there. • Bit Strings Beginning with “001”: In this case, the three consecutive zeros must appear in the*…show more content…*

SOLUTION: We observe directly that t1 = t2 = 0 and t3 = 1. Now according to the relation in (a), t4 = 1 + 0 + 0 + 21 = 3. Likewise, t5 = 3 + 1 + 0 + 22 = 8, t6 = 8 + 3 + 1 + 23 = 20, and t7 = 20 + 8 + 3 + 24 = 47. So the answer is 47. Problem 2. Find a recurrence relation for un , the number of bit strings of length n that do not contain two consecutive zeros, by (a): using the recurrence relation zn for the number of bit strings of length n that do contain two consecutive zeros. SOLUTION: We simply observe that all strings of length n either do or don’t have two consecutive zeros; mathematically, this means that zn +un = 2n . Hence, un = 2n −zn = 2n −(zn−1 +zn−2 +2n−2 ). (b): by reasoning from scratch. SOLUTION: We break up bit strings of length n into two cases: • Bit strings beginning with 1: There are un−1 ways to ﬁnish such a string such that there are no two consecutive*…show more content…*

Adding the two cases above, we arrive at the answer: un = un−1 + un−2 . (c): Use either (a) or (b) to determine the number of bit strings of length 7 that do not contain two consecutive zeros. SOLUTION: We note directly that u1 = 2 and u2 = 3. Then u3 = 2 + 3 = 5, u4 = 3 + 5 = 8, u5 = 5 + 8 = 13, u6 = 8 + 13 = 21, and u7 = 13 + 21 = 34. Problem 3. A country uses as currency coins with values of 1 peso, 2 pesos, 5 pesos, 10 pesos and bills with values of 5 pesos, 10 pesos, 20 pesos, 50 pesos, and 100 pesos. Find a recurrence relation for the number of ways bn to pay a bill of n pesos (for n ≥ 101) if the order in which the coins and bills are paid matters. SOLUTION: We break bn up according to which coin or bill was used ﬁrst. If we start with a 1 peso coin, then there are bn−1 ways to ﬁnish paying the bill. If we start with a 2 peso coin, then there are bn−2 ways to ﬁnish paying the bill. If we start with a 5 peso coin, then there are bn−5 ways to ﬁnish paying the bill. And so on. The ﬁnal answer is bn = bn−1 + bn−2 + 2bn−5 + 2bn−10 + bn−20 + bn−50 + bn−100

SOLUTION: We observe directly that t1 = t2 = 0 and t3 = 1. Now according to the relation in (a), t4 = 1 + 0 + 0 + 21 = 3. Likewise, t5 = 3 + 1 + 0 + 22 = 8, t6 = 8 + 3 + 1 + 23 = 20, and t7 = 20 + 8 + 3 + 24 = 47. So the answer is 47. Problem 2. Find a recurrence relation for un , the number of bit strings of length n that do not contain two consecutive zeros, by (a): using the recurrence relation zn for the number of bit strings of length n that do contain two consecutive zeros. SOLUTION: We simply observe that all strings of length n either do or don’t have two consecutive zeros; mathematically, this means that zn +un = 2n . Hence, un = 2n −zn = 2n −(zn−1 +zn−2 +2n−2 ). (b): by reasoning from scratch. SOLUTION: We break up bit strings of length n into two cases: • Bit strings beginning with 1: There are un−1 ways to ﬁnish such a string such that there are no two consecutive

Adding the two cases above, we arrive at the answer: un = un−1 + un−2 . (c): Use either (a) or (b) to determine the number of bit strings of length 7 that do not contain two consecutive zeros. SOLUTION: We note directly that u1 = 2 and u2 = 3. Then u3 = 2 + 3 = 5, u4 = 3 + 5 = 8, u5 = 5 + 8 = 13, u6 = 8 + 13 = 21, and u7 = 13 + 21 = 34. Problem 3. A country uses as currency coins with values of 1 peso, 2 pesos, 5 pesos, 10 pesos and bills with values of 5 pesos, 10 pesos, 20 pesos, 50 pesos, and 100 pesos. Find a recurrence relation for the number of ways bn to pay a bill of n pesos (for n ≥ 101) if the order in which the coins and bills are paid matters. SOLUTION: We break bn up according to which coin or bill was used ﬁrst. If we start with a 1 peso coin, then there are bn−1 ways to ﬁnish paying the bill. If we start with a 2 peso coin, then there are bn−2 ways to ﬁnish paying the bill. If we start with a 5 peso coin, then there are bn−5 ways to ﬁnish paying the bill. And so on. The ﬁnal answer is bn = bn−1 + bn−2 + 2bn−5 + 2bn−10 + bn−20 + bn−50 + bn−100

Related

## Unit 3 Assignment 1: Homework - Pt1420

608 Words | 3 Pagesdefault value as 0 to uninitialized variables 3. Write assignment statements that perform the following operations with variables a, b and c. set b = a+2 set a = b*4 set b = a/3.14 set a= b-8 4. Write assignment statements that perform the following operations with the variables a, b, and c. a. Adds 2 to a and stores the result in b b. Multiplies b times 4 and stores the result in a c. Divides a by 3.14 and stores the result in b d. Subtracts 8 from b and stores the result in at a. Set result = x + y = 4+8= 12 b.

## Real World Radical Formulas

517 Words | 3 PagesThe inches value shall be converted into decimal division. C = 4d -1/3b C= 4(23,245)-1/3 *(13.5) I plug in the given variables using the order of operations, the exponents will be solved first. C= 4(.035)*(13.5) – Multiply C= .14(13.5) Simplify C= 1.89 – the capsize value is less than 2 b) Solving for D in order to solve this equation I will be using the same formula that was given in the previous problem. C = 4d -1/3b 4d -1/3 b = c c Flipping equation so d is on the left. 4d -1/3 b = c 4d - 13 b = c Divide both sides by 4 and b.

## Steps To Solving A Linear System In Three Variable

829 Words | 4 PagesChoose which variable you want to eliminate; the coefficients of the variables must be exact opposites. You will only use two equations at one time. Second add the two equations together to cancel out your variables. IF nothing cancels than you have to multiply one or both of your equations by a number that will create an equal. Then for the unused equation and any of the other two equations repeat steps above.

## Nt1210 Unit 1 Rfeview Questions

1378 Words | 6 PagesCan be used to represent one character in the lowercase English alphabet c. Represents one binary digit d. Represents four binary digits 2. Which of the following terms means approximately 106 bytes? a. Terabyte b. Megabyte c. Gigabyte d. Kilobyte 3. Which answer lists the correct number of bits associated with each term? a.

## Pt1420 Unit 3 Assignment

545 Words | 3 PagesWhat value is stored in uninitialized variables? * Some languages assign a default value as 0 to uninitialized variables. Algorithm Workbench Review Questions: 3-10 3. Write assignment statements that perform the following operations with the variables a, b, and c. * Adds 2 to a and stores the result in b * Set b= 2 +a * Multiplies b times 4 and stores the result in a * set a= b*4 * Divides a by 3.14 and stores the result in b * set b= 3.14/b * Subtracts 8 from b and stored the result in a * set a= b-8 4. Assume the variables result, w, x, y, and z are all integers, and that w = 5, x = 4, y = 8, and z = 2.

## 200 Final Exam

1237 Words | 5 PagesSTAT 200 Final Exam Fall OL2 Click Link Below To Buy: http://hwaid.com/shop/stat-200-final-exam-fall-ol2/ 1. True or False. Justify for full credit. (15 pts) (a) If the variance of a data set is zero, then all the observations in this data set are zero. (b) If P(A) = 0.4 , P(B) = 0.5, and A and B are disjoint, then P(A AND B) = 0.9.

## Mat 540 Week 1 Assignment

1004 Words | 5 PagesGiven any input (a0,a1,a2,…a2n-1 describe the permutation of the leaves of the recursion tree. (Hint: write indices in binary and see what the relationship is of the bits of the ith element of the original sequence and the ith element of the resulting permutation of elements as they appear on the leaves on the recursion tree.) 3) Timing Problem in VLSI chips. Consider a complete balanced binary tree with n = 2k leaves. Each edge has an associate positive number that we call the length of this edge (see picture below).

## Lab 1.1 Essay

280 Words | 2 PagesRandy Michael NT 1210 Lab 1.1 Professor Chibuzo Onukwufor 4/1/15 Lab 1.1 1: Convert the decimal value 127 to binary. Explain the process of conversion that you used. Decimal Number | Binary Number | Remainder | 127 - | 64 | 63 | 63 - | 32 | 31 | 31 - | 16 | 15 | 15 - | 8 | 7 | 7 - | 4 | 3 | 3 - | 2 | 1 | 1 - | 1 | 0 | Binary | 27 | 26 | 25 | 24 | 23 | 22 | 21 | 20 | Decimal | 128 | 64 | 32 | 16 | 8 | 4 | 2 | 1 | Conversion | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | I took the decimal and divided it by two giving 1 for the remainders and 0 if it did not have a remainder. 2: Explain why the values 102 and 00102 are equivalent. They are equivalent because they represent the powers of 10 3: Based on the breakdown of the decimal and binary systems in this lab, describe the available digit values and the first four digits of a base 5 numbering system.

## Qnt 561 Final Exam Question with Answers.

1904 Words | 8 PagesFor what values of t will the null hypothesis not be rejected? a) To the left of -1.645 or to the right of 1.645 b) To the left of -1.345 or to the right of 1.345 c) Between -1.761 and 1.761 d) To the left of -1.282 or to the right of 1.282 2. Which of the following is a characteristic of the F distribution? a) Normally distributed b) Negatively skewed c) Equal to the t-distribution d) Positively skewed QNT 561 Final Questions and Answers QNT 561 Final Exam 3. For a chi-square test involving a contingency table, suppose the null hypothesis is rejected.

## MAT221: Introduction To Algebra Research Paper

271 Words | 2 PagesIt means a number that is more than one and I can only divide it by one, and has no remaining numbers. It is also becomes equal, when using prime factors. I divided starting with the small number, and then I finished until it was equal, a perfect square. I used the formula x^a X x^b=x 2x2x23 2x2x2x2x3x193 The prime factor is

### Unit 3 Assignment 1: Homework - Pt1420

608 Words | 3 Pages### Real World Radical Formulas

517 Words | 3 Pages### Steps To Solving A Linear System In Three Variable

829 Words | 4 Pages### Nt1210 Unit 1 Rfeview Questions

1378 Words | 6 Pages### Pt1420 Unit 3 Assignment

545 Words | 3 Pages### 200 Final Exam

1237 Words | 5 Pages### Mat 540 Week 1 Assignment

1004 Words | 5 Pages### Lab 1.1 Essay

280 Words | 2 Pages### Qnt 561 Final Exam Question with Answers.

1904 Words | 8 Pages### MAT221: Introduction To Algebra Research Paper

271 Words | 2 Pages