### Header Image

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

### Recent Comments

- In the Spotlight: MAT2540 – Discrete Structures and Algorithms II – The Open Road on Links
- 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

### Archives

### Categories

### Meta

## Final Test Review

Posted in Uncategorized
1 Comment

## Final Review_Javier_Joya

There are no answers to this as yet but I will probably post them Monday afternoon.Final_review

Posted in Final Exam Review
1 Comment

## Eric’s Final Review

Posted in Uncategorized
2 Comments

## Final Exam 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:

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.]

Posted in Final Exam Review
1 Comment

## Mergesort in python

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.

Posted in Discussion
1 Comment

## Upcoming important dates

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!!!

Posted in Final Exam Review, Homework, Project, Quizzes
Leave a comment

## Homework due and quiz #10 – Wednesday, May 18

5.1 #6, 18

5.2 #4, #12

Posted in Homework, Quizzes
Leave a comment

## Final Exam Review – OpenLab assignment

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.

Posted in Final Exam Review
3 Comments