Length of course:   One semester ( 14 weeks )

 

Classroom hours per week:  Four hours of lectures

 

 

Prerequisite:  Mathematics 113 or mathematics 111 with a minimum grade of B

 

Audience:   This course is designed for students of Mathematics, Computer Science or Engineering

 

Calendar description:  An elementary course in discrete mathematics introducing topics in logic, theory of sets and functions, asymptotics, algorithms, number theory, matrices, mathematical induction, recursive definitions and algorithms, permutations and combinations, theory of relations, graphs and trees.

 

1.   Logic, Sets, Functions  ( 3 weeks ) Propositions, logical connectives, truth tables, predicates and quantifiers, sets, set operations, cardinality, functions, sequences and summations, growth of functions and the big-O notation.

 

2.   Algorithms, Integers, Matrices  ( 3 weeks ) Algorithms and their complexity, search algorithms, the integers, primes, Euclidean algorithm, modular arithmetic, different bases, lcm, gcd, matrices and matrix operations

 

3.   Mathematical reasoning   ( 2 weeks )  Rules of inference, methods of proof, proof by contradiction, mathematical induction, recursively defined functions and sets, recursive algorithms, program correctness

 

4.   Counting   ( 2 weeks )  Basic methods of counting, permutations and combinations, the binomial theorem, the pigeonhole principle.

 

5.   Relations   ( 2 weeks )  Relations n-ary relations, equivalence relations, representing relations with matrices and digraphs, closures of relations, partial orderings.

 

6.   Graphs and trees   ( 1 week )  Definitions and terminology, graph connectivity, introduction to trees

 

Textbook:   Discrete Mathematics and its Applications, 4th edition  Kenneth H. Rosen

Sections of the text covered: