UW COLLEGES

DEPARTMENT OF MATHEMATICS

COURSE GUIDELINES

Course Title Discrete Mathematics_______________________

Course No. MAT 230__

Contact hrs/wk: Lecture __ Lecture/Discussion __3__ Lab ____

Course Prerequisites: A grade of C or better in MAT 221, or equivalent.

Catalog description: An introduction to discrete mathematics with emphasis on topics applicable to computer science. Topics include symbolic logic, sets and relations, induction and recursion, counting techniques, algorithm analysis, graphs and digraphs and Boolean algebra.

Course content (list of topics normally covered):

1. Symbolic logic (propositional and quantifier logic)

2. Set theory and axiomatic systems

3. Relations

4. Graphs and digraphs

5. Proofs (by induction, by contradiction, by cases)

6. Counting techniques (permutations, combinations, pigeonhole principle)

7. Functions over the natural numbers

8. Big Oh notation

9. Boolean algebras

10. Analysis of algorithms

11. Some elementary number theory

12. Exposure to mathematical culture and history (e.g., viewing and discussing the videos “Fermat’s Last Theorem”, “N is a Number” (about Paul Erdös), “Archimedes’s Palimpsest”)

Content-based department proficiencies:

The successful student will:

· Learn how to construct proofs of various sorts, e.g., proof by contradiction or by induction.

· Become familiar with the use of logic in formalizing statements and analyzing proofs, with the role of axioms, and with the formalization of mathematics.

· Become familiar with properties and operations of sets, properties of relations between sets, the graphs (digraphs) of the latter, the importance of equivalence relations, and their connection with partitions and the latter’s usefulness in combinatorics.Become familiar with a variety of counting techniques (permutations, combinations, partitions, the pigeonhole principle).

· Analyze algorithms, definitions by induction and by recursion.

· Become familiar with some number theory.

· Develop the beginnings of a foundation for upper division mathematics courses and theoretical computer science courses.

· Develop an appreciation for the human history and culture of mathematics.

Colleges-wide proficiencies assigned to course:

Students should be able to demonstrate the following:

A. Analytical skills Performance Indicators: Students should be able to:

1. Interpret and synthesize information and ideas.

4. Select and apply scientific and other appropriate methodologies.

B. Quantitative skills Performance Indicators: Students should be able to:

1. Solve quantitative and mathematical problems.

2. Interpret graphs, tables, and diagrams.

Representative textbooks used for the courses:

· Mathematics: A Discrete Introduction by Edward Scheinerman

· Discrete Mathematics and Its Applications by Kenneth Rosen

Approved April 22, 2006