MAT 281 Discrete Mathematics

This is a sample syllabus only. Ask your instructor for the official syllabus for your course.

Instructor:
Office:
Office hours:
Phone:
Email:

Course Description

Matrix algebra, graph theory, trees, combinatorics, Boolean algebra; with applications to computers and computer programming.

MAT 281 meets for three hours of lecture per week.

Prerequisites

MAT 271, and CSC 121 or MAT 241 or CSC 111 or equivalent with grades C or better. Students who enroll in MAT 281 are expected to be familiar with the following topics.

logic
set theory
techniques for proving theorems (e.g. mathematical induction, contradiction)
functions and relations
an introductory computer programming course

Objectives

MAT 281 provides mathematical foundations for various topics in discrete mathematics including those necessary for core computer science courses. Upon completing MAT 281 the student should be able to

use "big-oh" and "big-omega" notation
analyze the complexity of simple algorithms
understand and use permutations, combinations, binomial coefficients, the pigeonhole principle in algorithms and proofs
solve recurrence relations
understand basic concepts of graph theory: trees, binary trees, decision trees and apply them to problems e.g. sorting
understand combinatorial circuits and their properties; Boolean algebras; Boolean functions and synthesis of circuits.

Expected outcomes

Students should be able to demonstrate through written assignments, tests, and/or oral presentations, that they have achieved the objectives of MAT 281.

Method of Evaluating Outcomes

Evaluations are based on homework, class participation, short tests and scheduled examinations covering students' understanding of topics covered in MAT 281.

Text

Discrete Mathematics, by R. Johnsonbaugh. Macmillan Publishing Company, 1993.

Additional References

A. Gibbons, Algorithmic Graph Theory, Cambridge University Press, 1985.
R. L. Graham, D. E. Knuth, and O. Patashnik, Concrete Mathematics: A Foundation for Computer Science, Addison-Wesley, 1988.

Course Outline

Based on a 15 week course.

Week	Topics
1-2	Review of logic and set theory.
3	"Big-oh" and "big-omega" notation, analysis of complexity of the Euclidean algorithm.
4-5	Permutations, combinations, binomial coefficients, the Pigeonhole Principle.
6-7	Solving recurrence relations.
8-10	Graph theory: basic concepts, Euler cycles, Hamiltonian cycles, planar graphs.
11-13	Trees: basic concepts, characterization of trees, binary trees, decision trees, a lower bound for sorting.
14-15	Combinatorial circuits and their properties, Boolean algebras, Boolean functions and synthesis of circuits.
16	FINAL EXAM

Grading Policy

Students' grades are based on homework, class participation, short tests, and scheduled examinations covering students' understanding of the topics covered in MAT 281. The instructor determines the relative weights of these factors.

Attendance Requirements

Attendance policy is set by the instructor.

Policy on Due Dates and Make-Up Work

Due dates and policy regarding make-up work are set by the instructor.

Schedule of Examinations

The instructor sets all test dates except the date of the final exam. The final exam is given at the date and time announced in the Schedule of Classes.

Academic Integrity

The mathematics department does not tolerate cheating. Students who have questions or concerns about academic integrity should ask their professors or the counselors in the Student Development Office, or refer to the University Catalog for more information. (Look in the index under "academic integrity".)

Revision history:

Prepared by M. Suchenek 3/10/00. Edited by G. Jennings 7/8/01.