INFS 501 Syllabus & Assignments: Fall 2011
This syllabus is updated weekly at http://mymason.gmu.edu after class.
Instructor: William D. Ellis Email: wellis1@gmu.edu
Office Hours: By appt. (usually Wed. 56 pm) Room 5323, Engineering Building
Web Site: Syllabus updates, sample problems & solutions, lecture notes etc. are posted weekly at http://mymason.gmu.edu .
Schedule: 14 Classes, Wednesdays, 7:20  10:00 pm, Art & Design Bldg 2003
8/31/2011 – 12/7/2011 , except no class 11/23/2011
Final Exam on Wednesday 12/14/2011, 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. The textbook’s Appendix pages A1A3 (what could be numbered pages 821823) are helpful, too.
Topics: We will follow the textbook in this order: Chapters 5, 4, 6, 7, 8, 10, 2, and 9. Note there is a glossary of symbols inside the front and back covers. We will focus on problem solving, using fundamental definitions, theorems, and algorithms.
Textbook: Discrete Mathematics with Applications, 4^{th} ed. (8/4/2010) By Susanna S. Epp, ISBN10: 0495391328; ISBN13: 9780495391326. Copies of the 3^{rd} & 4^{th} editions are on 2hour reserve at the Johnson Center Library. (The small discussion of the Chinese Remainder Theorem in the 3^{rd} edition was omitted in the 4^{th} edition  gasp!) Give the call number QA 39.3 .E65 2011. The book is reserved under the librarian’s name: Theresa Calcagno.
Calculator: You will need a calculator capable of raising numbers to powers. Really! No cellphone calculators or calculatorsharing during exams will be allowed.
Exams: We will have: (i) 2 Quizzes, (ii) 2 Hour Exams, and (iii) a comprehensive Final Exam (Wednesday May 11, 2011). 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 available classroom space & should avoid sitting close together.
Grades: 1 Final Exam: 45% of final grade.
2 Hour Exams: 40% of the final grade (20% each)
Homework and Quizzes together: remaining 15% of final grade.
Help: Questions? Send me an email! If you email anything more than simple text, please send a pdf.
Homework: Homework assignments will always be on the Syllabus. The Syllabus will be updated each week after class. See courses.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.
Honor Code: Honor Code violations will be reported to the Honor Committee.
Tentative Schedule: Exam and Quiz Dates Are Subject to Change
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 
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, 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 wellknown properties of even & odd numbers. Doing #50 shows how the wellknown 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_{400} in scientific notation, e.g. F_{30} ≈ 1.35*10^{6}. Using the textbook’s closedform formula on page 324 is much faster algorithm than using the definition to calculate F_{400}... Note: Our textbook defines the Fibonacci sequence starting at F_{0}=1, while in many other texts & Wikipedia it is convenient to define the nonzero Fibonacci sequence starting at F_{1}=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^{ 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 nontrivial 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, gj; #13; #18 

(17) 
6.2 
9, 14, 23(c), 32. 
VennDiagram solutions are OK except on 6.2.14, use the “is an element of” method. Any VennDiagram solutions based on shading will NOT be accepted, because often shading is confusing and unconvincing. Instead, number regions and calculate a VennDiagram 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 (AB)C = (AC)(BC), (ii) ∀ sets A, B & C, (AB)C = (AC)(BC). 


(20) 
6.3 
20, 21 


(21) 
6.1 
Of a population of students taking 13 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 3digit base10 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^{40} (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^{374} (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=(231)(311), and x^{660} = 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^{2} = 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 nonisomorphic 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 CRTisomorphism exposes the modulararithmetic 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 
