INFS 501 Syllabus & Assignments: Fall 2016
This syllabus is updated weekly at http://mymason.gmu.edu after each class.
Instructor: Prof. William D. Ellis Email: wellis1@gmu.edu
Office Hours: By appt. (usually Wed. 56 PM) Rm. 4439, Engineering Bldg
Web Site: Syllabus updates, sample problems & solutions, lecture notes etc. are posted weekly after class at http://mymason.gmu.edu.
Schedule: 14 Classes 7:2010:00 PM Innovation Hall, Room 134
• Wednesdays 8/31/2016  12/7/2016 except November 23, 2016
• The Final Exam is Wednesday December 14, 2016, 7:3010: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 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 that can display 10 digits and raise numbers to powers. During an exam or quiz: Do not share a calculator or use a computer; cell phones must be put away.
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. Computers, including ebook readers, cannot be used during an openbook exam.
Exams: We will have: (i) 2 Quizzes, (ii) 2 Hour Exams, and (iii) a comprehensive Final Exam (Wednesday December 14, 2016). 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 an exam or quiz: Use all available classroom space, and avoid sitting next to a friend or close to anyone else.
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 weekly Syllabus updates. See http://mymason.gmu.edu. (Your username & password match your Mason NetID & Mason email password.) The Syllabus will be updated online on BlackBoard each week after each class, the first update being on 9/1/2016. Homework will never be accepted late. However, 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. (Use good scans  please don’t waste my toner!)
Honor Code: Honor Code violations are reported to the Honor Committee. See http://cs.gmu.edu/wiki/pmwiki.php/HonorCode/CSHonorCodePolicies Special for INFS501: No Honor Code violation if you collaborate on H/W or if you submit solutions from class discussion.
Semester Schedule: HourExam and Quiz Dates Are SubjecttoChange
Class 
Date 
Event 
Details 
(1) 
Aug 31, 2016 
1st Class 

(2) 
Sep 7, 2016 


(3) 
Sep 14, 2016 


(4) 
Sep 21, 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) 
Sep 28, 2016 


(6) 
Oct 5, 2016 


(7) 
Oct 12, 2016 


(8) 
Oct 19, 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) 
Oct 26, 2016 


(10) 
Nov 2, 2016 
Quiz 2 
The quiz will cover everything since the last exam, including set theory and functions, through HW #9. 
(11) 
Nov 9, 2016 


(12) 
Nov 16, 2016 



Nov 23, 2016 
no class 
** Enjoy Thanksgiving Break! ** 
(13) 
Nov 30, 2016 


(14) 
Dec 7, 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. 
(16) 
Dec 14, 2016 
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. 
Assignments are updated within approximately 24 hours after each class.
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. 
HW1 9/7/2016 
(2) 
5.2 
23, 27, 29. Hint: Try using Example 5.2.2 on page 251 & Example 5.2.4 on page 255. 
HW1 9/7/2016 
(3) 
5.6 
2, 8, 14, 33, 38. 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. 

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

(5) 
5.8 
12, 14 This problem is a little different than #12. Use Theorem 5.8.5 instead of Theorem 5.8.3. Email me if you have trouble solving the Characteristic Equation on either #12 or #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. The point of #50 is to see how the wellknown 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 

(10) 
4.8 
Find GCD(98741, 247021). 

(11) 
4.8 
12, 16; 20(b) [Don’t worry much about syntax. To describe an algorithm, we must describe: (i) its input, (ii) what it says to do, and (iii) its output.] 

(12) 
4.4 
35, 42, 44 [On BlackBoard, #4.4.43 is like H/W 4.4.35 & 4.4.42.] 

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

(14) 
4.8,5.8 
Write the Fibonacci no. F_{400} in scientific notation, e.g. F_{30} ≈ 1.35*10^{6}. Note: Be careful if you try using formulas on the Internet. Epp defines the Fibonacci sequence starting at F_{0}=1 while some others (like Wikipedia) start the sequence at F_{0}=0, F_{1}=1. Both enumerations list the same set of numbers. 

(15) 
2.1 
15, 33, 43. [On BlackBoard, #2.1.41 is like H/W 2.1.43; the Java problem in “Symbolic Logic Compared to Set Theory” is like H/W 2.1.33.] 

(16) 
2.2 
4, 15, 27 [#8 is solved on Blackboard. For 2.2.4, see the bottom table on page 1 of “Truth Tables, Arguments Forms & Syllogisms” on BlackBoard] 

(17) 
2.3 
10, 11 

(18) 
4.4 
Suppose we are given an integer x. Now call the statement s = “(x^{2}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. 

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

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

(21) 
1.2 
4; 7(b),(e)&(f); 12 (Section 1.2 fits with Ch. 6 on Set Theory.) 

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

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

(24) 
6.2 
14, 32 

(25) 
6.2 
10 

(26) 
6.3 
2, 4, 7. [Using the isanelementof method is always good for verifying a “forallsets” identity. It is also OK to instead verify (or find a counterexample) by calculating with numbered VennDiagram regions. However, any VennDiagram solution based on shading will NOT be accepted  shading alone is usually confusing & unconvincing.] 

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

(28) 
6.3 
20, 21 

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

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

(31) 
7.2 
8, 13(b), 17 

(32) 
7.3 
2, 4 

(33) 
7.3 
11, 17 

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

(35) 
8.3 
10 

(36) 
8.4 
2, 4, 8, 17, 18 

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

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

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

(40) 
8.4 
#20, 21, 23, 27, 32, 37, 38, 40 [#2127] Hints: The given encryptiondecryption pair (mod 55) is (3,27). (3,27) works because 55 = 5*11, (51)(111)=40, so Little Fermat Theorem implies x^{40} ≡ 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, (231)(311)=660, so the LFT implies x^{660} ≡ 1 (mod 713) when gcd(x, 713)=1. 

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

(42) 
8.4 
Solve for x: x^{2} ≡ 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 (14) above.] 

(43) 
10.1 
4, 19, 20, 29, 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 nonisomorphic simple graphs with 4 vertices. Note: Intuitively, two graphs are isomorphic if with suitable relabeling, 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. 

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

(47) 
10.5 
15, 16, 17, 18, 19 

(48) 
10.6 
15, 16, 17, 18 

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

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

(51) 
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 
