# CS208 Discrete Mathematics

## for F2RR 2004

Course Syllabus

Course Title CS 208 Discrete Mathematics

Course Schedule 18 October – 12 December 2004

Class Session Days/Time Monday and Wednesday 1930 - 2200

Prerequisite Any math course greater than MA 131

Credit Hours The course is designed to provide a

3-credit hour course.

Required Text Johnsonbaugh, R., “Discrete Mathematics”,

Prentice Hall, 2005, 6th Edition.

ISBN 0-13-117686-2

Electronic Resources To help with Discrete Mathematics

problems—check out www.purplemath.com

http://condor.depaul.edu/~rjohnson/dm6th

The Website contains expanded explanations of difficult material and links to other sites for additional information about discrete mathematics topics.

Supplements Computer exercises occur throughout the book

on particular topics which are available at

the Web Site that accompanies this textbook.

Instructor’s Name Kathleen Green, PhD

Telephone 208-383-9070 (W)

Email kathyg@verdeaviation.com

Availability Feel free to call me between the hours of 8:00 am to 5:00 pm,Monday through Friday. If I am not available, please leave your message and I’ll call you back as quickly as I can.

MISSION STATEMENT

The mission of Park University, an entrepreneurial institution of learning, is to provide access to academic excellence, which will prepare learners to think critically, communicate effectively and engage in lifelong learning while serving a global community.

VISION STATEMENT

Park University will be renowned international leader in providing innovative educational opportunities for learners with the global society.

COURSE DESCRIPTION

This course introduces the student to selected finite systems pertinent to the study of computer science. Course topics will include the following: mathematical induction, sets, relations, functions, matrices, graphs, trees, combinatorial analysis, Boolean algebra, and other structures.

FACULTY’S EDUCATIONAL PHILOSOPHY

The instructor’s intent is to communicate with students rather than to lecture to them, and to convince the student that the study of discrete mathematics can be lively, interesting, and a rewarding experience. If the course succeeds you’ll be well started in mathematics or computer science—both use the same language and much of the same kind of thinking. There’s a secret to working tough problems: Try it repeatedly between periods of other activity, like sleeping. Go as far as you can, quit, and see what happens the next morning. Often you’ll have made progress, “by osmosis.” So my advice is to work a little bit every day on this subject rather than a lot just before a deadline. You may spend the same total amount of time either way; but you learn far more, or find better solutions to problems, if you spread out your efforts. Why? Because you’ll have more periods of osmosis. You’ll get more out of class.

COURSE OBJECTIVES

“On completion of this course, the student should be able to:<br>

1. Focus using logic on the relationship among statements as opposed to the content of any particular statement.

Discuss some general methods of proofs, one of which, mathematical induction, is used throughout mathematics and computer science.

2. Deal with the language of mathematics. Some of the topics are: sets, sequences, number systems, relations, and functions.

3. Understand the complexity of algorithms, which refers to the time and space required to execute algorithms, and the analysis of the resources required for particular algorithms.

4. Develop several tools for counting.

5. Define a sequence by giving the nth value in terms of certain of its predecessors using recurrence relation.

6. Discuss some important concepts in graph theory, including paths and cycles.

7. Make extensive use of trees.

8. Maximize the flow in a network.

9. Explore the relationship of Boolean algebra to circuits.

COURSE TEXTBOOK

Johnsonbaugh, R., “Discrete Mathematics,” Prentice Hall, 2005, 6th Edition.

ACADEMIC HONESTY

“Academic Honesty is required of all members of a learning community. Hence, Park will not tolerate cheating or plagiarism on tests, examinations, papers or other course assignments. Students who engage in such dishonesty may be given failing grades or expelled from Park.”

PLAGIARISM

Plagiarism—the appropriation or imitation of the language or ideas of another person and presenting them as one’s original work—sometimes occurs through carelessness or ignorance. Students who are uncertain about proper documentation of sources should consult their instructors.”

CLASSROOM RULES OF CONDUCT

