INFS 501 Syllabus & Assignments: Fall 2015
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) Rm. 5306, 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, Wednesdays, 7:20-10 PM Rm. 2026, Art & Design Bldg
• Wednesdays 9/2/2015-12/9/2015 except 11/25/2015
• The Final Exam is Wednesday 12/16/2015, 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 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 that can display 10 digits and raise numbers to powers. Using a computer or cell-phone calculator, or sharing a calculator are 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 16, 2015). 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. Students should use all available classroom space & avoid sitting close together during exams and quizzes.
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 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 weekly Syllabus updates. See http://mymason.gmu.edu. (Your username & password match your Mason NetID & Mason e-mail password.) The Syllabus will be updated online on BlackBoard each week after each class, the first update being on 9/23/2015. 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 & e-mail 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: Hour-Exam and Quiz Dates Are Subject to Change
Class |
Date |
Event |
Details |
(1) |
Sep 2, 2015 |
1st Class |
|
(2) |
Sep 9, 2015 |
|
|
(3) |
Sep 16, 2015 |
|
|
(4) |
Sep 23, 2015 |
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 30, 2015 |
|
|
(6) |
Oct 7, 2015 |
|
|
(7) |
Oct 14, 2015 |
|
|
(8) |
Oct 21, 2015 |
Hour Exam 1 & Lecture |
|
(9) |
Oct 28, 2015 |
|
|
(10) |
Nov 4, 2015 |
|
|
(11) |
Nov 11, 2015 |
|
|
(12) |
Nov 18, 2015 |
Quiz 2 |
|
|
Nov 25, 2015 |
-no class- |
Thanksgiving Recess |
(13) |
Dec 2, 2015 |
|
|
(14) |
Dec 9, 2015 |
Hour Exam 2 & Lecture |
|
(15) |
Dec 16, 2015 7:30 - 10:15 PM |
FINAL EXAM |
The Final Exam will cover everything from the entire semester. Problems will be like in the Sample Quizzes & Sample Exams, in the prior Quizzes & the prior Exams, and in the homework. |
Assignments are each week 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. |
HW-1 9/9/2015 |
(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/9/2015 |
(3) |
5.6 |
2, 8, 14, 33. Hint: You may mimic the “Second Order Recurrence Example” on BlackBoard when doing 5.6.14 and/or 5.6.33. On 5.6.33, you may instead choose to use the Hint on Blackboard. (The formula in 5.6.33 is derived in the textbook on pages 323-324.) |
|
(4) |
5.7 |
1c, 2b & 2d, 4, 23, 25 |
|
(5) |
5.8 |
12 Hint: See the “Second Order Recurrence Example” or the solution to Sample Quiz 1 #5 on BlackBoard |
|
(6) |
5.8 |
14 |
|
(7) |
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.”] |
|
(8) |
4.2 |
2, 7, 20, 28 |
|
(9) |
4.3 |
3, 5, 21, 41 |
|
(10) |
4.4 |
6, 21, 25, 35, 42, 44 |
|
(11) |
4.8 |
Find GCD(98741, 247021). |
|
(12) |
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.] |
|
(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 non-trivial way. |
|
(14) |
4.4 |
Suppose we are given an integer x. Now call the statement s = “(x2-x) is exactly divisible by 3.” Complete only 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. |
|
(15) |
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 a faster algorithm than using the definition to calculate F400... Note: Be careful if you try using formulas on the Internet. Epp defines the Fibonacci sequence starting at F0=1 while some others start the sequence at F1=1. |
|
(16) |
2.1 |
15, 33, 43 |
|
(17) |
2.2 |
4, 8, 15 [Note #27 is solved on Blackboard] |
|
(18) |
2.3 |
10, 11 |
|
(19) |
3.1 |
12, 17(b), 18(c)-(d), 28(a), 28(c), 32(b), 32(d) |
|
(20) |
3.2 |
10, 17, 25b, 25c, 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 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, 32 |
|
(25) |
6.3 |
2, 4, 7, 13. [Using the is-an-element-of method is always good for verifying a “for-all-sets” identity. It is also OK if instead we 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.] |
|
(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; 20. These problems fit with Ch. 7 on Functions. |
|
(29) |
7.1 |
2; 5; 14; 51 d, e, f |
|
(30) |
7.2 |
8, 13(b), 17, 18, |
|
(31) |
7.3 |
2, 4, 11, 17 |
|
(32) |
8.1 |
3(c),(d). Use the definition of a relation on page 14. |
|
(33) |
8.3 |
10 |
|
(34) |
8.4 |
2, 4, 8, 17, 18 |
|
(35) |
8.4 |
Calculate 2373 (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 x40 ≡ 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 x660 ≡ 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: x2 ≡ 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, 28, 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 one 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 textbook page 678. |
|
(44) |
10.5 |
3, 15, 16, 17, 18, 19 |
|
(45) |
10.6 |
15, 16, 17, 18 |
|
(46) |
9.1 |
7, 10, 12(b)(ii)-(iii), 14(b)-(c) |
|
(47) |
9.2 |
8, 12(b), 17(a),(b),(d) |
|