Prelim 1 Review Questions

Prelim 1 will be Tuesday, March 8th in the evening 7:30-9 pm in Upson B17.

This is a closed notes, closed book test!

Those with conflict with an other prelim should let us know ASAP, by sending email to eva@cs.cornell.edu. I sent an acknowledgement to all of you who already sent such an email (on Tuesday, March 1st). If you have not received an acknowledgement, please let me know again. Those with conflict will be allowed to take the exam early. Exact arrangements (time and room) will be emailed to you shortly.

Sam and Hari will hold a review session on Monday night, March 7th in UP 205. The review session will start at 7pm, the location will be announced here shortly. We will also rearrange office hour for the week to help prepare for the prelim. Please check the Web for the schedule.

The topics for the prelim cover the material of problem sets 1-5. You need to know:

functions we used, and how to compute with them (exponent, logarithm, ceiling, floor, mod)
summations and products, harmonic function H
logic concepts (such as P ® Q or P «Q, $, ", and negating statements)
circuits
proof methods (such as direct proof, contradiction, etc.)
proofs by induction (strong and weak induction)
recursively defined functions like Fibonacci numbers,
recursively defined algorithms, like Euclid's algorithm, modular exponentiation
Basic number theory (primes, prime decomposition, gcd, lcm)
Euclid's algorithm including the extended version writing the gcd as a linear combination of the two numbers
modular arithmetic, inverse mod a prime, and solving modular equations
Fermat's theorem,
RSA, and its applications

These topics are covered in Rosen sections 1.1-3, Sections 2.2-2.5, Sections 3.1-3.4. Unfortunately, exact section numbers and the content of each section depends on which edition of the book you own. Nothing will be tested that we did not have in class or homeworks. So your notes from class and the homework is a better guide than the book.

Here are a few questions from the book that would be useful for review. These are not meant to be handed in, and solutions will not be handed out (though some solutions are available at the back of the book). Feel free to ask about them during any office hours or the review session.

Question numbers from the 5th edition of the book. We'll post the corresponding numbers from the 4th edition will be posted shortly.

Review Questions and Supplementary Exercises from Section 1 (page 113-116): review questions 7, 11, and supplementary exercises 1, 10, 11, 13, 17, 18, 19.

Review Questions and Supplementary Exercises from Section 2 (page 208-210): review questions 3, 15, 16, 17 and supplementary exercises 20, 21, 23, 25

Review Questions and Supplementary Exercises from Section 3 (page 291-294): supplementary exercises 8, 13, 14, 16, 18, 25, 35, 40, 43.

Questions

Legend:
\forall   "
\geq   >= (greater than or equal to)
\leq   <= (less than or equal to)

The blank space in the question number space in the fourth edition of the book shows that the question is newly added in the fifth edition. In such a case, the exact statement of the question is reproduced in the last column.

Question in 4th edition	Question in 5th edition	Statement of the question
Chapter 1
Review 7	Review 7
	11	(a) Suppose that the statement of the form " P(x) is false. How can this be proved? (b) Show that the statement ``For every positive integer n, n^2 ≤ 2n'' is false.
Supplementary 1	Supplementary 1
6	10
7	11
	13	Use quantifiers to express the statement ``Everyone has exactly two biological parents'' using the propositional function P(n,y), which represents ``x is the biological parent of y.''
11	17
12	18
13	19
Chapter 2
	Review 3	(a) State the definition of the fact that f(n) is O(g(n)), where f(n) and g(n) are functions from the set of positive integers to the set of real numbers. (b) Use the definition of the fact that f(n) is O(g(n)) directly to prove or disprove that n^2+18n+107 is O(n^3). (c) Use the definition of the fact that f(n) is O(g(n)) directly to prove or disprove that n^3 is O(n^2+18n+107).
Review 10	15
11	16
12	17
Supplementary 6	Supplementary 20
7	21
9	23
11	25
Chapter 3
Supplementary 8	Supplementary 8
13	13
14	14
16	16
18	18
21	25
	35	Use mathematical induction to prove that if n people stand in a line, where n is a positive integer, and if the first person in the line is a woman and the last person in line is a man, then somewhere in the line there is a woman directly in front of a man.
	40	A unit or Egyptian fraction is a fraction of the form 1/n, where n is a positive integer. In this exercise, we will use strong nduction to show that a greedy algorithm can be used to express every rational number p/q with 0<p/q<1 as the sum of distinct unit fractions. At each step of the algorithm, we find the smallest positive integer n such that 1/n can be added to the sum without exceeding p/q. For example, to express 5/7 we first start the sum with 1/2. Since 5/7-1/2=2/14 we add 1/5 to the sum since 5 is the smallest positive integer k such that 1/k<3/14. Since 3/14-1/5=1/70, the algorithm terminates, showing that 5/7=1/2+1/5+1/70. Let T(p) be the statement that this algorithm terminate for all rational numbers p/q with 0<p/q<1. We will prove that the algorithm always terminates by showing that T(p) holds for all positive integers p. (a) Show that the basis step T(1) holds. (b) Suppose that T(k) holds for positive integers k with k<p. That is, assume that the algorithm terminates for all rational numbers k/4, where 1≤ k<p. Show that if we start with p.q and the fraction 1/n is selected in the first step of the algorithm, then p/q=p'/q'+1/n, where p'=np=q and q'=nq. After considering the case where p/q=1/n, use the induction hypothesis to show that the greedy algorithm terminates when it begins with p'/q' and complete the induction step.
31	43