The student shall, at all times, conduct themselves in a responsible and orderly manner, and shall appear for class in a sober and receptive condition. Violation of these conditions is cause for dismissal.

ATTENDANCE AND PARTIDIPATION POLICY (not applicable for Independent Study students)

Instructors are required to keep attendance records and report absences. The instructor may excuse absences for cogent reasons, but missed work must be made up within the term of enrollment. Work missed through unexcused absences must also be made up within the term of enrollment, but unexcused absences may carry further penalties. In the event of two consecutive weeks of unexcused absences in a term of enrollment, the student will be administratively withdrawn, resulting in a grade of “F”. An Incomplete will not be issued to a student who has unexcused or excessive absences recorded for a course. Students receiving Military Tuition Assistance (TA) or Veterans Administration (VA) educational benefits must not exceed three unexcused absences in the term of enrollment. Excessive absences will be reported to the appropriate agency and may result in a monetary penalty to the student. Reports of F grade (attendance or academic) resulting from excessive absence for students receiving financial assistance from agencies not mentioned above will be reported to the appropriate agency.

Each of you needs to actively participate in discussions relating to the subject materials for each week for full participation credit and to make this class an enjoyable learning experience for us all. You should read, analyze, and respond to questions and comments from fellow students and me. These may include additional questions from me, as the discussions evolve, not just the questions assigned at the end of the chapters. Don’t be afraid to express your opinion of the topics that we will discuss. Differences of opinion are normal; but the important thing about any disagreement is to differ with respect and to provide an explanation and clear factual basis for your different point of view.

LATE SUBMISSION OF COURSE MATERIALS

The instructor will not accept assignments late. Assignments not submitted on the due date will receive a grade of “zero”. Purchase your textbook well enough in advance, not having a textbook is NO excuse.

COURSE ASSESSMENT GRADING PLAN

Point Values for the Course Assignments

Homework Assignments 30 pts 100 – 90 A

MidTerm Examination 30 pts 89 – 80 B

Final Examination 30 pts 79 – 70 C

Participation 10 pts 69 – 60 D

Below 60 F

COURSE POLICIES

1. MidTerm and Final Examinations – Students are expected to take the MidTerm and Final Examination at the designated time and place. No makeup Exams will be given. The MidTerm Exam is scheduled for the Forth Week and the Final Exam is scheduled for the Eighth Week. Exam questions will test your understanding of the lectures and material presented in the textbook and demonstrations. Emphasis is placed on testing your understanding of the material presented in the course, rather than in testing memorization of facts and figures.

Each of the examinations given during the course will focus on the material just prior of that examination.

2. Homework Worksheets – Worksheets will be due by the end of the Term. The worksheet can be submitted electronically (via email) as MS Word documents to the Instructor.

COURSE TOPICS/DATES/ASSIGNMENTS

Week One: 18 October 2004

Chapter 1: Logic and Proofs

1.1 Propositions

1.2 Conditional Propositions and Logical Equivalence

1.3 Quantifiers

1.4 Nested Quantifiers

ASSIGNMENT

· Read Chapter 1 in the text, Discrete Mathematics.

· Do problems on WorkSheet – Chapter One.

Week One: 20 October 2004

Chapter 1: Logic and Proofs

1.5 Proofs

1.6 Resolution Proofs

1.7 Mathematical Induction

1.8 Strong Form of Induction and the Well-Ordering Property

Week Two: 25 October 2004

Chapter2: The Language of Mathematics

2.1 Sets

2.2 Functions

2.3 Sequences and Strings

ASSIGNMENTS

· Read Chapter 32 in the text, Discrete Mathematics.

· Do problems on WorkSheet – Chapter Two.

Week Two: 27 October 2004

Chapter 3: Relations

3.1 Relations

3.2 Equivalence Relations

3.3 Matrices of Relations

3.4 Relational Databases

ASSIGNMENTS

· Read Chapter 3 in the text, Discrete Mathematics.

· Do problems on WorkSheet – Chapter Three.

Week Three: 01 November 2004

Chapter 4: Algorithms

