Queries to a database of student records at a college

Problem 1E A group of 10 people begin a chain letter, with each person sending the letter to four other people. Each of these people sends the letter to four additional people. a) Find a recurrence relation for the number of letters sent at the nth stage of this chain letter, if no person ever receives more than one letter. ________________ b) What are the initial conditions for the recurrence relation in part (a)? ________________ c) How many letters are sent at the nth stage of the chain letter?

Problem 7E How many ways are there to form these postages using the rules described in Exercise 6? a) 12 cents ________________ b) 14 cents ________________ c) 18 cents ________________ d) 22 cents

Problem 5E Messages are sent over a communications channel using two different signals. One signal requires 2 microseconds for transmittal, and the other signal requires 3 microseconds for transmittal. Each signal of a message is followed immediately by the next signal. a) Find a recurrence relation for the number of different signals that can be sent in n microseconds. ________________ b) What are the initial conditions of the recurrence relation in part (a)? ________________ c) How many different messages can be sent in 12 microseconds?

Problem 3E Every hour the U.S. government prints 10,000 more $1 bills, 4000 more $5 bills, 3000 more $10 bills, 2500 more $20 bills. 1000 more $50 bills, and the same number of $100 bills as it did the previous hour. In the initial hour 1000 of each bill w ere produced. a) Set up a recurrence relation for the amount of money produced in the nth hour. ________________ b) What are the initial conditions for the recurrence relation in part (a)? ________________ c) Solve the recurrence relation for the amount of money produced in the nth hour. ________________ d) Set up a recurrence relation for the total amount of money produced in the first n hours. ________________ e) Solve the recurrence relation for the total amount of money produced in the first n hours.

Problem 8E Find the solutions of the simultaneous system of recurrence relations an = an ? 1 + b n – 1 bn = an ? 1 ? b n – 1 with a0 = 1 and b0 = 2.

Problem 9E Solve the recurrence relation an = if a0 = 1 and a1 =2. [Hint: Take logarithms of both sides to obtain a recurrence relation for the sequence log an, n = 0. 1.2......]

Problem 10E Solve the recurrence relation if a0 = 2 and a1 = 2. (See the hint for Exercise 9.)

Problem 12E Find the solution of the recurrence relation an= 3an?1 ? 3an?2 + an?3 if a 0 = 2, a1 =2, and a2 = 4.

Problem 11E Find the solution of the recurrence relation an = 3an?1 – 3an ? 2 + an - 3 + 1 if a0 = 2, a1 = 4, and a2 = 8.

Problem 14E In this exercise we construct a dynamic programming algorithm for solving the problem of finding a subset S of items chosen from a set of n items where item i has a weight wi , which is a positive integer, so that the total weight of the items in S is a maximum but does not exceed a tixed weight limit W. Let M(j. w) denote the maximum total weight of the items in a subset of the first j items such that this total weight does not exceed w. This problem is known as the knapsack problem. a) Show that if wj > w, then M(j, w) = M(j ? 1, w). ________________ b) Show that if wj ? w, then M (j, w) = max ( M ( j ? 1, w), wj + M (j — 1. w — wj)). ________________ c) Use (a) and (b) to construct a dynamic programming algorithm for determining the maximum total weight of items so that this total weight does not exceed W. In your algorithm store the values M(j, w) as they are found. ________________ d) Explain how you can use the values M(j. w) computed by the algorithm in part (c) to find a subset of items with maximum total weight not exceeding W. In Exercises 15-18 we develop a dynamic programming algorithm for finding a longest common subsequence of two sequences a1, a2,....,am and b1,b2,..., bn, an important problem in the comparison of DNA of different organisms.

Problem 13E Suppose that in Example I of Section 8.1 a pair of rabbits leaves the island after reproducing twice. Find a recurrence relation for the number of rabbits on the island in the middle of the nth month.

