MATH/CSE 1019 Final Examination
Fall 2011
December 17, 2011
Instructor: S. Datta
1. (2 points) Evaluate the infinite geometric series
9
10
+
9
100
+
9
1000
+ . . .
Note that the left hand side is 0.99 . . .. Use the answer above to fill in the blank below
Solution: This is a geometri...
mathcse 1019 final examination fall 2011 december 17
2011 instructor s datta 1 2 points evaluate the infinite geometric series 9 10 9 100 9 10
Written for
EECS 1028
All documents for this subject (2)
Seller
Follow
ExamsConnoisseur
Reviews received
Content preview
MATH/CSE 1019 Final Examination
Fall 2011
December 17, 2011
Instructor: S. Datta
1. (2 points) Evaluate the infinite geometric series
9 9 9
+ + + ...
10 100 1000
Note that the left hand side is 0.99 . . .. Use the answer above to fill in the blank below
a 0.9
Solution: This is a geometric series with a = 0.9 and r = 0.1. So the infinite sum is 1−r = 1−0.1 = 1.
0.99 . . . = 1.
2. (2 points) Express the following statement in predicate logic: “given any 2 distinct rational numbers, there
exists a rational number between them in value”.
Solution: Make the domain Q, the set of rational numbers. Then, the given statement is
∀x∀y[(x 6= y) → (∃z(x < z < y) ∨ (x > z > y))].
3. (2 points) Prove that if f : Z+ → Z, f (n) = n2 − 100n then f (n) ∈ Ω(n2 ).
Solution: Note that n2 − 100n ≥ n2 /2 if n ≥ 200. So we use n0 = 200, c = 0.5 in the definition of Ω(n2 )
and thus f (n) ∈ Ω(n2 ).
4. (2 points) What is the negation of ∀x∃yP (x) → Q(y). Your answer should not have negation symbols
before quantifiers and no implication symbols.
Solution: First we rewrite the given statement as ∀x∃y(¬P (x) ∨ Q(y)). Then we can negate this in the
usual way and get
∃x∀y(P (x) ∧ ¬Q(y))
5. (2 points) Write down the function that the following recursive algorithm computes and give a 1-sentence
justification for your answer. Assume that n is a positive integer.
Mystery(n)
1 if n = 1
2 then return 1
3 else return (n + Mystery(n − 1))
Pn n(n+1)
Solution: The program computes i=1 = 2 .
Each recursive call adds the previous number, stopping at 1, so it computes the sum n + (n − 1) + . . . + 2 + 1.
6. (3 points) Prove using induction the inequality n < 2n for all n >= 0, n ∈ Z.
Solution: We check that it is true for n = 0, 1 and then prove the rest using induction. It holds for n = 0, 1
because 0 < 20 = 1 and 1 < 21 = 2.
Base Case (n = 2): True because 2 < 22 = 4.
Inductive Step: Assume the statement is true for n = k. So k < 2k . Now for n = k + 1 we have
RHS = 2k+1
= 2 ∗ 2k
> 2k
> k + 1 for all k > 1.
This study source was downloaded by 100000850872992 from CourseHero.com on 04-10-2023 23:40:20 GMT -05:00
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller ExamsConnoisseur. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $7.99. You're not tied to anything after your purchase.