4.1 Introduction

4.2 Examples of Algorithms

4.3 Analysis of Algorithms

4.4 Recursive Algorithms

ASSIGNMENTS

· Read Chapter 4 in the text, Discrete Mathematics. Do problems on WorkSheet – Chapter Four.

Week Three: 03 November 2004

Chapter 5: Introduction to Number Theory

5.1 Divisors

5.2 Representations of Integers and Integer Algorithms

5.3 The Euclidean Algorithm

5.4 The RSA Public-Key Cryptosystem

ASSIGNMENTS

· Read Chapter 5 in the text, Discrete Mathematics.

· Do problems on WorkSheet-Chapter Five.

Week Four: 08 November 2004

Chapter 6: Counting Methods and the Pigeonhole Principle

6.1 Basic Principles

6.2 Permutations and Combinations

6.3 Algorithms for Generating Permutations and Combinations

6.4 Introduction to Discrete Probability

6.5 Discrete Probability Theory

6.6 Generalized Permutations and Combinations

6.7 Binomial Coefficients and Combinatorial Identities

6.8 The Pigeonhole Principle

ASSIGNMENTS

· Read Chapter 6 in the text, Discrete Mathematics.

· Do problems on WorkSheet-Chapter Six.

Week Four: 10 November 2004

MidTerm Examination

Week Five: 15 November 2004

Chapter 7: Recurrence Relations

7.1 Introduction

7.2 Solving Recurrence Relations

7.3 Applications to the Analysis of Algorithms

ASSIGNMENTS

· Read Chapter 7 in the text, Discrete Mathematics.

· Do problems on WorkSheet-Chapter 7.

Week Five: 17 November 2004

Chapter 8: Graph Theory

8.1 Introduction

8.2 Paths and Cycles

8.3 Hamiltonian Cycles and the Traveling Salesperson

Problem

8.4 A Shortest-Path Algorithm

8.5 Representations of Graphs

8.6 Isomorphisms of Graphs

8.7 Planar Graphs

8.8 Instant Insanity

ASSIGNMENTS

· Read Chapter 8 in the text, Discrete Mathematics.

· Do problems On WorkSheet – Chapter 8.

Week Six: 22 November 2004

Chapter 9: Trees

9.1 Introduction

9.2 Terminology and Characterizations of Trees

9.3 Spanning Trees

9.4 Minimal Spanning Trees

9.5 Binary Trees

9.6 Tree Traversals

9.7 Decision Trees and the Minimum Time for Sorting

9.8 Isomorphisms of Trees

9.9 Game Trees

ASSIGNMENTS

· Read Chapter 9 in the text, Discrete Mathematics.

· Do problems on WorkSheet – Chapter 9.

Week Six: 24 November 2004

Chapter 11: Boolean Algebras and Combinatorial Circuits

11.1 Combinatorial Circuits

11.2 Properties of Combinatorial Circuits

11.3 Boolean Algebras

11.4 Boolean Functions and Synthesis of Circuits

11.5 Applications

ASSIGNMENTS

· Read Chapter 11 in the text, Discrete Mathematics.

· Do problems on WorkSheet – Chapter 11.

Week Seven: 29 November 2004

Chapter 12: Automata, Grammars, and Languages

12.1 Sequential Circuits and Finite-State Machines

12.2 Finite-State Automata

12.3 Languages and Grammars

12.4 Nondeterministic Finite-State Automata

12.5 Relationships Between Languages and Automata

ASSIGNMENTS

· Read Chapter 12 in the text, Discrete Mathematics.

· Do problems on WorkSheet - Chapter 12.

Week Seven: 01 December 2004

Chapter 13: Computational Geometry

13.1 The Closest-Pair Problem

13.2 An Algorithm to Compute the Convex Hull

ASSIGNMENTS

Read Chapter 13 in the text, Discrete Mathematics.

· Do problems on WorkSheet – Chapter 13.

Week Eight: 06 December 2004

Review

Week Eight: 08 December 2004

Final Examination