MA 219

Mathematics Department
Indiana University of Pennsylvania
Indiana, PA 15705

Course Number:		MA 219

Course Title:		Discrete Mathematics

Credits:		3 semester hours

Prerequisites:		CO 110 and MA 123, MA 127, or MA 122

Textbook:		Discrete Mathematical Structures for Computer Science 
			by Kolman and Busby
			Prentice Hall

Revised:		9/92

Catalog Description:

Topics include set algebra, mappings, relations, semigroups, groups, directed and undirected graphs, Boolean algebra, and propositional logic, with examples and applications of these various areas of computer science. Emphasis is placed on developing an intuitive understanding of basic structures rather than formal theories and influence of these topics on theory and practice of computing.

Course Outline/Time Schedule:

I.	Fundamentals(8-9 hours)
	A.  Sets and Subsets
	B.  Sequences
	C.  Operations on Sets
	D.  Counting Sequences and Subsets
	E.  Algorithms and Pseudocode
	F.  Induction and Recursion
	G.  Division in the Integers
	H.  Matrices

II.	Relations and Digraphs(7 hours)
	A.  Product Sets and Partitions
	B.  Relations and Digraphs
	C.  Paths in Relations and Digraphs
	D.  Properties of Relations
	E.  Computer Representations of Relations and Digraphs
	F.  Manipulation of Relations
	G.  Connectivity and Warshall's Algorithm
III.	Functions(3-4 hours)
	A.  Functions
	B.  Permutations

IV.	Trees and Languages(7-8 hours)
	A.  Trees
	B.  Labeled Trees
	C.  Languages
	D.  Representations of Special Grammars
	E.  Tree Searching
	F.  Undirected Trees

V.	Semigroups and Groups(6-7 hours)
	A.  Binary Operations
	B.  Semigroups
	C.  Products and Quotients of Semigroups
	D.  Groups
	E.  Products and Quotients of Groups

VI.	Finite-State Machines and Languages(5-6 hours)
	A.  Finite-State Machines
	B.  Semigroups, Machines, and Languages
	C.  Machines and Regular Languages
	D.  Simplification of Machines

Depending on orientation and time, one may include the following topics:

VII.	Order Relations and Structures(6-7 hours)
	A.  Partially Ordered Sets
	B.  Extremal Elements of Partially Ordered Sets
	C.  Lattices
	D.  Boolean Algebra
	E.  Implementation of Boolean Functions

VIII. Groups and Coding
A.  Coding of Binary Information and
    Error Detection(3-4 hours)
	B.  Decoding and Error Correction

Read this disclaimer.

Maintained by Charles Lamb <clamb@iup.edu>
Last Modified on Monday, 13-Aug-2001 16:53:18 EDT