# CS208 Discrete Mathematics

## for S2W 2005

**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/05**** – ****Sunday 5/15/05**

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

**Park**** **
**University**** Vision**

**Park**** **
**University**** ****Mission**

The mission of

**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

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.

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.

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

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

**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.

**ADA**** Compliance**

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.

Grading weights are as follows:

Individual project (25%)

Participation (25%)

Midterm exam (25%)

Final exam (25%)

Letter grades are assigned (based on your overall score) as follows:

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.

**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:

Refer to http://jwilson.coe.uga.edu/Texts.Folder/GLaD/GLaD.Comments.html, and http://scientium.com/diagon_alley/archival/segments/euclid1.htm. 1) Prove the GLAD Construction problem mathematically using mathematical induction method. 2) Present any known applications of the GLAD Construction problem.

Option 2:

Design a sequential circuit. Specifications will be provided in class.