Course
Syllabus
Ohio
Northern University
College of Arts
and Sciences
Department of
Mathematics
Date: Fall
2005
Course Math-
336 Name: Discrete
Mathematics
Credit hours 4 Lecture
hours/week 4
Lab hours/week 0
Instructor Mihai
Caragiu
Usual student level Junior/Senior
Course required of students in Electrical
& Computer Engineering and
Computer Science
Course frequency per year Fall
and Winter Quarters
Average enrollment per year 40-50
This course has a prerequisite Math
164
This course is a prerequisite for none
Catalogue
description
An introduction to discrete mathematical
structures: sets, logic,
combinatorics, relations and
digraphs, functions, elementary graph
theory, partially ordered sets, lattices and Boolean
Algebras, Karnaugh
maps and simple circuit design.
Course
Objectives
To
provide
mathematical background for addressing discrete sets
and structures
defined on
them as well as for concepts used in computer science.
Textbook: Discrete Mathematics and It’s
Applications, 5th edition,
by Kenneth H. Rosen
Course
Outline - Math 336 - Discrete
Mathematics
Propositional Calculus
Truth Tables
Logical Equivalences and Tautologies
Predicate Calculus
Nested Quantifiers
Methods of Proof
Sets and Set Operations
Set identities and Venn Diagrams
Functions
Injective, Surjective and Bijective Functions
Growth of Functions
Integers and Division
Prime Factorization and Primality Testing
Representation of Integers in Various Bases
The Euclid Algorithm and the Extended Euclid Algorithm
Congruences
Modular Arithmetic with Applications to Cryptography
Mathematical Induction
Recurrent Sequences and Solving Recurrence Relations
Fibonacci Numbers
Permutations and Combinations
Inclusion-Exclusion Principle
The Pigeonhole Principle
The Binomial Theorem, Binomial Coefficients
Combinatorial Identities
Discrete Probability
Relations and their Properties
Operations with Relations
Digraphs
Transitive Closure
Equivalence Relations and Partitions
Order Relations, Posets
Extremal Elements in Posets
Lattices and Finite Boolean Algebras
Graphs
Special Types of Graphs: Eulerian, Hamiltonian, Planar, Bipartite
Connectivity
Graph Coloring
Trees and their Applications
Spanning Trees
Boolean Functions and Boolean Expressions
Minterms and Disjunctive Normal Forms
Simplifying Boolean Expresions: Karnaugh Maps
Modeling Computation: Grammars and Automata
Discrete
mathematics is a
subset of the language of mathematics used to describe various features
of
discrete sets and structures defined on them. A discrete set is a
set
whose elements can be isolated, in some sense, from each other. All
finite sets
and some infinite sets (e.g. the set of integers) are discrete.
Discrete
mathematics is useful in a wide variety of disciplines. Chemists
study
isomers (rearrangements of discrete sets of atoms) of compounds.
Civil
engineers deal with discrete sets of objects to design and construct
bridges
and other structures. Computer scientists use discrete sets to
represent
data storage, languages and networks. Electrical engineers
manipulate the
elements in discrete sets to construct circuits and hardware
systems.
Physicists heavily use discrete models of continuous physical
systems arising in statistical mechanics, field theory, etc. Biologists
examine the behavior of discrete sets of individuals in a
population.
Discrete mathematics is the common thread.