Class

Date

Event

Details

(1)

Aug 28, 2013

1st Class

(2)

Sep 4, 2013

(3)

Sep 11, 2013

(4)

Sep 18, 2013

Quiz 1

The questions will be like the questions in: (1) the homework, (2) the Sample Sequences & Progressions pdf on Blackboard, and (3) the sample quiz.

(5)

Sep 25, 2013

(6)

Oct 2, 2013

(7)

Oct 9, 2013

• Exam 1

• Lecture

Exam problems will be like on Sample Exam 1, Quiz 1, Sample Quiz 1, the Sample Sequences & Progressions pdf on Blackboard, and the homework.

(8)

Oct 16, 2013

(9)

Oct 23, 2013

(10)

Oct 30, 2013

(11)

Nov 6, 2013

Quiz 2

(12)

Nov 13, 2013

(13)

Nov 20, 2013

Nov 27, 2013

Thanksgiving Recess

(14)

Dec 4, 2013

• Exam 2

• Lecture

• Review

(15)

Dec 11, 2013

7:30 - 10:15 PM

FINAL EXAM

On everything covered during the entire semester. Problems will be like in the Sample Quizzes, Hour Exams, Sample Quizzes & Exams, and the homework.

Row

§

Problems are from the textbook or written out below.

Due

(1)

5.1

2, 7, 13, 16, 32, 61.

HW-1 9/4/2013

(2)

5.2

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

HW-1

9/4/2013

(3)

5.6

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

(4)

5.7

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

(5)

5.8

12, 14

(6)

4.1

3, 5, 8, 12, 27, 36, 50. [#50 requires directly applying the definitions of “even” and “odd” (on pg. 147) instead of using well-known properties of even & odd numbers. The point of #50 is to see how the well-known properties of even & odd numbers (to be summarized in §4.2 on page 167) are themselves based on the definitions of “even” and “odd.”]

(7)

4.2

2, 7, 20, 28

(8)

4.3

3, 5, 21, 41

(9)

4.4

6, 21, 25, 35, 42, 44

(10)

4.8

Find GCD(98741, 247021).

(11)

4.8

12, 16; 20(b) [Don’t worry too much about syntax. Just describe the steps actually needed to produce the desired output.]

(13)

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.

(14)

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 a faster algorithm than using the definition to calculate F₄₀₀... Note: Be careful if you try using formulas on the Internet. Epp defines the Fibonacci sequence starting at F₀=1 while some others start the sequence at F₁=1.

(15)

2.1

12, 15, 33, 43                             

(16)

2.2

2, 4, 8, 15, 27

(17)

2.3

10, 11

(18)

3.1

17, 18, 28, 32

(19)

3.2

10, 17, 25b, 25c, 38

(20)

6.2

10, 14.

(21)

6.3

2, 4, 7, 13

(22)

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).

(23)

6.3

20, 21

Using the is-an-element-of method is always good for verifying a “for-all-sets” identity. It is also OK instead if we verify (or find a counterexample) by calculating with numbered Venn-Diagram regions. However, any Venn-Diagram solution based on shading will NOT be accepted - shading alone is usually confusing & unconvincing.

(24)

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?

(25)

1.3

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

(26)

7.1

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

(27)

7.2

8, 13(b), 17, 18

(28)

7.3

2, 4, 11, 17

(29)

1.3

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

8.1

3. Use the definition of a relation on page 14.

(30)

8.3

15 b, c, d; 21(2). On #21(2), just give the number of equivalences classes and describe each class.

(31)

8.4

2, 4, 8, 17, 18, 27

(32)

8.4

Calculate 2³⁷³ (mod 367). [Hint: If it matters, 2, 367, and 373 are all prime numbers.]

(33)

8.4

12b, 13b [Hint: 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). The same approach works no matter how many digits a positive integer has.] These problems are like #3 on Sample Quiz #2.

(34)

8.4

Solve for x: 1014*x ≡ 7 (mod 4,157), 0 ≤ x ≤ 4,156.

(35)

8.4

20, 21, 23, 27. [The encryption-decryption pair (mod 55) is (3,27). The pair works because 3*27 ≡ 1 (mod 40) where 40=(5-1)(11-1).]37, 38, 40 [The decryption exponent is the answerfrom #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)

10.1

4, 19, 20, 28, 34

(39)

10.2

8 b, c, d; 9; 10

(40)

10.4

On #4, #11 & #13, #15.

On #13: Only explain why the given pair of graphs cannot be isomorphic. Hint: Look at the length of circuits.

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

Note: We are using only an intuitive definition for graphs to be “isomorphic,” because using an exact definition is impractical. See the last paragraph on page 678. However, we will see the technical definition of isomorphism is practical for producing “weird square roots” like in line (36) above, the standard approach for attacking RSA.

(41)

10.5

3, 15, 16, 17, 18, 19

(42)

10.6

15, 16, 17, 18

(43)

9.1

7, 10, 12(b)(ii)-(iii), 14(b)-(c)

(44)

9.2

10, 12(b), 16(b)-(d), 33, 40