INFS 501 Syllabus & Assignments: Fall 2012

This syllabus is updated weekly at http://mymason.gmu.edu after class.

 

Instructor:    Prof. William D. Ellis               E-mail: wellis1@gmu.edu

Office Hours:  By appt. (usually Wed. 5-6 pm)    Room 5323, Engineering Bldg.

 

Teaching Asst: To Be Determined (“TBD”)           E-mail: TBD

               Office Hours: TBD                                            

 

Web Site:      Syllabus updates, sample problems & solutions, lecture notes etc. are posted weekly at http://mymason.gmu.edu .

 

Schedule:      14 Classes, Wed., 7:20 - 10:00 pm         Enterprise Hall 174

8/29/2012 – 12/5/2012, except no class 11/21/2012

Final Exam on Wednesday 12/12/2012, 7:30 - 10:15 pm.

 

Prerequisite:  “Completion of 6 hours of undergraduate mathematics.” As a practical matter, you need a working knowledge of algebra, including the laws of exponents. Several free tutorials may be found on the Internet. Also see textbook’s Appendix pages A1-A3.

 

Topics:        We will follow the textbook in this order: Chapters 5, 4, 2, 3, 6, 7, 8, 10, and 9. We will focus on problem solving, using fundamental definitions, theorems, and algorithms.

 

Calculator:    You will need a calculator capable of raising numbers to powers. Really! Using a computer or a cell-phone calculator or sharing a calculator is not permitted during an exam or quiz.

 

Textbook:      Discrete Mathematics with Applications, 4th ed. (8/4/2010) By Susanna S. Epp, ISBN-10: 0495391328; ISBN-13: 978-0495391326. A copy will be on 2-hour reserve at the Johnson Center Library under Theresa Calcagno, QA 39.3 .E65 2011. A computer cannot be used to access any electronic text during an open-book exam.

 

Exams:         We will have: (i) 2 Quizzes, (ii) 2 Hour Exams, and (iii) a comprehensive Final Exam (Wednesday Dec 12, 2012). Quizzes will be “closed book,” Exams will be “open book & notes.” Exams and Quizzes will be given only one time - no makeup exams. During exams and quizzes, students should use all available classroom space & should avoid sitting close together.

 

Grades:        Final Grade = weighted average of letter grades: 45% {Final Exam} + 20% {Hour Exam 1} + 20% {Hour Exam 2} + 15% {Quizzes + Homework}. The largest possible Quiz-H/W Total = 1,800 (300 x 2 quizzes + 100 x 12 H/W). The Quiz-H/W Total is converted to a Quiz-H/W letter grade by grading on the curve.

 

Help:          Questions? Send me an e-mail! Use the ^ symbol for exponents, * for multiplication. You may also e-mail a pdf or scanned image.

 

Homework:      Homework assignments will be on the Syllabus updates. The Syllabus will be updated each week after class. See http://mymason.gmu.edu . Homework will never be accepted late. Of the 13 Homework assignments, only the 12 with the highest percentage scores will be counted toward your grade. Submit homework on paper, or scan & e-mail if you cannot attend class.

 

Honor Code:    Honor Code violation will be reported to the Honor Committee. See http://cs.gmu.edu/wiki/pmwiki.php/HonorCode/HomePage. No violation if you submit H/W solutions from class discussion.


Tentative Schedule: Exam and Quiz Dates Are Subject to Change

Class

Date

Event

Details

(1)

Aug 29, 2012

1st Class

 

(2)

Sep 5, 2012

 

 

(3)

Sep 12, 2012

 

 

(4)

Sep 19, 2012

Quiz 1

 

(5)

Sep 26, 2012

 

 

(6)

Oct 3, 2012

 

 

(7)

Oct 10, 2012

 

 

(8)

Oct 17, 2012

EXAM I

Problems will be like in Quiz 1, Sample Quiz 1, Sample Exam I, and the homework.

(9)

Oct 24, 2012

 

 

(10)

Oct 31, 2012

 

 

(11)

Nov 7, 2012

Quiz 2

 

(12)

Nov 14, 2012

 

 

 

Nov 21, 2012

No Class

Thanksgiving Recess

(13)

Nov 28, 2012

 

 

(14)

Dec 5, 2012

EXAM II

& Review

The Exam will be on everything covered in class that was not on Exam I. Problems will be like in Quiz 2, Sample Quiz 2, Sample Exam II, and the homework.

(15)

Dec 12, 2012

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.



Homework assignments are updated weekly within 24 hours after each class.

Row

Sec

Problems are from the textbook or written out here.

Due

(1)

5.1

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

HW-1 9/05/2012

(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/05/2012

(3)

5.6

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

HW-1 9/05/2012

(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. Doing #50 shows how the well-known properties of even & odd numbers (in Ex. 4.2.3 on page 167) themselves follow from the definitions.]

 

(7)

4.2

2, 20, 28

 

(8)

4.3

3, 5, 21, 41

 

(9)

4.4

6, 17, 21, 35, 42÷

 

(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.]

 

(12)

4.8

Observe: 247,710 2 - 38,573 2

    = 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.8,5.8

Write the Fibonacci no. F400 in scientific notation, e.g. F30 ≈ 1.35*106. Using the textbook’s closed-form formula on page 324 is much faster algorithm than using the definition to calculate F400... Note: Our textbook defines the Fibonacci sequence starting at F0=1, while in many other texts & Wikipedia it is convenient to define the Fibonacci sequence starting at F1=1.

 

(14)

2.1

15

 

(15)

2.1

33, 43

 

(16)

2.2

2, 15, 27

 

(17)

2.3

10, 11

 

(18)

3.1

17, 18

 

(19)

3.1

28, 32

 

(20)

3.2

10, 17, 25b, 25c, 38

 

(21)

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

 

(22)

6.1

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

 

(23)

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?

 

(24)

6.2

10, 14.

 

(25)

6.3

2, 4, 7, 13

Verifying a set identity with Venn-Diagram regions is OK except, any Venn-Diagram solutions based on shading will NOT be accepted, because often shading is confusing and unconvincing. Instead of shading, number regions and calculate a Venn-Diagram set as a set of regions, like we do in class.

 

(26)

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

 

(27)

6.3

20, 21

 

(28)

1.3

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

 

(29)

7.1

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

 

(30)

7.2

8, 13(b), 17, 18

 

(31)

7.3

2, 4, 11, 17

 

(32)

1.3

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

 

(33)

8.1

4, 11, 20

 

(34)

8.2

2, 10, 13, 14, 16

 

(35)

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.

 

(36)

8.4

2, 4, 8, 17, 18.

 

(37)

8.4

20, 21, 23. [The encryption-decryption pair (mod 55) is (3,27). The pair works because 3*27 ≡ 1 (mod 40) where 40=(5-1)(11-1).]

27

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

 

(38)

8.4

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

 

(39)

8.4

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

 

(40)

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 #10 on Sample Quiz #2.

 

(41)

8.4

Solve for x: x2 = 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.

 

(42)

8.4

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

 

(43)

10.1

4, 19, 20, 28, 34

 

(44)

10.2

8 b, c, d; 9; 10

 

(45)

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.

 

(46)

10.5

3, 15, 16, 17, 18

 

(47)

10.6

15, 16, 17, 18

 

(48)

9.1

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

 

(49)

9.2

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