Problem 15E Suppose that c1,c2,...., cp is a longest common subsequence of the sequences a1,a2,...., am and b1,b2,...., bn. a) Show that if am = bn, then cp = am = bn and c1,c2,..., cp-1 is a longest common subsequence of a1, a2,..., am-1 and b1,b2,.... bn-1 when p > 1. ________________ b) Suppose that am ? bn. Show that if cp ? am,then c1,c2,....cp is a longest common subsequence of a1, a2,..., am-1 and b1 ,b2...... bn and also show that if cp ? bn. then c1. c2...... cp is a longest common subsequence of a1.a2..... am and b1.b2....,bn-1.

Problem 16E Let L (i. j) denote the length of a longest common subsequence of a1.a2 ......ai and b1.b2..... bj. where 0 ? i ? m and 0 ? j ? n. Use parts (a) and (b) of Exercise 15 to show that L(i. j) satisfies the recurrence relation L(i. j) = L (i?1 . j ?1) + 1 if both i and j are nonzero and ai = bi. and L(i. j) = max (L(i. j ? 1), L (i – 1, j)) if both i and j are nonzero and ai? bi, and the initial condition L(i. j) = 0 if i= 0 or j =0.

Problem 17E Use Exercise 16 to construct a dynamic programming algorithm for computing the length of a longest common subsequence of two sequences a1.a2 ....am and b1 , b2 ...... bn, storing the values of L(i. j) as they are found.

Problem 19E Find the solution to the recurrence relation f (n) = f(n/2) + n2 for n = 2k where k is a positive integer and f (1) = 1.

Problem 18E Develop an algorithm for finding a longest common subsequence of two sequences a1,a2....... am and b1,b2....... bn using the values L(i. j) found by the algorithm in Exercise 17.

Problem 20E Find the solution to the recurrence relation f (n) = 3 f (n/5) + 2n4, when n is divisible by 5. for n = 5k, where k is a positive integer and f (1) = 1.

Problem 21E Give a big-O estimate for the size of f in Exercise 20 if f is an increasing function.

Problem 23E Give a big-O estimate for the number of comparisons used by the algorithm described in Exercise 22.

Problem 22E Find a recurrence relation that describes the number of comparisons used by the following algorithm: Find the largest and second largest elements of a sequence of n numbers recursively by splitting the sequence into two subsequences with an equal number of terms, or where there is one more term in one subsequence than in the other, at each stage. Stop when subsequences with two terms are reached.

Problem 24E A sequence a1,a2...... an is unimodal if and only if there is an index m, 1 ? m ? n, such that ai < ai+1 when 1 ? i < m and ai >ai+1 when m ? i < n. That is, the terms of the sequence strictly increase until the mth term and they strictly decrease after it, which implies that am is the largest term. In this exercise, am will always denote the largest term of the unimodal sequence a1, a2,.....an. a) Show that am is the unique term of the sequence that is greater than both the term immediately preceding it and the term immediately following it. ________________ b) Show that if ai < ai + 1 where 1 ? i < n, then i + I ? m ? n. ________________ c) Show that if ai > ai + i where 1 ? i < n, then 1 ? m ? i. ________________ d) Develop a divide-and-conquer algorithm for locating the index m. [Hint: Suppose that i < m < j. Use parts (a), (b), and (c) to determine whether ?(i + j)/2? + 1 ? m ? n, 1 ? m ? ?( i + j ) /2? ? 1, or m = ?(i + j)/2?.]

Problem 25E Show that the algorithm from Exercise 24 has worst-case time complexity O (log n) in terms of the number of comparisons. Let {an} be a sequence of real numbers. The forward differences of this sequence arc defined recursively as follows: The first forward difference is ?an = an+1 ? an: the (k + 1)st forward difference ?k+1 an is obtained from ? k an by ?k + 1an = ?kan + 1 ? ?kan.

Problem 26E Find ?an, where a) an = 3. ________________ b) an = 4n + 7. ________________ c) an = n2+ n + 1.

