I. NUMBER AND TITLE OF COURSE

Mathematics 670,  Discrete Mathematics and Foundations of Computer Science

Since secondary schools are currently expecting teachers to introduce many ideas from discrete mathematics into their curriculum, this course in mathematics will give students the knowledge, skills and tools required to be proficient teachers of discrete mathematics and algorithmic problem solving.

A. To present problems and theorems from discrete mathematics and computer science to students and future teachers of mathematics.

B. To provide students of mathematics and future teachers with opportunities to improve problem solving skills and algorithmic thinking, and to use the student oriented instructional techniques advocated in the Curriculum and Evaluation Standards for School Mathematics.

C. To facilitate student experimentation and exploration in discrete mathematics, perhaps, by using Mathematica or some other combinatorial computing environment.

A. Review of Foundations and Discrete structures

1. Sets
2. Relations
3. Graphs
4. Trees
5. First order logic

B. Combinatorics and Recursion

1. Advanced Counting Methods
2. Induction
3. Recursion
4. Sequences and summations
5. Permutations and combinations
6. Recurrence relations and their closed solutions
7. Polynomial and exponential growth of functions; (f(n)) defined
8. Ramsey's Theorem

C. Algorithms

1. Algorithms and pseudo code
2. Divide and conquer
3. Sorting
4. Algorithms on graphs and trees
5. Measures of complexity space and time

a. Worst case ''run time"
b. Expected "run time"

6. Heuristic approximation

D. Feasible and non feasible computations

1. Polynomial time
2. Non Polynomial time
3. NP Completeness

1. Models of computation: Turing Machines
2. Busy Beaver Problem
3. Halting Problem

A. Books

A. V. Aho, J. E. Hopcroft, J.D. Ullman, The Design end Analysis of Computer Algorithms, Addison-Wesley, 1974.

A. B. Bender, S.G. Williamson, Foundations of Applied Combinatorics, Addison-Wesley, 1991.

Bogart, Discrete Mathematics, D.C. Heath and Company, 1988.

G. Chartrand, Introductory Graph Theory, Dover, 1977.

G. Chartrand, L. Lesniak, Graphs and Digraphs, Chapman and Hall, 1986.

Cormen, Leiserson, Rivest, Introduction to Algorithms, MIT Press, 1990.

Q. L. . Graham, D.E. Knuth, O. Patashnik, Concrete Mathematics, Addison-Wesley, 1991.

J. E. Hopcroft, J.D. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, 1979.

B. W. Jackson, D. Thoro, Applied Combinatorics with Problem Solving, Addison-Wesley, 1990.

H.R. Lewis, C.H. Papadimitriou, Elements of the Theory of Computation, Prentice Hall, 1981.

S. B. Maurer, A. Ralston, Discrete Algorithmic Mathematics, Addison-Wesley, 1 991.

N.C.T.M. Yearbook Discrete Mathematics Across the Curriculum K-12, 1991.

A. Ralston (editor), Discrete Mathematics in the First Two Years, M.A.A. Notes, Number 15, 1989.

B. Sagan, The Symmetric Group, Chapman and Hall, 1991.

S. Skiena, Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica, Addison-Wesley, 1990.

D.R. Stinson, Introduction to Design end Analysis of algorithms, The Charles Babbage Research Center, 1985.

B. Periodicals

In Discrete Mathematics ? Using Discrete Mathematics in the Classroom, Center for Discrete Mathematics and Theoretical Computer Science (DIMACS) at Rutgers University

The class will be conducted as a seminar/laboratory, where students can explore discrete structures, combinatorics and algorithms in a computer/mathematics lab. Students will be evaluated as a result of their performance on traditional examinations and on the quality of their laboratory work.

Admission into the Masters program

3 semester hours.

This course was examined in accord with the recommended procedures and was approved by the graduate faculty of the Mathematics Department on May 13, 1993.

_______________________________________Department Chair

CATALOG DESCRIPTION

MAT 670 - DISC MATH & COMP SCI Problems, theorems, and discrete structures commonly used in mathematics and computer science. This course will present a mathematical analysis of many algorithmic/computer solutions to problems in mathematics. In addition, the course will discuss mathematical problems which are not solvable by computer.

A Ph.D. in mathematics or mathematics education is the minimum formal education required. Beyond this, a person teaching this course should have experience with discrete structures, algorithms, and the theory of computation.

A software laboratory containing Macintosh computers (or workstations) with Mathematica (or some other combinatorial/graphics computing software).