DISCRETE MATHEMATICAL STRUCTURES

MA 210

Catalogue Description

An introduction to counting methods and graph theory, elementary Boolean Algebra and introductory automata theory. Additional topics include induction, recursion, relations, and lattices. The course is appropriate for Mathematics or Computer Science Majors. 3 credits - No Prerequisites.

Goals

A. To teach those mathematical concepts of sets, relations, logic, induction, lattices, and matrices which form a basis for the further study of mathematics and computer science.

B. To introduce the student to subscripts and indexing notation as well as matrix notation.

C. To increase the student's ability to prove theorems.

D. To increase the student's ability to use calculators and computers.

E. To encourage the student to attack interesting problems not presented in class.

F. To encourage the student to use criteria of consistency and reasonableness in evaluating his solutions to problems.

Procedures

A. Lecture/Discussion

B. Step-by step problem calculations with calculators or computers.

C. Student critiques of erroneous solutions.

D. Daily Homework assignments and in-class discussion of solutions.

Course Content

A. Introduction to Graphs and Trees

1. Graphs

2. Special paths and trees

3. Matrices for graphs

B. Sets

1. Some special sets

2. Set operations

3. Subscripts and indexing

4. Ordered pairs, matrix notation

C. Elementary Logic and Induction

1. Propositional Calculus

2. Formal proofs

3. Methods of proof

4. First look at induction

D. Functions and sequences

1. Functions

2. Invertible Functions

3. Sequences and Big-oh notation

4. Recursive definitions

5. Recursive relations

6. General recursive definitions

E. Matrices and other Semigroups

1. Matrices

2. Semigroups

3. The division algorithm and Z(p)

F. Relations

1. Partially ordered sets

2. Special orderings

3. Equivalence relations

4. General relations

5. Composition of relations

6. Closures of relations

7. The Lattice of partitions

G. Graphs

1. Directed Graphs

2. Isomorphisms and Invariants

3. Undirected Graphs

4. Matrices, relations, and graphs

5. Graph algorithms

6. Modifications and applications of the algorithms

H. Boolean Algebra

1. Lattices

2. Distributive and Boolean Lattices

3. Boolean Algebras

4. Boolean Expressions

5. Logic networks

6. Karnaugh Maps

Evaluation methods

1. Daily homework assignments. These will not be graded but students are expected to do them and be prepared to discuss the problems in class.

2. Quizzes. Quizzes will be given as necessary. All quizzes will count collectively as an additional test.

3. Tests. Unit tests will be given every three to four weeks. The results will be discussed in class.

4. Comprehensive Final Exam. This will test whether the student has finally learned to do the problems which are representative of the course and to what extent he possesses these skills at the conclusion of the course.

TESTS.......................2/3

FINAL EXAMS...........1/3

Bibliography

Required Text: Ross, Kenneth A. & Wright, Charles R.B, Discrete Mathematics, 2nd Ed., Englewood Cliffs, N.J., Prentice-Hall, 1988.

Althoen, Steven C. & Bumcrot, Robert J., Introduction to Discrete Mathematics, PWS- Kent Publishing Co., 1988.

Bogart, Kenneth P., Discrete Mathematics, D.C. Heath & Co., 1988.

Bradley, James, Introduction to Discrete Mathematics, Addison-Wesley, 1988.

Joshi, K.D, Discrete Structures and Combinations, John Wiley & Sons, 1988.

Mislove, Michael, Introduction to Discrete Mathematics, John Wiley & Sons, 1988.

Molluzzo, John C. & Buckley, Fred, First Course in Discrete Mathematics, Wadsworth Publishing Co., 1986.

Prather, Ronald E., Discrete Mathematical Structures for Computer Science, Boston, Ma., Houghton-Mifflin Co., 1976.

Roman, Steven, An Introduction to Discrete Mathematics, 2nd Ed., Chicago, Ill., Harcourt Brace Janovich, Inc., 1989.