Class

Date

Event

Details

(1)

Jan 20, 2016

1st Class

(2)

Jan 27, 2016

(3)

Feb 3, 2016

(4)

Feb 10, 2016

Quiz 1

Quiz 1 will be on everything we’ve covered in Chapter 5. Problems will be like in: (1) the homework, (2) the Sample Sequences & Progressions pdf on Blackboard, and (3) the Sample Quiz.

(5)

Feb 17, 2016

(6)

Feb 24, 2016

(7)

Mar 2, 2016

Mar 9, 2016

-no class-

** Enjoy Spring Break! **

(8)

Mar 16, 2016

Hour Exam 1

& Lecture

The exam will cover everything covered in class through Section 3.2. Questions will be like the questions in: (1) the Homework; (2) the Sample Sequences & Progressions pdf on Blackboard; and (3) Sample Quiz 1, Quiz 1, Sample Exam 1

(9)

Mar 23, 2016

(10)

Mar 30, 2016

Quiz 2

The quiz will cover everything since the last exam, including set theory and functions, through HW #9.

(11)

Apr 6, 2016

(12)

Apr 13, 2016

Happy Thanksgiving!

(13)

Apr 20, 2016

(14)

Apr 27, 2016

Hour Exam 2

& Lecture

Exam 2 will cover everything covered in class in Chapters 1, 6, 7, 8, and 10, through HW #12. Questions will be like the questions in: 1) the Homework; (2) Sample Quiz 2, Quiz 2, Sample Exam 2.

(15)

May 4, 2016

7:30 - 10:15 PM

FINAL EXAM

The Final Exam will cover everything from the entire semester, through section 9.5. Problems will be like in: • the Sample Quizzes & Sample Exams, • the prior Quizzes & the prior Exams, • the Homework, ending with the 2 section 9.5 problems listed below.

Row

§

Problems are from the textbook or written out below.

Due

(1)

5.1

7, 13, 16, 32, 57, 61, 83

On 5.1.57: Just calculate the sum for n=5. Do not bother changing variable like the textbook asks.

HW-1

1/27/2016

(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

1/27/2016

(3)

5.6

2, 8, 14, 33. Hints: On 5.6.14, you may mimic Part (1) of the “Second Order Recurrence Example” on BlackBoard. (You would need different values for the constants raised to powers & for the recursion coefficients A & B). On 5.6.33, you may choose to use the Hint on Blackboard. (The formula given in 5.6.33 is derived in the textbook on pages 323-324.)

(4)

5.7

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

(5)

5.8

12, 14 Hint on #12: See Part (2) of the “Second Order Recurrence Example” on BlackBoard.

Hint on #14: This problem is a little different than

#12. Use Theorem 5.8.5 instead of Theorem 5.8.3.

(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. To describe an algorithm, we must describe: (i) its input, (ii) what it does, and (iii) its output.]

(12)

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.

(13)

4.4

Suppose we are given an integer x. Now call the statement s = “(x²-x) is exactly divisible by 3.” Complete exactly one of the following answers (a), (b), or (c): (a) Prove s is true; (b) Prove s is not true; (c) Explain why (a) and (b) are impossible.

(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

15, 33, 43                                         

(16)

2.2

4, 8, 15 [Note #27 is solved on Blackboard]

(17)

2.3

10, 11

(18)

3.1

12, 17(b), 18(c)-(d), 28(a)&(c), 32(b)&(d)

(19)

3.2

10, 17, 25(b)-(c), 38

(20)

1.2

4; 7(b),(e)&(f); 12

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

(21)

6.1

7b; 12(a),(b),(g)&(j); 13; 18

(22)

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?

(23)

6.2

[10-omittted] 14, 32. Hint on 32: Use the is-an-element-of method.

(24)

6.3

2, 4, 7. [Using the is-an-element-of method is always good for verifying a “for-all-sets” identity. It is also OK to instead 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.]

(25)

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

(26)

6.3

20, 21

(27)

1.3

15(c),(d),&(e); 17. These problems fit with Ch. 7 on Functions.

(28)

7.1

2; 5; 14; 51(d),(e),&(f)

(29)

7.2

8, 13(b), 17  

(30)

7.3

2, 4

(31)

7.3

11, 17

(32)

8.1

3(c)&(d). (Relation is defined on page 14.)

(33)

8.3

10

(34)

8.4

2, 4, 8, 17, 18

(35)

8.4

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

(36)

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. For 12b, reduce the 10’s (mod 9). For 13b, reduce the 10’s (mod 11). The same approach works no matter how many digits a positive integer has.]

(37)

8.4

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

(38)

8.4

#20, 21, 23, 27, 32, 37, 38, 40

[#21-27] Hints: The given encryption-decryption pair (mod 55) is (3,27). (3,27) works because 55 = 5*11, (5-1)(11-1)=40, so Little Fermat Theorem implies x⁴⁰ ≡ 1 (mod 55) if gcd(x,55)=1, and 3*27 ≡ 1 (mod 40).

[#40] Hint: The decryption exponent is from #38 since modulus 713 = 23*31, (23-1)(31-1)=660, so the LFT implies x⁶⁶⁰ ≡ 1 (mod 713) when gcd(x, 713)=1.

(39)

8.4

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

(40)

8.4

Solve for x: x² ≡ 4 (mod 675,683). Give all 4 solutions. All 4 answers should be between 0 & 675,682. Use 675,683 = 821 * 823, the product of 2 prime numbers. The general technique is at Square roots (mod pq) two examples.pdf, on BlackBoard. [This problem shows why RSA is susceptible to attack following the approach in Row (13) above.]

(41)

10.1

4, 19, 20, 29, 34

(42)

10.2

8(b),(c)&(d); 9; 10

(43)

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: Intuitively, two graphs are isomorphic if with suitable re-labeling, one graph can be deformed into the other by stretching & bending etc., without tearing, breaking, or adding or subtracting components. The technical definition of isomorphism is often impractical to use with graphs. See the last paragraph on the textbook’s page 678.

(44)

8.4

What integer x satisfies: (a) 1 ≤ x ≤ 2,622,187; (b) x = 510 (mod 661); and (c) x = 479 (mod 3967)?

Here, 661*3967 = 2,622,187.

(45)

10.5

15, 16, 17, 18, 19

(46)

10.6

15, 16, 17, 18

(47)

9.1

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

(48)

9.2

8, 12(b), 17(a),(b)&(d), 22, 33, 40

(49)

9.5

7(a)-(b) & 10 [posted on BlackBoard]. The brief lecture notes on BlackBoard should tell all you need to know about section 9.5