DOC PREVIEW
Berkeley MATH 55 - Midterm

This preview shows page 1 out of 4 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 4 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 4 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

MATH 55, midterm test, Oct 3rd.NameStudent ID #All the necessary work to justify an answer and all the necessary steps of a proof must beshown clearly to obtain full credit. Partial credit may be given but only for significantprogress towards a solution. Show all relevant work in logical sequence and indicate allanswers clearly. Cross out all work you do not wish considered. Books and notes are allowed.Calculators, computers, cell phones, pagers and similar devices are not allowed during thetest.1. (8pts total; 2 pts each subitem) Find the negation of these statements:(a) Every student in this class knows calculus.(b) If it snows today, then I will go skiing tomorrow.(c) In every math class there is some student who falls asleep during lectures.(d) If it rains, you will need an umbrella.12. (12pts, 6pts for each subitem) The shaker sort successively compares adjacent pairs ofelements, exchanging them if they are out of order, and alternately passing through the listfrom the beginning to the end and then from the end to the beginning until no exchangesare needed.(a) Show the steps used by the shaker sort to sort the list2, 5, 1, 7, 9, 6.(b) Estimate the time complexity of this algorithm.23. (10pts total) Prove thatlnmm=n + m − 1mfor all positive integers n and m.34. (8pts total; 4pts for each subitem) Let k be a positive integer. Show that(a) 1k+ 2k+ · · · + nkis O(nk+1);(b) 1k+ 2k+ · · · + nkis Ω(nk).5. (10pts total) Show that (377− 1)/2 is odd and


View Full Document

Berkeley MATH 55 - Midterm

Download Midterm
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Midterm and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Midterm 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?