5/00
MATHEMATICS
211
INTRODUCTION
TO THE MATHEMATICS OF COMPUTER SCIENCE
I. Introduction
A. Catalog Description
An introduction to the mathematics
underlying computer science. Topics
include a review of basic set theory, logic (propositional and predicate),
theorem proving techniques, logic as a method for representing information,
equivalence relations, induction, combinatorics, graph theory, formal languages
and automata. Prerequisites: Math 121 or Math
258 or equivalent.
B. Objectives
This course helps provide the necessary
background in mathematics for computer science while giving other students an
exposure to the field of discrete mathematics.
C. Prerequisites
Math 121 or Math 258 or
equivalent. A grade of C- or better is
required in the prerequisite course.
II. Required
Topics
1. Sets, relations, equivalence relations,
functions, the relational algebra.
2. Propositional logic: truth tables, Boolean
algebra, logic circuits.
3. Predicate logic: representing knowledge in logic, the relational calculus.
4. Proof techniques: modus ponens, modus tollens, converse and contrapositive, proof
by contradiction
5. Induction.
6. Basic combinatorics, permutations,
combinations
7. Recurrence relations and generating functions
8. Graph theory, paths and connectedness, trees
9. Formal languages, grammars, and models for
computation
This course presents covers a diverse
collection of topics needed for a variety of computer science courses. In the course discrete mathematics is
presented as a sub field of mathematics by integrating the topics so that
students see them as a related series instead of a diverse collection of
unrelated topics. Relationships with
other areas of mathematics and computer science will also be emphasized.
The evaluation criteria will be those
standard to mathematics courses.
Homework: Assigned daily and collected weekly.
Midterm Exams: Three or four spread over the semester.
Final Exam: Comprehensive (given during exam week)
III. Bibliography
Aho and Ullman Foundations of Computer Science
Graham, Knuth, and Patashnik Concrete Mathematics: A Foundation for Computer Science
Grimaldi Discrete & Combinatorial
Mathematics: An Applied Introduction
Hirschfelder &
Hirschfelder Introduction to
Discrete Mathematics
Knuth, Donald:
The Art of Computer Programming, Vol I:
Fundamental Algorithms
Kolman, Busby,
Ross Discrete Mathematical Structures
Skvarcius and
Robinson Discrete Mathematics with
Computer Science Applications