1. Use pseudocode to describe an algorithm that takes a list of n integers a1, a2, . . ., an and finds the number of integers which are greater than 5 in the list.

2. Use pseudocode to descibe an algorithm to find the largest and second largest elements in a list of integers.

3. Give a big-O estimate for the number of operations (where an operation is an addition or a multiplcation) used in this segment of an algorithm:

t:= 0

for i:= 1 to 3

for j:= 1 to 4

t:= t+ij

Explain your answer.

4. Show that f(n) = x2+x+1 is O(x2)

5. Solve: an = 4an-1-4an-2; a0 = 1 a1 = 1 (recuurence relation)

6. Solve: an = 5an-1 + 6an-2; a0=7 an= 16 (reccurence relation)

7. Suppose f(n)= f(n/3)+1 where n is a positive integer divisible by 3 and f(1) = 1. Find f(3), f(9), f(27), f(2187).

8. Find a closed form for the generating function for each of these sequences.

a) 0, 0, 0, 1, 1, 1, 1, 1, 1, …

b) 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, …

c) 1, 1, 0, 1, 1, 1, 1, 1, 1, 1…

9. Solve using generating functions: ak=3ak-1+2; a0=1

10. Prove: 1 + 3 + 5 +···+ (2n − 1) = n2 (induction)

11. Use strong induction to show that every positive integer n can be written as a sum of distinct powers of two, that is, as a sum of a subset of the integers 20 = 1, 21 = 2, 22 = 4, and so on. [Hint: For the inductive step, separately consider the case where k + 1 is even and where it is odd. When it is even, note that (k + 1)/2 is an integer.]

### Header Image

Creative Commons image courtesy of Flickr user StormPetrel1-
### Recent Posts

### Recent Comments

- OpenLab Workshop for Opening Gateways Fellows | 2018-2019 Opening Gateways Faculty Seminar on Final Exam Review
- Eric on Eric’s Final Review
- Kate Poirier on Hints/reminders from today’s class
- Kate Poirier on Final Exam Review
- Kate Poirier on Final Exam Review

### Archives

### Categories

### Meta

Nice questions, Cindy! I especially like #5.