Finite Mathematics - CS 4/51012
Fall 2002

Tuesday, Thursday 3:15 - 4:30 p.m.
MSB 121

Instructor
Office Hours

Email
Telephone

Dr. Feodor Dragan
Room 254 MSB
Tue, Thu 4:30 - 6:30 PM
and by appointment
dragan@cs.kent.edu
(330)672-9058

Teaching Assistant
Office Hours

Email
Telephone

????? ?????
Room ??? MSB
???, ??? ?? - ?? p.m.
and by appointment
????que@cs.kent.edu
(330)672-9???

WWW http://www.cs.kent.edu/~dragan/CS4-51012-FM.html
Course Description

A continuation of discrete mathematics; emphasizing combinatorial techniques, graph applications in algorithms, finite algebra, number theory and probability. Covers useful mathematics for CS majors.

Prerequisites

CS 31011 or MATH 31011

Text

James A. Anderson, Discrete Mathematics with Combinatorics, Prentice Hall, 2001. (order on-line)
Richard Johnsonbaugh, Discrete Mathematics, 5/E, Prentice Hall, 2001. (order on-line)

Supplementary Text

Douglas B. West, Introduction to Graph Theory, 2/E, Prentice Hall, 2001. (order on-line)
Bernard Kolman, Robert C. Busby, Sharon Cutler Ross, Discrete Mathematical Structures, 4/E, Prentice Hall, 2000. (order on-line)
Martin Charles Golumbic, Algorithmic Graph Theory and Perfect Graphs, Academic Press, New York, 1980.

Topics will include:

- Boolean Algebra and Combinatorial Circuits:
Combinatorial Circuits, Properties of Combinatorial Circuits, Boolean Algebras, Boolean Functions and Synthesis of Circuits, Applications

- Graphs, Trees, and Networks:
Euler Paths and Cycles, Representations of Graphs, Hypercubes and Gray Code, Binary Search Trees, Traversing Trees, Spanning Trees, Networks and Flows, Matching, Petri Nets, Planar Graphs, Coloring Graphs, Hamiltonian Paths and Cycles, Cliques and Independent Sets, Perfect Graphs, Intersection Graphs, Isomorphisms of Trees, Reconstruction of Graphs, Weighted Graphs

- Algebraic Structures:
Partially Ordered Sets, Lattices, Semilattices

- Counting and Discrete Probability:
Permutations and Combinations, Generalized Permutations and Combinations, Pigeonhole Principle, Discrete Probability, Bayes Theorem, Markov Chains, Occupancy Problems, Catalan Numbers

- Theory of Codes:
Generator Matrices, Hamming Codes, Coding of Binary Information and Error Detection, Decoding and Error Correction

Course Requirements

Homework	-	-	-	30%
Midterm Exam	TBA	October ??, 2002	3:15 - 4:30 pm	35%
Final Exam	Wednesday,	December 11, 2002	7:45 - 10:00 am	35%

Milestone for successful completion of the course

Attend the classes regularly,
Perform the homework thoroughly and independently,
Read the book carefully and several times.

Students with Disabilities

In accordance with university policy, if you have a documented disability and require accommodations to obtain equal access in this course, please contact the instructor at the beginning of the semester or when given an assignment for which an accommodation is required. Students with disabilities must verify their eligibility through the Office of Student Disability Services (SDS) in the Michael Schwartz Student Services Center (672-3391).

F. Dragan
dragan@cs.kent.edu
Fall 2002

Finite Mathematics - CS 4/51012 Fall 2002

Finite Mathematics - CS 4/51012
Fall 2002