Problem 27E Let an = 3n3 + n + 2. Find ?kan, where k equals a) 2. ________________ b) 3. ________________ c) 4.

Problem 29E Let {an} and {bn} be sequences of real numbers. Show that ? (anbn) = an+1(?bn) + bn (?an).

Problem 28E Suppose that an = P(n), where P is apolynomial of degree d. Prove that ?d+1an= 0 for all nonnegative integers n.

Problem 30E Show that if F(x) and G(x) are the generating functions for the sequences {ak} and {bk}, respectively, and c and d are real numbers, then (cF + dG) (x) is the generating function for {cak + dbk}.

Problem 31E (Requires calculus) This exercise shows how generating functions can be used to solve the recurrence relation (n +1)an+1 = an + (1 /n!) for n ? 0 with initial condition a0=1. a) Let G(x) be the generating function for {an}. Show that G'(x) = G(x) + ex and G(0) = 1. b) Showfrompart (a) that (e? xG(x))' = 1, andconclude that G(x) = xex + ex. c) Use part (b) to find a closed form for an.

Problem 32E Suppose that 14 students receive an A on the first exam in a discrete mathematics class, and 18 receive an A on the second exam. If 22 students received an A on either the first exam or the second exam, how many students received an A on both exams?

Problem 33E There are 323 farms in Monmouth County that have at least one of horses, cows, and sheep. If 224 have horses, 85 have cows, 57 have sheep, and 18 farms have all three types of animals, how many farms have exactly two of these three types of animals?

Problem 34E Queries to a database of student records at a college produced the following data: There are 2175 students at the college, 1675 of these are not freshmen. 1074 students have taken a course in calculus, 444 students have taken a course in discrete mathematics, 607 students are not freshmen and have taken calculus, 350 students have taken calculus and discrete mathematics, 201 students are not freshmen and have taken discrete mathematics, and 143 students are not freshmen and have taken both calculus and discrete mathematics. Can all the responses to the queries be correct?

Problem 35E Students in the school of mathematics at a university major in one or more of the following four areas: applied mathematics (AM), pure mathematics (PM). operations research (OR), and computer science (CS). How many students are in this school if (including joint majors) there are 23 students majoring in AM; 17 in PM: 44 in OR; 63 in CS; 5 in AM and PM; 8 in AM and CS; 4 in AM and OR; 6 in PM and CS; 5 in PM and OR; 14 in OR and CS; 2 in PM, OR, and CS; 2 in AM, OR, and CS; 1 in PM. AM. and OR; 1 in PM, AM, and CS: and 1 in all four fields.

Problem 36E How many terms are needed when the inclusion- exclusion principle is used to express the number of elements in the union of seven sets if no more than five of these sets have a common element?

Problem 37E How many solutions in positive integers are there to the equation x1 + x2 + x3 = 20 with 2 < x1 < 6, 6 < x2 < 10, and 0 < x3 < 5?

Problem 38E How many positive integers less than 1,000,000 are a) divisible by 2, 3, or 5? ________________ b) not divisible by 7, 11. or 13? ________________ c) divisible by 3 but not by 7?

Problem 39E How many positive integers less than 200 are a) second or higher powers of integers? ________________ b) either primes or second or higher powers of integers? ________________ c) not divisible by the square of an integer greater than 1? ________________ d) not divisible by the cube of an integer greater than 1 ? ________________ e) not divisible by three or more primes?

Problem 40E How many ways are there to assign six different jobs to three different employees if the hardest job is assigned to the most experienced employee and the easiest job is assigned to the least experienced employee?

Problem 41E What is the probability that exactly one person is given back the correct hat by a hatcheck person who gives n people their hats back at random?

Problem 43E What is the probability that a bit string of length six chosen at random contains at least four 1 s?

Problem 42E How many bit strings of length six do not contain four consecutive 1s?