INFS 501 Syllabus & Assignments
See courses.gmu.edu after each class for updates.
Instructor: William D. Ellis E-mail: wellis1@gmu.edu
Office Hours: By appt. (usually Wed. 5-6 pm) Room 5323, Engineering Building
Teaching Asst: To Be determined E-mail: -
Office Hours: By appointment
Web Site: http://courses.gmu.edu . Your ID = 1st part of your GMU e-mailaddress, before the @; Password = your e-mail password.
Schedule: 14 Classes, Wednesdays, 7:20 - 10:00 pm in Innovation Hall 208
1/26/2011 – 5/4/2011, except 3/16/2011
Final Exam on Wednesday 5/11/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 A1-A3 (what could be numbered pages 821-823) 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, 4th ed. (8/4/2010) By Susanna S. Epp, ISBN-10: 0495391328; ISBN-13: 978-0495391326. A copy of the 4th edition is on 2-hour reserve at the Johnson Center Library. 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. No cell-phone calculators or calculator-sharing during exams will be allowed.
Exams: We will have: (i) 3 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 time. 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 e-mail! If you e-mail 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) |
Jan 26, 2011 |
1st Class |
|
(2) |
Feb 02, 2011 |
|
|
(3) |
Feb 09, 2011 |
Quiz 1 |
|
(4) |
Feb 16, 2011 |
|
|
(5) |
Feb 23, 2011 |
|
|
(6) |
Mar 02, 2011 |
Quiz 2 |
|
(7) |
Mar 09, 2011 |
|
|
- |
Mar 16, 2011 |
- |
** Sring Break ** |
(8) |
Mar 23, 2011 |
Exam I |
On everything covered in class to date. The questions will be like the questions in Sample Exam I, in the quizzes and sample quizzes, & in the Homework. |
(9) |
Mar 30, 2011 |
|
|
(10) |
Apr 06, 2011 |
|
On everything covered since Exam I |
(11) |
Apr 13, 2011 |
Quiz 3 |
|
(12) |
Apr 20, 2011 |
|
|
(13) |
Apr 27, 2011 |
|
|
(14) |
May 04, 2011 |
EXAM II & Review |
On everything that we covered in class that was not on Exam I. The questions will be like the questions in Sample Exam II, in Sample Quiz 3, in Quiz 3, & in the Homework. |
|
May 11, 2011 7:30–10:15 pm |
FINAL EXAM |
On everything covered during the entire semester. Problems will be like in the quizzes, hour exams (including samples), and homework. |
Homework assignments are updated after each class, within 24 hours.
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. |
H/W-1: 2/2/2011 |
(2) |
5.2 |
7, 11, 12. Use Mathematical Induction. |
H/W-1: 2/2/2011 |
(3) |
5.2 |
23, 27, 29. Hint: Try using Example 5.2.2 on page 251 & Example 5.2.4 on page 255. |
H/W-1: 2/2/2011 |
(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, 8, 12, 27, 36, 50. Note: #50 requires directly applying the definitions of “even” and “odd,” instead of using well-known properties of even & odd numbers. Those well-known properties (in Example 4.2.3 on page 167 of the next section) themselves depend on the definitions of “even” and “odd.” |
|
(8) |
4.2 |
2, 20, 28 |
|
(9) |
4.3 |
3, 5, 16, 41 |
|
(10) |
4.4 |
6, 21, 30, 35, 42 |
|
(11) |
4.8 |
12, 20, 25. On #20(b), don’t worry too much about syntax. Mainly what you need to do is describe the steps actually needed to produce the desired output. |
|
(12) |
4.8 |
Find GCD(98741, 247021) = GCD(98,741 ; 247,021). |
|
(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.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 many other texts & Wikipedia instead define the non-zero Fibonacci sequence starting at F1=1. |
|
(15) |
1.2 |
#1; #4, #7 b, e, f; #9 c, d, e, f, g, h; #12 (Section 1.2 fits with Chapter 6 on Set Theory.) |
|
(16) |
6.1 |
#7 b; #12 a, b, g-j; #13; #18 |
|
(17) |
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? |
|
(18) |
6.2 |
9, 14, 23(c), 32. Using Venn diagrams is OK on all except 14. Hint on #32: Number the regions of each Venn Diagram (the same way) and represent each constructed set as a set of regions. Venn-Diagram solutions based on shading will not be accepted. |
|
(19) |
6.3 |
4, 7, 20, 21 |
|
(20) |
1.3 |
15 c, d, e; 17; 20. These problems fit with Chapter 7 on Functions. |
|
(21) |
7.1 |
2; 7; 8 c, d, e; 14; 51 d, e, f [skip logarithms] |
|
(22) |
7.2 |
8, 13(a), 18, 19 - Corrected: 8, 13(b), 17, 18 |
|
(23) |
7.3 |
2, 4, 11, 17 |
|
(24) |
1.3 |
2, 6. These problems fit with Chapter 8 on Relations. |
|
(25) |
8.1 |
4, 11, 20 |
|
(26) |
8.2 |
2, 10, 13, 14, 16 |
|
(27) |
8.3 |
9; 12; 15 b, c, d; 21. For #9, define “the sum of the elements” of the empty set to be 0. |
|
(28) |
8.4 |
2, 4, 8, 17, 18, 27, 32 |
|
(29) |
8.4 |
Calculate 1740 mod 83,523. Your answer should be between 0 and 83,522. |
|
(30) |
8.4 |
20, 23, 37, 38, 40, 42 |
|
(31) |
8.4 |
Under RSA: p = 13, q = 17, n = 221, & e = 37 is the encryption exponent. Find the decryption exponent d. |
|
(32) |
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. |
|
(33) |
8.4 |
Find the integer x satisfying: 1 ≤ x ≤ 2,622,187, x = 510 (mod 661), and x = 479 (mod 3967) |
|
(34) |
10.1 |
4, 19, 20, 28, 29, 34 |
|
(35) |
10.2 |
8 b, c, d; 10 |
|
(36) |
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.) |
|
(37) |
10.5 |
3, 15, 16, 17 |
|
(38) |
10.6 |
15, 16, 18 |
|
(39) |
2.1 |
15, 33, 43 |
|
(40) |
2.2 |
2, 15, 27 |
|
(41) |
2.3 |
10, 11 |
|
(42) |
9.5 |
6, 9, 14 |
|