DISCRETE MATHEMATICS FOR COMPUTER SCIENCE

COMPUTER SCIENCE 300   FALL 2011

Instructor:  Dr. R. P. Webber

Office and hours:  East Ruffner 332.  MF 2 - 3:00, T 1:30 - 3, and by appointment or coincidence.  I am not usually on campus on Thursdays.

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 160.  3 credits.

Course objectives:  The student will understand basic propositional logic.  The student will understand mathematical induction and its relationship with recursion.  The student will be able to determine the properties of relations.  The student will be able to simplify circuits using the laws of 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, 7th edition. Pearson/Prentice Hall, 2009. 

Course requirements and grading:  There will be three tests and a group 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.  Plus and minus grades will ordinarily be given for grades in the upper 2 and lower 2 points, respectively, of each range.

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 22 - 26

1.1 - 1.4:  Propositional logic

Week 2  Aug 29 - Sep 2

1.4 - 1.6, 2.4:  Quantifiers; mathematical induction

 

Labor Day September 5 - no classes

Week 3  Sep 7 - 9

2.4, 3.1:  Mathematical induction; functions

Week 4  Sep 12 – 16

3.3 - 3.6:  Relations and their properties

Week 5  Sep 19 - 23

Catch up; TEST

Week 6  Sep 26 - 30

4.1 - 4.3:  Algorithms; timing

Week 7  Oct 3 - 7

4.3 - 4.4:  Timing; recursion

 

Fall Break October 10 - 11

Week 8  Oct 12 – 14

8.1 - 8.3:  Graph theory

Week 9  Oct 17 – 21

8.3 - 8.5:  Graph theory

Week 10  Oct 24 – 28

Catch up; TEST

Week 11  Oct 31 – Nov 4

11.1 - 11.3:  Circuit design; Boolean algebra

Week 12  Nov 7 – 11

11.4 - 11.5:  Boolean algebra

Week 13  Nov 14 – 18

12.1 - 12.3:  Finite state machines and automata

Week 14  Nov 21

Notes:  P vs. NP

 

Thanksgiving break Nov 23 – 25

Week 15  Nov 28 - Dec 2

Catch up; TEST

Tuesday, December 6

FINAL EXAM 3 - 5:30 p.m.