Syllabus & Assignments: INFS 501 - Spring 2010
See courses.gmu.edu after each class for an updated Syllabus & Assignments.
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: [to be determined]
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: Classes are Wednesdays, 7:20 - 10:00 pm in Robinson B104
1/20/2010 – 4/28/2010, except 3/10/2010 (14 classes).
Final Exam on Wednesday 5/05/2010, 7:30 - 10:15 pm.
Prerequisite: “Completion of 6 hours of undergraduate mathematics.” As a practical matter, you must have a working knowledge of algebra. Several free tutorials may be found on the Internet.
Topics: Course Catalog: “Study of discrete and logical structures for information systems analysis and design including basic set theory and proof techniques, propositional and predicate logic, trees and graphs, finite state machines, formal languages and their relation to automata, computability and computational complexity, formal semantics-operational, axiomatic and denotational approaches.” We will focus on problem solving.
Textbook: Discrete Mathematics with Applications, 3rd edition (Dec. 22, 2003) By Susanna S. Epp, Publ: Brooks Cole; ISBN-10: 0534359450; ISBN-13: 978-0534359454. We will start with mathematical induction, a method of proof with maybe the least conceptual and notational overhead. With that apology, we’ll follow the textbook in this order: Chapters 4, 8, 3, 9, 5, 7, 10, 11, 1, & 2. A glossary of symbols is inside the front and back covers.
Calculator: You will need a calculator capable of raising numbers to powers. No cell-phone calculators or calculator-sharing during exams.
Exams: We will have: (i) 2 Quizzes, (ii) 2 Hour Exams, and (iii) a comprehensive Final Exam on May 5, 2010. Quizzes will be “closed book,” Exams will be “open book & notes.” Exams and Quizzes will never be given late.
Grades: 1 Final Exam: 45% of final grade.
2 Hour Exams: 20% of final grade each, 40% total.
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: Any Honor Code violations will be reported to the Honor Committee.
Homework Problem Sets Are Updated Weekly After Class - See courses.gmu.edu.
Row |
Sec |
Problems |
Due |
(1) |
4.1 |
2 [correction: bj=(5-j)/(5+j)], 7, 13, 21, 31, 60 |
1/27/2010 |
(2) |
4.2 |
20, 22, 26, 28- Use Thms 4.2.2-3, no math induction |
1/27/2010 |
(3) |
8.1 |
2, 4, 8, 14, 24, 35a & 35b - skip set partitions |
1/27/2010 |
(4) |
8.2 |
1c, 2b&d, 4, 13, 15, 20, 23, write the Fibonacci No. F400 in scientific notation, e.g. F30 ≈ 1.35*106 |
|
(5) |
8.3 |
12 |
|
(6) |
3.1 |
3, 5, 12, 27, 32, 46 |
|
(7) |
3.2 |
2, 15, 21, 27 |
|
(8) |
3.3 |
2, 9, 16, 18, 38 |
|
(9) |
3.4 |
17, 18, 24, 35, 50 |
|
(10) |
3.8 |
2, 12, 16, 20, 25 |
|
(11) |
3.8 |
Observe: 247,710 2 - 38,573 2 = 61,360,244,100 - 1,487,876,329 = 59,872,367,771 = 260,867*229,513 Factor 260,867 in a non-trivial way. |
|
(12) |
5.1 |
#2; #3; #7; #11 a, b, g-j; #12 a, c, e, g, i; #15 |
|
(13) |
5.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? |
|
(14) |
5.2 |
#4; #9 (Venn-diag. proof OK); #13; #21, b, c; # 30 |
|
(15) |
5.3 |
2, 4, 7, 16, 17 |
|
(16) |
7.1 |
2; 11; 14; 35 d, e, f |
|
(17) |
7.2 |
8, 13, 18, 19 |
|
(18) |
7.4 |
2, 4, 11, 17 |
|
(19) |
10.1 |
2, 6, 18, 30 |
|
(20) |
10.2 |
2, 13, 16, 17, 19 |
|
(21) |
10.3 |
11; 12; 13 b, c, d; 19 |
|
(22) |
10.4 |
2, 4, 5, 8, 17, 18 |
|
(23) |
10.4 |
Calculate 1740 mod 83,523. Your answer should be between 0 and 83,522. |
|
(24) |
10.4 |
20, 23, 27, 32, 42 |
|
(25) |
10.4 |
37, 38, 40 |
|
(26) |
Under RSA: p = 13, q = 17, n = 221, & e = 37 is the encryption exponent. Find the decryption exponent d. |
|
|
(27) |
11.1 |
4, 17, 18, 29, 34 |
|
(28) |
11.2 |
8, 9, 10 |
|
(29) |
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. |
|
|
(30) |
11.4 |
• In each problem 4, 11 & 13, explain why the given pair of graphs cannot be isomorphic. Hint on 13: Look for circuits of length 5. • Draw all non-isomorphic simple graphs on 4 vertices. Hint: There are 11. |
|
(31) |
11.5 |
3, 15-20, 43-47, 49 |
|
(32) |
1.1 |
17, 36, 44 |
|
(33) |
1.2 |
2, 15, 27 |
|
(34) |
1.3 |
10, 11 |
|
Tentative Schedule: Exam and Quiz Dates Are Subject to Change
Class |
Date |
Event |
Details |
(1) |
Jan 20, 2010 |
1st Class |
|
(2) |
Jan 27, 2010 |
|
|
(3) |
Feb 3, 2010 |
|
|
(4) |
Feb 10, 2010 |
Quiz 1 |
|
(5) |
Feb 17, 2010 |
|
|
(6) |
Feb 24, 2010 |
|
|
(7) |
Mar 3, 2010 |
EXAM I |
Problems similar to homework, on the quiz, & on the sample quiz & exam |
|
Mar 10, 2010 |
No Class |
Spring Break |
(8) |
Mar 17, 2010 |
|
|
(9) |
Mar 24, 2010 |
|
|
(10) |
Mar 31, 2010 |
|
|
(11) |
Apr 7, 2010 |
Quiz 2 |
|
(12) |
Apr 14, 2010 |
|
|
(13) |
Apr 21, 2010 |
|
|
(14) |
Apr 28, 2010 |
EXAM II & Review |
|
|
May 5, 2010 7:30-10:15 pm |
FINAL EXAM |
|