C S 1813 Discrete Mathematics

Catalog description

Introduction to the mathematical foundation of computer science. Topics include combinatorics, logic, relations, functions, computational complexity, automata, and graph theory.

Prerequisites

C S 1323.

Audience

Freshman computer science majors and majors pursuing the computer engineering option or computer science option.

Frequency

Twice a year during fall and spring semesters.

Format

Lecture, three hours per week.

Laboratory

None.

Recommended texts

  • Discrete Mathematics and Its Applications, Kenneth Rosen, 4th edition, McGraw-Hill, 1999.

    Supplementary texts

  • Discrete Mathematics and Its Applications Solutions Manual, Kenneth Rosen, 4th edition, McGraw-Hill, 1999.

    Typical schedule of topics

    1. Logic - truth tables, logical equivalences, quantifiers, methods of proof
    2. Mathematical induction - principle of mathematical induction, recursive definitions
    3. Relations and functions - Cartesian products and relations, functions, equivalence relations, composition, partitions, partial orders
    4. Notation for computational complexity - definitions, order classes
    5. Automata - languages, finite state machines
    6. Graph theory - definitions, Euler paths, trees
    Discrete Mathematics / Course descriptions / OU School of Computer Science / 22 August 2000