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 informa­tion, 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