UW-Madison MATH 240 - Exam 1 (12 pages)

Previewing pages 1, 2, 3, 4 of 12 page document View the full content.
View Full Document

Exam 1



Previewing pages 1, 2, 3, 4 of actual document.

View the full content.
View Full Document
View Full Document

Exam 1

57 views

Problems/Exams


Pages:
12
School:
University of Wisconsin, Madison
Course:
Math 240 - Introduction to Discrete Mathematics
Introduction to Discrete Mathematics Documents

Unformatted text preview:

Exam 1 A Miller Spring 2002 Math 240 1 Show all work Circle your answer No notes no books no calculator no cell phones no pagers no electronic devices at all Solutions will be posted shortly after the exam www math wisc edu miller m240 Name Problem Points Score 1 6 2 6 3 6 4 6 5 6 6 6 7 6 8 5 9 5 10 8 11 8 12 8 13 8 14 8 15 8 Total 100 Exam 1 A Miller Spring 2002 Math 240 1 6 pts Show that p q and q p are logically equivalent 2 6 pts Construct a truth table for the following propositional sentence p q p r 2 Exam 1 A Miller Spring 2002 Math 240 3 3 6 pts Find a statement which is logically equivalent to x P x y Q y but in which the negation sign appears if at all only in front of the predicate symbols 4 6 pts Let A 1 2 and B 1 3 5 Find A B Exam 1 A Miller Spring 2002 5 6 pts Let A 1 3 4 B 2 4 and C 3 4 5 6 Find a A b B C c A B C 6 6 pts Let f R R be defined by f x bxc Let S 2 5 Find f 1 S Math 240 4 Exam 1 A Miller Spring 2002 Math 240 5 7 6 pts Compute the following double sum 2 X 3 X i j i 1 j 1 8 5 pts How large a problem can be solved in 10 seconds or less using an algorithm that when input n requires f n n2 bit operations where each bit operation is carried out in 10 9 seconds Exam 1 A Miller Spring 2002 Math 240 6 9 5 pts The value of the Euler function at the positive integer n is defined to be the number of positive integers less than or equal to n that are relatively prime to n Find 12 10 8 pts What is smallest positive integer k such that the function f n n log n 1 2 is O nk Exam 1 A Miller Spring 2002 Math 240 11 8 pts Show that 2n 2n 1 for all integers n 3 12 8 pts Let fn be the nth element of the Fibonacci sequence Prove that f1 f3 f5 f2n 1 f2n for every positive integer n 7 Exam 1 A Miller Spring 2002 13 8 pts Find a 2 2 matrix A so that 1 2 1 0 A 0 1 3 2 Hint Solve a system of linear equations Math 240 8 Exam 1 A Miller Spring 2002 Math 240 14 8 pts Let n ak ak 1 a2 a1 a0 2 be any positive integer written in binary Let E be the set of even k such that ak 1 and let O be the set of odd



View Full Document

Access the best Study Guides, Lecture Notes and Practice Exams

Loading Unlocking...
Login

Join to view Exam 1 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 Exam 1 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?