# MAT 281 Discrete Mathematics

Instructor:
Office:
Office hours:
Phone:
Email:

### Updated Course Description

Logic and sets, functions and relations, Boolean algebra and circuit design, mathematical induction, recursion, modular arithmetic and elementary number theory, counting techniques and combinatorics, big-O notation and complexity of algorithms, graphs and trees; with applications to computers and computer programming.

MAT 281 meets for three hours of lecture per week.

### Prerequisites

MAT 153, and CSC 121 or MAT 241 or CSC 111 or equivalent with grades C or better.

### 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

• construct and understand rigorous logical arguments and inferences
• construct and understand proofs by mathematical induction
• understand and use permutations, combinations, binomial coefficients, the pigeonhole principle, in algorithms, counting arguments, and proofs
• use "big-oh" and "big-omega" notation
• analyze the complexity of simple algorithms
• understand basic concepts and algorithms of graph theory
• understand combinatorial circuits and their properties; 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 Structures with Contemporary Applications, by A. Stanoyevitch. Chapman & Hall (2011)

### Course Outline

Based on a 15 week course.

Week Topics
1-2 Logic and sets.
3-4 Functions and relations, equivalence relations
5-6 Mathematical induction and recursion
7-8 Modular arithmetic and elementary number theory
9-10 Counting techniques and combinatorics
11-12 Big-O notation and the complexity of algorityms
13-14 Graphs and trees
15 Boolean algebra and circuit design

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.