DISCRETE MATHEMATICS FOR COMPUTER SCIENCE
COMPUTER SCIENCE 300 FALL 2006
Instructor: Dr. R. P. Webber
Office and hours: East Ruffner 332. MWF 10 - 10:50, TR 1:10 - 2, and by appointment or coincidence
Telephone: 395-2192
email: webberrp@longwood.edu
Course description: Topics in discrete mathematics used in computer science, including methods of proof, graphs, computability, and formal grammars. Prerequisite: CMSC 206. 3 credits.
Course objectives: The student will understand the basic methods of mathematical proof. The student will be able to determine the properties of relations. The student will be able to determine whether a given system is a Boolean algebra. The student will be able to solve recurrence relations. The student will be able to explain basic graph terminology. The student will understand the meaning of Big-O notation.
Text: Johnsonbaugh, Discrete Mathematics, 6th edition. Pearson/Prentice Hall, 2005.
Course requirements and grading: There will be
three tests, each counting 19% of your course grade. Your group grade will count
18%, and the and a group work grade. You
will drop the lowest of these four, and the remaining three will count 25%
each. The final exam will count the remaining 25%. The grading scale
goes by tens: 90 - 100, A; 80 - 90, B; 70 - 80, C; 60 - 70, D; below 60,
F.
Homework: Homework will be assigned for each sections. It is your responsibility to do the homework and to ask questions about problems you do not understand. Homework will not be collected without warning.
Group work: Occasionally you will be asked to work in groups, usually (but not always) in class. Each group will solve a problem and present its results to the class. Missed class participation cannot be made up, but you will be allowed one absence from a class participation session without penalty. You will receive a grade of 0 for each additional missed session.
Attendance: Your attendance is expected at all classes. Makeup tests will be given reluctantly, and then only upon presentation of a doctor's excuse. Makeup tests are always more difficult than regular tests, regardless of the reason for absence. You may not make up missed class participation sessions.
Honor code: I subscribe to the Longwood University honor system, which, among other things, assumes you do not cheat and that you take responsibility to see that others do not. Infractions will be dealt with harshly. A student who is convicted of an Honor Code offense involving this class will receive a course grade of F, in addition to any penalties imposed by the Honor Board.
Course schedule:
| Week 1 Aug 28-Sep 1 | 1.1 - 1.3: Propositional logic; quantifiers |
| Week 2 Sep 6-8 | 1.4 - 1.6: Methods of proof |
| Week 3 Sep 11-15 | 1.7 - 1.8: Mathematical induction |
| Week 4 Sep 18-22 | 3.1 - 3.4: Relations and their properties |
| Week 5 Sep 25-29 | Review, TEST, 4.1: Algorithms |
| Week 6 Oct 2-6 | 4.2 - 4.3: Big-O notation and timing considerations |
| Week 7 Oct 9-13 | 4.3 - 4.4: Recursive algorithms |
| FALL BREAK | |
| Week 8 Oct 18-20 | 7.1 - 7.2: Recurrence relations |
| Week 9 Oct 22-27 | 7.3 - 8.2: Solving recurrence relations; graph theory |
| Week 10 Oct 30 - Nov 3 | 8.3 - 8.5: Graph theory; review; TEST |
| Week 11 Nov 6-10 | 11.1 - 11.3: Circuit design; Boolean algebra |
| Week 12 Nov 13-17 | 11.4 - 11.5: Boolean algebra |
| Week 13 Nov 20 | Notes: P vs. NP |
| THANKSGIVING | |
| Week 14 Nov 27 - Dec 1 | Review; TEST; 12.1: Finite state machines |
| Week 15 Dec 4-8 | 12.2 - 12.3: Finite state automata; review |
| Monday, December 11 | FINAL EXAM 3 - 5:30 p.m. |