MAD 3107 Discrete Math

Syllabus

Dr. Schnackenberg

Spring 2005

I.          Course Number and Title:

MAD 3107 – Discrete Mathematics

II.         Prerequisites for the Course:

MAC 2312 with a minimum grade of C.

 

III.        General Course Information:

MAD 3107 is an introduction to concepts of discrete mathematics, as used by computer scientists.  Topics include: symbolic logic and Boolean algebra, prepositional and predicate calculus, sets, functions, and relations, enumeration and counting principles, introduction to graphs, trees, spanning trees, shortest path and matching algorithms, finite state automata, and Turing machines.

 

 

IV.       Requirements for the Students:

The student should read all new topics before they are discussed in class and complete the homework assignments on time.  The professor will devote a portion of classroom activities to the solution of any “troublesome” exercises.  The student is expected to spend between 6 and 9 hours per week on reading the text, reviewing and/or rewriting notes, solving problems  -  in general, STUDYING!  Calculators and computers may be used to solve problems.

 

Students are strongly encouraged to participate in classroom discussions and to be prepared to demonstrate the solutions to assigned homework problems at the ‘blackboard’.

 

V.        Absence Policy:

Students are expected to attend all class periods.  There are no “allowable cuts”.  Students should recognize the very important sequential nature of this course, and that each absence tends to create a learning gap which can be very difficult to bridge.  An absence in a four-hour course that meets twice a week can have a disastrous effect on the student’s progress and understanding in the course

 

VI.       Grading Procedure:

A.        Grading Criteria:
Chapter Exams                                                                              80%

            Homework                                                                                    20%

           

 

B.         Percentage Ranges for Letter Grades

93       -      100    =      A

90       -        92    =      A-

87       -        89    =      B+
80       -        86    =      B

77       -        79    =      B-

74       -        76    =      C+

67       -        73    =      C
64       -        66    =      C-
60       -        63    =      D
0         -        59    =      F

 

C.        Incompletes (I):
Incompletes will be given only for extreme emergency conditions and must be approved by the professor before the final examination begins.  The student must be doing passing work at the time the request is made, and must reasonably expect to complete the work within three weeks after the close of the semester.

 

D.        Course Work:
All homework must be submitted on date due.  Homework submitted after that date will not be accepted.  If you are unable to attend class, you may fax your homework to the number at the top of the syllabus.

 

E.         Make-Up Exam:

Make-up exams will be EXTREMELY DIFFICULT!  They are to be avoided whenever possible.

 

F.         Special Needs:

            Students with special needs must make them known to the professor at the beginning of the semester.

 

VII.      Textbook Requirements:

Discrete Mathematics, 4th edition, by Dossey, Otto, Spence, and Vanden Eynden, Addison-Wesley.

 

 

SCHEDULE

1          1/11     Chapter 1.1 – The time to complete a project;

                        Chapter 1.2 – A matching problem;

2          1/13     Chapter 1.3 – A knapsack problem;

                        Chapter 1.4 – Algorithms and their efficiency;

            1/18     Chapter 2.1 – Set operations;

                        Chapter 2.2 – Equivalence relations;

3          1/20     Chapter 2.3 – Congruence;

                        Chapter 2.4 – Partial ordering relations;

            1/25     Chapter 2.5 – Functions;

                        Chapter 2.6 – Mathematical induction;

4          1/27     Chapter 2.7 – Applications;

            2/1       Review

5          2/3       Test 1 – Chapters 1,2

            2/8       Chapter 3.1 – Graphs and their representations;

                        Chapter 3.2 – Paths and circuits;

6          2/10     Chapter 3.3 – Shortest paths and distance;

                        Chapter 3.4 – Coloring a graph;

            2/15     Chapter 3.5 – Directed graphs and multigraphs;

7          2/17     Chapter 4.1 – Properties of trees;

                        Chapter 4.2 – Spanning trees;

            2/22     Chapter 4.3 – Depth-first search;

                        Chapter 4.4 – Rooted trees;

8          2/24     Chapter 4.5 – Binary trees and traversals;

                        Chapter 4.6 – Optimal binary trees and binary search trees;

9          3/1       Review

            3/3       Test 2 – Chapters 3,4

10        3/15     Chapter 7.1 – Pascal’s triangle and the binomial theorem;

                        Chapter 7.2 – Three fundamental principles;

            3/17     Chapter 7.3 – Permutations and combinations;

                        Chapter 7.4 – Arrangements and selections with repetitions;

11        3/22     Chapter 8.1 – Recurrence relations;

                        Chapter 8.2 – The method of iteration;                                                       

            3/24     Chapter 8.3 – Linear difference equations with constant coefficients;

                        Chapter 8.5 – Counting with generating functions;

12        3/29     Chapter 8.6 – The algebra of generating functions;

            3/31     Review

13        4/5       Test 3 – Chapter 7,8

            4/7       Chapter A.1 – Statements and connectives;

                        Chapter A.2 – Logical equivalence;

14        4/12     Chapter A.3 – Methods of proof;

            4/14     Chapter 9.1 – Logical gates;

                        Chapter 9.2 – Creating combinatorial circuits;

15        4/19     Chapter 9.3 – Karnaugh maps;

                        Chapter 9.4 – Finite state machines;

            4/21     Review

16        4/26     Test 4 – Chapters 8, A, 9                                                                  


ASSIGNMENTS:

Problem Set 1

1.1              odd

1.2              odd

1.3              odd

1.4              1-27 odd

2.1              odd

2.2              odd

2.3              1-41 odd, 45-48, 51

2.4              1-11 odd,13-21, 23-27, 29, 31, 35

2.5              1-69 odd

2.6              1-10, 11-25 odd, 27-29

2.7              1-39 odd, 47, 48

 

Problem Set 2

3.1              1-47 odd

3.2              1-29 odd, 30-34, 35-61 odd

3.3              1-15 odd

3.4              1-29 odd

3.5              1-21 odd, 35-49 odd, 53-59 odd, 61-77 odd

4.1              1-17 odd, 31

4.2              1-11 odd, 15-31 odd, 39

4.3              1-27 odd

4.4              1-11 odd, 15, 21, 23, 29-32

4.5              1-57 odd

4.6              1-39 odd, 49, 55

 

Problem Set 3

7.1              1-33 odd

7.2              1-31 odd

7.3              1-31 odd

7.4              1-33 odd

 

 

 

| Florida Gulf Coast University | Dr. S's Home Page |

 

 

Created August 1998; last updated 16 December 2004

Copyright Σ 1998-2004, all rights reserved. This page is not an official page of Florida Gulf Coast University and, as such, expresses the sole view of the author