Practice: a) How many permutations of {a,b,c,d,e,f,g} end with a? b) How many different ways are there to choose a president, vice president and treasurer out of 10 people? c) How many ways are there to choose a committee of 3 people out of ten people? Exercises: 1: How many positive integers between 5 and 31: 1.1) are divisible by 3? 1.2) are divisible by 4? 1.3) are divisible by 3 and 4? 2: How many bit strings of length 14 contain: 2.1) exactly four 1s? 2.2) at most four 1s? 2.3) at least four 1s? 2.4) an equal number of 0s and 1s? 3) If there is a room with 36 people and every person shakes hands with every other person exactly once, how many handshakes are there in all? 4) How many ways can a set of three positive integers less than 100 be chosen? 5) A professor writes 40 discrete mathematics true/false questions. Of the statements in these questions, 17 are true. If the questions can be positioned in any order, how many different answer keys are possible? 6) If a password is made up of lowercase letters or digits, how many passwords of length 6 are there that contain AT LEAST one digit? 7) How many permutations of the letters ABCDEFG contain - the string BCD? - the strings BA and GF? Recursion fix'em: //return the factorial of n public int factorial(int n){ if(n == 0) return 1; return factorial(n-1); } //return the factorial of n public int factorial(int n){ if(n == 0) return 0; return n * factorial(n-1); } //return the number at the nth index in the Fibonacci sequence public int fib(int n){ if(n == 0 || n == 1) return n; return fib((n-1) + (n-2)); } In class we solved the problem of finding the maximum element in an array using the following approach: The maximum in the array is the maximum of the first element, and the maximum in the rest of the array. An alternative approach is to divide the array into two equal parts and compute the maximum as the maximum over the two parts. Implement this approach! Do you expect one of these to work faster or slower than doing this with a for loop? Induction Let's get induction down. Prove using mathematical induction that For n >= 1, 1×2 + 2×3 + 3×4 + ... + (n)(n+1) = (n)(n+1)(n+2)/3 (a) What is the statement P(1)? (b) Show that P(1) is true (basis step). (c) What is the induction hypothesis? (d) What do you need to to prove in the inductive step? (e) Complete the inductive step. (f) Explain why these steps show that this formula is true for every positive integer n.