Class

Date

Event

Details

(1)

Aug 31, 2011

1st Class

(2)

Sep 7, 2011

(3)

Sep 14, 2011

(4)

Sep 21, 2011

Quiz 1

(5)

Sep 28, 2011

(6)

Oct 5, 2011

(7)

Oct 12, 2011

EXAM I

Exam I

(8)

Oct 19, 2011

(9)

Oct 26, 2011

(10)

Nov 2, 2011

(11)

Nov 9, 2011

Quiz 2

(12)

Nov 16, 2011

Nov 23, 2011

No Class

Thanksgiving Vacation

(13)

Nov 30, 2011

(14)

Dec 7, 2011

EXAM II

& Review

On everything covered in class that was not on Exam I.

(15)

Dec 14, 2011

FINAL EXAM

On everything covered during the entire semester. Problems will be like in the quizzes, hour exams (including samples), and the homework

Row

Sec

Problems are from the textbook or written out here.

Due

(1)

5.1

2, 7, 13, 16, 32, 61, 72, 76. Hint: For #72 & 76, the examples on pages 239 and 569 will help.

 9/07/2011

(2)

5.2

7, 11, 12. Use Mathematical Induction.

(3)

5.2

23, 27, 29. Hint: Try using Example 5.2.2 on page 251 & Example 5.2.4 on page 255.

(4)

5.6

2, 8, 14, 38a & 38b.

(5)

5.7

1c, 2b & 2d, 4, 23, 25

(6)

5.8

12, 14

(7)

4.1

3, 5, 8, 12, 27, 36, 50. [#50 requires directly applying the definitions of “even” and “odd,” instead of using well-known properties of even & odd numbers. Doing #50 shows how the well-known properties of even & odd numbers (in Example 4.2.3 on page 167) also follow from the definitions.]

(8)

4.2

2, 20, 28

(9)

4.3

3, 5, 16, 41

(10)

4.4

6, 21, 30, 35, 42

(11)

4.8,5.8

Write the Fibonacci no. F₄₀₀ in scientific notation, e.g. F₃₀ ≈ 1.35*10⁶. Using the textbook’s closed-form formula on page 324 is much faster algorithm than using the definition to calculate F₄₀₀... Note: Our textbook defines the Fibonacci sequence starting at F₀=1, while in many other texts & Wikipedia it is convenient to define the non-zero Fibonacci sequence starting at F₁=1.

(12)

4.8

12, 20, 25. On #20(b), don’t worry too much about syntax. Just describe the steps actually needed to produce the desired output.

(13)

4.8

Find GCD(98741, 247021).

(14)

4.8

Observe: 247,710 ² - 38,573 ²

  = 61,360,244,100 - 1,487,876,329

  = 59,872,367,771 = 260,867*229,513.

Now factor 260,867 in a non-trivial way.

(15)

1.2

#1; #4, #7 b, e, f; #9 c, d, e, f, g, h; #12

(Section 1.2 fits with Ch. 6 on Set Theory.)

(16)

6.1

#7 b; #12 a, b, g-j; #13; #18

(17)

6.2

9, 14, 23(c), 32.

Venn-Diagram solutions are OK except on 6.2.14, use the “is an element of” method. Any Venn-Diagram solutions based on shading will NOT be accepted, because often shading is confusing and unconvincing. Instead, number regions and calculate a Venn-Diagram set as a set of regions, like we do in class.

(18)

6.3

2, 4, 7, 13

(19)

6.3

Prove or disprove:

(i) ∃ sets A, B & C such that (A-B)-C = (A-C)-(B-C),

(ii) ∀ sets A, B & C, (A-B)-C = (A-C)-(B-C).

(20)

6.3

20, 21

(21)

6.1

Of a population of students taking 1-3 classes each, exactly: 19 are taking English, 20 are taking Comp Sci, 17 are taking Math, 2 are taking only Math, 8 are taking only English, 5 are taking all 3 subjects, and 7 are taking only Computer Science. How many are taking exactly 2 subjects?

(22)

1.3

15 c, d, e; 17; 20. These problems fit with Chapter 7 on Functions.

(23)

7.1

2; 7; 8 c, d, e; 14; 51 d, e, f [skip logarithms]

(24)

7.2

8, 13(b), 17, 18

(25)

7.1

5

(26)

7.3

2, 4, 11, 17

(27)

1.3

2, 6. These problems fit with Chapter 8 on Relations.

(28)

8.1

4, 11, 20

(29)

8.2

2, 10, 13, 14, 16

(30)

8.3

9; 12; 15 b, c, d; 21. For #9, define “the sum of the elements” of the empty set to be 0. On #21, just say how many equivalences classes there are and describe each class.

(31)

8.4

2, 4, 5, 8, 12b, 13b, 21. Hint on 12b & 13b: If we call the hundred’s digit “h,” the tens digit “t,” and the unit’s digit “u,” then the 3-digit base-10 number htu = h*10^2+t*10+u. Now reduce the 10's (mod 9) in problem 12. Reduce (mod 11) in problem 13. The same approach works no matter how many digits a positive integer has.

(32)

8.4

Calculate 17⁴⁰ (mod 83,523). Your answer should be between 0 and 83,522.

(33)

8.4

17, 18, 20, 23, 27, 32, 38, 42

(34)

8.4

Calculate 2³⁷⁴ (mod 367). Hint: 367 is prime, so we can shortcut with the Little Fermat Theorem 8.40.10.

(35)

8.4

37, 38, 40. Hint: The decryption exponent is the answer from #38 because 713 = 23*31, 660=(23-1)(31-1), and x⁶⁶⁰ = 1 (mod 713) when gcd(x, 660)=1.

(36)

8.4

Under RSA: p = 13, q = 17, n = 221, & e = 37 is the encryption exponent. Find the decryption exponent d.

(37)

8.4

Solve for x: x² = 4 (mod 675,683). Give all 4 solutions. Your answers should be between 0 & 675,682. Note: 675,683 = 821 * 823, the product of 2 prime numbers.

(38)

8.4

Find the integer x satisfying: 1 ≤ x ≤ 2,622,187,

x = 510 (mod 661), and x = 479 (mod 3967)

(39)

10.1

4, 19, 20, 28, 29, 34

(40)

10.2

8 b, c, d; 9; 10

(41)

10.4

#4, #11 & #13. On 4, 11, & 13, explain why the given pair of graphs cannot be isomorphic. Hint on 13: Look for circuits of length 5.

#15. Hint on 15: There are 11 non-isomorphic simple graphs with 4 vertices.

Note: In this class we use only an intuitive definition for graphs to be “isomorphic,” because the technical definition is so impractical to use. See the last paragraph on page 678. However, we use the technical (and practical) definition for isomorphism when using the Chinese Remainder Theorem. The CRT-isomorphism exposes the modular-arithmetic weakness used today for attacking RSA.

(42)

10.5

3, 15, 16, 17, 18

(43)

10.6

15, 16, 17, 18

(44)

2.1

15, 33, 43

(45)

2.2

2, 15, 27

(46)

2.3

10, 11

(47)

9.5

6, 9, 14