INFS 501 Syllabus & Assignments: Spring 2013
This syllabus is updated weekly at http://mymason.gmu.edu after class.
Instructor: Prof. William D. Ellis Email: wellis1@gmu.edu
Office Hours: By appt. (usually Wed. 56 pm) Room 5323, Engineering Bldg.
Teaching Asst: To Be Determined
Office Hours:
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 Robinson Hall B113
1/23/2013 – 5/1/2013, except no class 3/13/2013
The Final Exam is Wednesday 5/8/2013, 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 A1A3.
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 cellphone calculator or sharing a calculator is not permitted during an exam or quiz.
Textbook: Discrete Mathematics with Applications, 4^{th} ed. (8/4/2010) By Susanna S. Epp, ISBN10: 0495391328; ISBN13: 9780495391326. A copy will be on 2hour 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 openbook exam.
Exams: We will have: (i) 2 Quizzes, (ii) 2 Hour Exams, and (iii) a comprehensive Final Exam (Wednesday May 8, 2013). Quizzes will be “closed book,” Exams will be “open book & notes.” Exams and Quizzes will be given only one time  no makeup exams. I often give partial credit when grading. However, no partial credit will be given for a purported proof to a false statement. During exams and quizzes, students should use all 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! Use the ^ symbol for exponents, * for multiplication. You may also email 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 & email if you cannot attend class.
Honor Code: Honor Code violations are reported to the Honor Committee. See http://cs.gmu.edu/wiki/pmwiki.php/HonorCode/CSHonorCodePolicies 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) 
Jan 23, 2013 
1st Class 

(2) 
Jan 30, 2013 


(3) 
Feb 6, 2013 


(4) 
Feb 13, 2013 
Quiz 1 

(5) 
Feb 20, 2013 


(6) 
Feb 27, 2013 


(7) 
Mar 6, 2013 



Mar 13, 2013 
No Class 
Spring Break 
(8) 
Mar 20, 2013 


(9) 
Mar 27, 2013 


(10) 
Apr 3, 2013 
Quiz 2 

(11) 
Apr 10, 2013 


(12) 
Apr 17, 2013 


(13) 
Apr 24, 2013 


(14) 
May 1, 2013 
EXAM II & Review 

(9) 
May 8, 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. 
Assignments are updated weekly within approximately 24 hours after each class.
Row 
§ 
Problems are from the textbook or written out below. 
Due 

(1) 
5.1 
2, 7, 13, 16, 32, 61, 72. Hint: For #72, the examples on pages 239 and 569 might help. 
HW1 1/30/2013 

(2) 
5.2 
23, 27, 29. Hint: Try using Example 5.2.2 on page 251 & Example 5.2.4 on page 255. 
HW1 1/30/2013 

(3) 
5.6 
2, 8, 14, 33, 38a & 38b. 
HW1 1/30/2013 

(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 wellknown properties of even & odd numbers. Doing #50 shows how the wellknown 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, 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.] 


(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 nontrivial way. 


(13) 
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 Fibonacci sequence starting at F_{1}=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, 28, 32 


(19) 
3.2 
10, 17, 25b, 25c, 38 


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


(21) 
6.1 
#7 b; #12 a, b, g, j; #18 


(22) 
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? 


(23) 
6.2 
10, 14. 


(24) 
6.3 
2, 4, 7, 13 
Verifying a set identity with VennDiagram regions is OK except, any VennDiagram solutions based on shading will NOT be accepted, because often shading is confusing and unconvincing. Instead of shading, number regions and calculate a VennDiagram set as a set of regions, like we do in class. 

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


(26) 
6.3 
20, 21 


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


(28) 
7.1 
2; 5; 8 c, d, e; 14; 51 d, e, f [skip logarithms] 


(29) 
7.2 
8, 13(b), 17, 18 


(30) 
7.3 
2, 4, 11, 17 


(31) 
1.3 
2, 6. These problems fit with Chapter 8 on Relations. 


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


(33) 
8.4 
2, 4, 8, 17, 18, 27 


(34) 
8.4 
Calculate 2^{373} (mod 367). [Hint: If it matters, 2, 367, and 373 are all prime numbers.] 


(35) 
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 3digit base10 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. 


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


(37) 
8.4 
20, 21, 23, 27. [The encryptiondecryption pair (mod 55) is (3,27). The pair works because 3*27 ≡ 1 (mod 40) where 40=(51)(111).] 37, 38, 40 [The decryption exponent is the answer from #38 because 713 = 23*31, 660=(231)(311), andx^{660} = 1 (mod 713) when gcd(x, 660)=1.] 


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


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


(40) 
10.1 
4, 19, 20, 28, 34 


(41) 
10.2 
8 b, c, d; 9; 10 


(42) 
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 nonisomorphic 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. 


(43) 
10.5 
3, 15, 16, 17, 18, 19 


(44) 
10.6 
15, 16, 17, 18 


(45) 
9.1 
7, 10, 12(b)(ii)(iii), 14(b)(c) 


(46) 
9.2 
10, 12(b), 16(b)(d), 33, 40 
