UNIVERSITY OF DAYTON

 

CPS 341  Discrete Structures

Winter Semester 2006       3 credits

Meets:  T,Th     1:30-2:45pm

 109 Miriam Hall

 Dr. Jennifer Seitzer

Syllabus

Description and Motivation


Discrete Structures is a course that examines the underlying background of virtually all computer science courses.  The kernels of knowledge that are found in this discipline are used heavily in Artificial Intelligence, Graphics, Human-Computer Interactions, Software Engineering, Computer Networking, Operating Systems, Computer Architecture, as well as many others.  Moreover, it contains the material constituting the essence of programming.  By mastering the concepts in discrete mathematics, one is training oneself to think like a computer scientist.

 

In this class, we will first study logic and deductive reasoning.  We consider the fundamental unit of our work to be the statement, an expression that is either true or false. By manipulating and navigating through sets of statements we become able to construct proofs.  A proof is a convincing argument expressed in the language of logic.  We will study the following proof techniques:  construction, choose, induction, specialization, contradiction, and contraposition.  A set is collection of items (e.g., data).  A definition is merely an agreement.  We use definitions to unambiguously decide on the parameters of an item or a set of items.  We will explore counting of sets, including techniques of permutations and combinations.  We will look at how sets interrelate in relations and functions.  And lastly, we will examine directed graphs.  Graphs are powerful tools of abstraction that pictorially depict relations as well as the behavior of many seminal algorithms in classical computer science.

 

Objectives:

·        To learn some of the parlance of logic and theoretical computer science.  In particular, know how to define: theorem, proposition, corollary, lemma, proof, truth table, definition, algorithm, relation, function, graph.

·        To learn the fundamentals of propositional and predicate logic

·        To know how to construct a proof using both forward and backward techniques.

·        To be able to write a proof using the techniques of direct proof, induction, and contradiction.

·        To be able to define and count sets using simple combinatoric techniques

·        To understand basic relation types including equivalence relations and partial orders

·        To distinguish between “one-to-one” and “onto” functions

·        To learn the basics of graph constructions and traversals

 

 

Lectures

 

Subject Matter   (Tentative list and schedule of coverage):

Week

Topics

Readings

 

1 – Week of  01/01/06

Introduction to Discrete Math

Chapter 1

2 -- Week of  01/08/06

Propositional Logic

Chapter 2

3 -- Week of  01/15/06

Predicate Logic and Derivation Rules

Chapters 3

4 -- Week of  01/22/06

Test 1 – Material so far;  Introduction to Proofs

Chapters 4 and 5

Last Day to Withdraw with no record Wednesday 1/25/2006

 

 

5 –  Week of 01/29/06

Direct Proof;  Proof by Contradiction; Proof by Contraposition;

 

6 --  Week of 02/05/06

Proof by Induction

 

7 --  Week of 02/12/06

Review of All Proof Techniques

 

8 --  Week of 02/19/06

Test 2 -- Proofs

 

9 –  Week of 02/26/06

Sets

 

10 -- Week of 03/05/06

Basic Combinatorics

 

Mid-Term Break

No Class 3/14//06 and 3/16/06

 

 

11--- Week of 03/19/06

Pigeon-hole principle;  Test 3 – Sets and Counting

 

Last Day to Withdraw with a  W;    Wednesday, 3/22/06

 

 

12--- Week of 03/26/06

Relations

 

Easter Break

No Classes Thur 4/13/2006

 

 

13 – Week of 04/02/06

Functions

 

14-- Week of 04/09/06

Introduction to Graph theory

 

15 --  Week of 04/16/06

Finite State Machines

 

16 – Week of 04/23/06

Turing Machines

 

FINAL EXAMINATION

Friday, May 5, 2006

1:30 – 2:45pm

 

 

 

 

 

Course Facilitators

 

Old Tests for Study Purposes

·        Old Test 1