# CS208 Discrete Mathematics

## for S2W 2005

PU 100

CS208 - Discrete Math

Park University Course Syllabus

Benny Phillips, Ph.D., Academic Director @ Tinker AFB

benny.phillips@park.edu

(405) 378 6138

Spring II 2005

Monday 3/21/05Sunday 5/15/05

M-W 4:30PM-7:20PM

Park University Vision

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

Park University Mission

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.

Course Description

This course introduces the student to selected finite systems pertinent to the study of computer science. Course topics will include the following: sets, relations, functions, matrices, graphs, trees, combinatorial analysis, Boolean algebra. The course may also cover recurrence relations, induction, and propositional calculus. Prerequisite: MA 131 (or any math course > MA 131). 3:0:3

I. Overview and Course Goals

This course introduces the student to selected finite systems pertinent to the study of computer science. Course topics include: mathematical induction, sets, relations, functions, matrices, graphs, trees, combinatorial analysis. Prerequisite: MA 131 or higher-level course.

II. Course Objectives

Upon the successful completion of this course students will be able to:

• Describe basic properties of sets, bags, tuples, relations, graphs, trees, and functions.
• Perform traversals of graphs and trees; construct simple functions by composition of known functions; determine whether simple functions are injective, surjective, or bijective; and classify simple functions by rate of growth.
• Describe the concepts of countable and uncountable sets, and apply the diagonalization method to construct elements that are not in certain countable sets.
• Construct inductive definitions for sets, construct grammars for languages (sets of strings), and construct recursive definitions for functions and procedures.
• Determine whether a binary relation is reflexive, symmetric, or transitive and construct closures with respect to these properties.
• Construct a topological sort of a partially ordered set and determine whether a partially ordered set is well-founded.
• Use elementary counting techniques to count simple finite structures that are either ordered or unordered, to count the worst case number of comparisons and, with discrete probability, to count the average number of comparisons for simple decision trees.
• Find closed form solutions for simple recurrences using the techniques of substitution, cancellation, and generating functions.
• Demonstrate standard proof techniques and the technique of inductive proof by writing short informal proofs about simple properties of numbers, sets, and ordered structures.
• Solve problems involving elementary logic, predicate logic, applied logic, computational logic, and Boolean algebra.
• Use Visual Prolog as an experimental tool for testing properties of discrete structures.

III. Required Texts/Materials

James Hein, Discrete Mathematics, 2nd Edition, Jones and Bartlett Publishers, Inc., 2003, ISBN 0-7637-2210-3.

IV. Course Policies

Individual homework must be done independently. You may ask procedural or conceptual questions to your classmates. However, you may not ask for or obtain a classmate’s homework answers. If you copy part of someone else's work, if someone else copies part of your work, or if you do not work independently, you will receive zeros on the current and previous homework assignments. In addition, if you are caught cheating or plagiarizing, you may receive one of the following: an immediate “F” in the course, referral to university authorities for further discipline, expulsion from Park University.

Attendance

It is a Park University Attendance Policy that failure to attend class for two consecutive weeks will result in an automatic withdrawal from the course.  Failure to attend class will also affect the participation grade.

Homework

Homework must be turned in no later than the beginning of the class period on which it is due. Normally, if you turn in a homework assignment later than that, then that homework's score will be reduced by one-quarter for each intervening class period before the homework is turned in.

Exams

There will be a midterm exam, a term project, and a final exam.

Make-Up Exams

You will be allowed to take a make-up test only if you give me a note that is signed by a doctor, sports coach, or funeral director, and the signer's phone number is on the note. Make-up tests will tend to be harder than the original tests. All make-up tests must be taken within one week of the original test's date.

If you are a student with a disability, and if you will be requesting accommodations, it is your responsibility to contact the proper school services.

Other

The schedule and procedures for this course are subject to change in the event of extenuating circumstances.

Individual project (25%)

Participation (25%)

Midterm exam (25%)

Final exam (25%)

90% – 100% (A)

80% - 89% (B)

70% - 79% (C)

60% - 69% (D)

Less than 60% (F)

Academic honesty is the prerequisite for academic study. Academic dishonesty is inimical to the spirit of a learning community. Hence, Park will not tolerate cheating or plagiarism on tests, examinations, papers, and other course assignments. Students who engage in such dishonesty may be given failing grades or expelled from Park.

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. This does not make it less serious. However, students who are uncertain about proper documentation of sources should consult their course faculty member.

VII. Participation and Attendance

Professors are required to keep attendance records and report absences throughout the term. Excused absences can be granted by the instructor for medical reasons, school sponsored activities, and employment-related demands including temporary duty. The student is responsible for completing all missed work. Absences in excess of four (4) class periods (2 weeks in a term) will be reported to the Dean for appropriate action. Any student who misses class for two consecutive weeks, without an approved excuse, will be institutionally withdrawn, and notified by mail that an "F" will be recorded.

IX. Course Activities

Week1:

Read Chapters 1, 2, and solve problems posted in eCompanion.  Also, post your solutions in eCompanion for tracking purposes.

Week2:

Read Chapters 3, 4, and solve problems posted in eCompanion.  Also, post your solutions in eCompanion for tracking purposes.

Week3:

Read Chapters 5, and solve problems posted in eCompanion.  Also, post your solutions in eCompanion for tracking purposes.

Week4:

Review, Midterm Exam

Week5:

Read Chapters 6, 7, and solve problems posted in eCompanion.  Also, post your solutions in eCompanion for tracking purposes.

Week6:

Read Chapters 8, 9, and solve problems posted in eCompanion.  Also, post your solutions in eCompanion for tracking purposes.

Week7:

Read Chapter 10, and solve problems posted in eCompanion.  Also, post your solutions in eCompanion for tracking purposes.

Week8:

Review, Term Project due, Final Exam

Term Project:

Option 1: