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

emailwebberrp@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.