Discrete Mathematics
Course Objective.
The goal of this course is to help students to understand, explain, and apply the foundational mathematical concepts at the core of computer science.
Catalog Course Description
This course enables students to strengthen and increase the understanding of discrete mathematics with special emphasis on computer science applications. Topics include sets, number systems, the nature of proof, formal logic, functions and relations, combinatorics, recurrence relations, trees and Boolean algebra.
Required Course Content and Direction
REFERENCE, RESOURCE, OR LEARNING MATERIALS TO BE USED BY STUDENT:
There is a departmentally selected textbook and calculator. The instructor will provide specific details for each section. See course syllabus.
The goal of this course is to help students to understand, explain, and apply the foundational mathematical concepts at the core of computer science.
Catalog Course Description
This course enables students to strengthen and increase the understanding of discrete mathematics with special emphasis on computer science applications. Topics include sets, number systems, the nature of proof, formal logic, functions and relations, combinatorics, recurrence relations, trees and Boolean algebra.
Required Course Content and Direction
 COURSE LEARNING GOALS Students will:
 demonstrate an understanding and apply the concepts and procedures for expressing mathematical ideas clearly, precisely and unambiguously;
 demonstrate a proficiency in analyzing an argument's form to determine whether the truth of the conclusion follows necessarily from the truth of the premises;
 apply the logic of quantified statements and the precision of thought and language to achieve a mathematical certainty;
 demonstrate a proficiency in discovering and characterizing regular patterns associated with repeated processes;
 apply the concepts of set theory, including Boolean logic and work with functions such as discrete sets, onetoone and onto, existence of inverse functions, and the interaction of composition of functions and the properties of onetoone and onto; and
 apply the concept of equivalence relations as used in modular arithmetic and cryptography.
 PLANNED SEQUENCE OF TOPICS AND/OR LEARNING ACTIVITIES
 variables and the language of sets, relations and functions
 logic of compound statements
 logic of quantified statements
 elementary number theory and methods of proof
 sequences, mathematical induction and recursion
 set theory
 functions and relations
 counting and probability
 ASSESSMENT METHODS FOR COURSE LEARNING GOALS
REFERENCE, RESOURCE, OR LEARNING MATERIALS TO BE USED BY STUDENT:
There is a departmentally selected textbook and calculator. The instructor will provide specific details for each section. See course syllabus.
Required Readings

Unit 1: Course Materials
•Definitions: set, element
•Terminology and notation •Set equal, multiset, bag, set builder, intension, extension, Venn Diagram (representation), empty set, singleton set, subset, proper subset, finite/infinite set, cardinality •Proving equivalences •Power set •Tuples (ordered pair) •Cartesian Product (a.k.a. Cross product), relation •Quantifiers •Set Operations (union, intersection, complement, difference), Disjoint sets •Set equivalences (cheat sheet or Table 1, page 124) •Inclusion in both directions • Using membership tables •Generalized Unions and Intersection •Computer Representation of Sets 

Unit 2: Course Materials
•We will study
–Propositional Logic (PL) –FirstOrder Logic (FOL) •Defining Propositional Logic –Propositions –Connectives –Precedence of Logical Operators –Truth tables •Usefulness of Logic –Bitwise operations –Logic in Theoretical Computer Science (SAT) –Logic in Programming •Logical Equivalences –Terminology –Truth tables –Equivalence rules 

Unit 3: Course Materials
Motivation
•Terminology •Rules of inference: •Modus ponens, addition, simplification, conjunction, modus tollens, contrapositive, hypothetical syllogism, disjunctive syllogism, resolution, •Examples •Fallacies •Proofs with quantifiers •Types of proofs: •Trivial, vacuous, direct, by contrapositive (indirect), by contradiction (indirect), by cases, existence and uniqueness proofs; counter examples •Proof strategies: •Forward chaining; Backward chaining; Alertsectives 

Unit 4: Course Materials
•Relation:
–Definition, representation, relation on a set •Properties –Reflexivity, symmetry, antisymmetric, irreflexive, asymmetric •Combining relations composite of relations •Representing relations –01 matrices, directed graphs •Closure of relations –Reflexive closure, diagonal relation, Warshall’s Algorithm, •Equivalence relations: Equivalence class, partitions, 

Unit 5: Course Materials
Review before Midterm Exam


Unit 6: Course Materials
•Motivating example
•Definitions –Partial ordering, comparability, total ordering, well ordering •Principle of wellordered induction •Lexicographic orderings •Hasse Diagrams •Extremal elements •Lattices •Topological Sorting 

Unit 7: Course Materials
•Motivation
•What is induction? –Viewed as: the WellOrdering Principle, Universal Generalization –Formal Statement –6 Examples •Strong Induction –Definition –Examples: decomposition into product of primes, gcd 

Unit 8: Course Materials
•Introduction & definition
•Algorithms categories & types •Pseudocode •Designing an algorithm –Example: Max •Greedy Algorithms –Change 

Unit 9: Course Materials
•Introduction
•Terminology: –Propositional functions; arguments; arity; universe of discourse •Quantifiers –Definition; using, mixing, negating them •Logic Programming (Prolog) •Transcribing English to Logic •More exercises 
Unit 10: Course Materials
•Introduction
•Input Size •Order of Growth •Intractability •Worst, Best, and Average Cases •Mathematical Analysis of Algorithms –3 Examples •Summation tools 

Unit 11: Course Materials
•Introduction, Motivating Example
•Recurrence Relations –Definition, general form, initial conditions, terms •Linear Homogeneous Recurrences –Form, solution, characteristic equation, characteristic polynomial, roots –Second order linear homogeneous recurrence •Double roots, solution, examples •Single root, example –General linear homogeneous recurrences: distinct roots, any multiplicity •Linear Nonhomogenous Recurrences •Other Methods –Backward substitution –Recurrence trees –Cheating with Maple 

Unit 12: Course Materials
•Introduction
•Counting: –Product rule, sum rule, Principal of Inclusion Exclusion (PIE) –Application of PIE: Number of onto functions •Pigeonhole principle –Generalized, probabilistic forms •Permutations •Combinations •Binomial Coefficients •Generalizations –Combinations with repetitions, permutations with indistinguishable objects •Algorithms –Generating combinations (1), permutations (2) •More Examples 


**Teaching Improvement:
Please feel free to make suggestions to improve the content of the class and my instruction skills. You can tell these suggestions directly to me or anonymously leave your comments in my mailbox .
**Teaching Improvement:
Please feel free to make suggestions to improve the content of the class and my instruction skills. You can tell these suggestions directly to me or anonymously leave your comments in my mailbox .