Header ImageCreative Commons image courtesy of Flickr user StormPetrel1
There are no answers to this as yet but I will probably post them Monday afternoon.Final_review
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:
for i:= 1 to 3
for j:= 1 to 4
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.]
Professor Thiel will be covering our class next week while I’m away. Not all of you may know python, but it’s pretty easy to read even if you don’t know it. Professor Thiel has typed up mergesort in python and shared it with me so I could share it with you. If you’re still working on the code for your project due Monday, you may find this helpful.
You can see his code here.
Monday, May 16: Project due by 11:59pm (via email)
Wednesday, May 18: Quiz #10/HW #10 due
Monday, May 23: OpenLab Final Exam Review assignment due by 7:59am
Wednesday, May 25: Final exam day!!!
5.1 #6, 18
5.2 #4, #12
As announced in class today, your final OpenLab assignment is to create your own final exam and post it. You may make up questions yourself or you may copy them from
- previous tests
- homework and quizzes
- practice problems
The format for your actual final exam will be similar to the formats of your previous tests. Try to choose questions that cover a wide variety of topics. Try to choose questions of varying levels of difficulty. (One common mistake students make when studying is avoiding harder questions; so don’t forget to include some hard ones!) Most of the questions you’ve seen in class are appropriate exam questions; longer problems aren’t as long as they might seem if you’re not solving them for the first time.
You’re welcome to include questions you don’t already know how to solve, but you should at least try to solve them before Monday’s class. You’ll be invited to share your solutions after Monday’s class. Don’t forget to add the category Final Exam Review from the right-hand-side of the screen.
Your post is due by Monday, May 23 at 7:59am (right before class starts). As announced in class today, May 23’s class is officially a “review” class, but I will not prepare anything. My plan is to address any questions that have popped up in your studying that you have issues with. We’ll look at everyone’s exams as a group and address questions that pop up then too. Please come prepared to discuss specifics that day.