Name:__________________________________________________ UFID:____________________________ 1 COT 3100 Spring 2010 Practice for Midterm 2 For the first two questions #1 and #2, do ONLY ONE of them. If you do both, only question #1 will be graded. 1. (20 pts) Give iterative and recursive algorithms for reversing a bit string. 2. (20 pts) Give iterative and recursive algorithms for calculating the ℎ term of the sequence * + where . Which algorithm is more efficient and why?Name:__________________________________________________ UFID:____________________________ 2 3. (10 pts.) Use mathematical induction to show that ( ) , whenever n is a positive integer. 4. (20 pts) Let ( ) . Use induction to show that a) ∑ for .Name:__________________________________________________ UFID:____________________________ 3 b) ( ) ( ). 5. (10 pts) Give the recursive definition of the sequence {an}, n = 1,2,3,… if a. b. ( ) 6. (10 pts) How many ways are there to seat 6 people around a circular table, where seatings are considered to be the same if they can be obtained from each other by rotating the table?Name:__________________________________________________ UFID:____________________________ 4 7. (20 pts) Show that among any group of 20 people (where any two people are either friends or enemies), there are either four mutual friends or four mutual enemies.Name:__________________________________________________ UFID:____________________________ 5 8. (10 pts) Find the error in this "proof" of the clearly false claim: "n lines can divide the plane into regions". "Proof": Let P(n) be the statement that "n lines in the plane can divide the plane into regions". We will try to prove that P(n) is true for n ≥ 1. 1. Basis step: P(1) is true due to the obvious fact. 2. Inductive step: Assume that P(k) is true. 3. Consider the case when there are k+1 lines. Suppose the first k lines have the same position as in the P(k). And the additional line can divide every region to two regions. 5. Then, P(k+1) is true, since .Name:__________________________________________________ UFID:____________________________ 6 Bonus questions: 1. (5pts) Show that ( ) ( ) ( ) ( ) is ( ) 2. (5 pts) Let x be an irrational number. Show that for some positive integer j not exceeding n, the absolute value of the difference between jx and the nearest integer to jx is less than