# CIS 242 Course Outline

*" In Computer Science, Elegance Is Not A Dispensable Luxury, But A Matter Of Life And Death "*

### Semester : Fall 2006

**Time: Lecture: ***Mondays, 10:40 – 12:30am, Wednesdays: 11:40 – 12:30am *

**Place: 403B ***Tuttleman*

**Text: ***Kolman, Busby, Ross: ***Discrete Mathematical Structures***. *

* Prentice Hall (5th edition)*

**Pre-requisites: ***CIS66, 68, 72, 166 and Math 75/85*

**References: Discrete Mathematics and its Application, ***Kenneth Rosen*

** Discrete Mathematics with Applications, ***Susanna S. Epp*

**Instructor :*** Dr. Arthur T. Poe*

**Office : *** 1008 Wachman Hall*

**Office Phone*** : 204-6481*

**Fax:: ***204-5082*

**Email address***: poe@temple.edu*

**Office hour***: To be announced*

* *

* *

* And/Or : by appointment, by phone, by email*

**Grading: ***Homework : 15-20 %*

* Midterm(s) 25 –35%*

* Final: 45 – 60%*

* *

*Since there are many preliminary topics that were treated in the prerequisites, I will review and revisit these topics first. My lectures may or may not follow the order or the presentation in the text. It is most important that you take good class notes. Please pay attention to the differences between my presentation and text’s. I will make my lectures self-contained and will presume that you had math maturity but little prior knowledge. From time to time, I supplement my lectures by handing out class notes. Obviously, it is important that you read these handouts. Needless to say, good attendance will enable you to receive therefore understand these handouts, and I do check attendance. *

Our course material development is formal but with an intuitive appeal. Most proofs are constructive in nature.

* *

*I believe in active learning, namely learning is a two-way street. Therefore, I encourage the class to ask questions. My answers, most of the time, will be another question --- a leading question. I expect you to read the course material we cover in class either before we meet in class or after class, PREFERABLY BOTH.*

* *

*I collect homework every week. You are encouraged to DISCUSS with your classmates about course materials, homework etc, or get help from me. Copying somebody else's work is prohibited.
I do not give make-up exam. If you have legitimate excuse, AND you obtained my prior approval, your course grade then will depend on homework and final.*

* *

*The Dean’s office asks us also to provide with the following information::*

* *

*First day of class: Monday, August 28th, 2006*

*No Class : Labor Day, Monday, September 4th.*

*Last day to drop: Monday, September 11th.*

*Last day to withdraw: Monday, October 30th.*

*Thanksgiving Recess: Thursday November 23 – Sunday November 26 *

*Last day of Class: Wednesday, December 6th, 2004*

*Final Exam: See University Schedule *

* (Wednesday, December 13th, 8:30 – 10:30)*

** **

## Outline

** **

** **

**Preliminaries and Fundamentals: **

** **

*Logic, Implication, Rules of Inference, An Argument being Valid, *

*Sets, Subsets and Power Set, Principle of Mathematical Induction, *

* Program Correctness,Properties of Integers, Counting, Pigeon Hole**Principle, Functions, Injections, Surjections, Invertible Functions, *

* Cardinality, Denumerable(countable) and non-denumerable (non-**countable) sets, Recursive Definitions, Recursive Relations, **Algorithm, Complexity, Big O Notation and Classes **Binomial Theorem, Matrices and their Evaluations **Relations and their Closures, Equivalence Relations and Partitions **Shortest path problems, Dijkstra’s Algorithm, H-sum*

**Planarity: **

Examples of planar and non-planar graphs, Euler’s Formula,

* Homeomorphic Graphs, Kuratowski ‘s Theorem,*

* *

**Permutations***:*

* Operations on Permutation, Order, Cycles, Cyclic Decomposition, **Transposition, Parity of Permutation*

* *

**Algebraic Systems***:*

*Binary Operator, Identity and Inverse, Semi-group, Monoid, Partial *

* Order, Poset, Hasse Diagram, Maximal and Minimal elements, *

* Topological Sort, Group, Congruence Relation*

* *

**Languages, Machines and Finite Automata***:*

* Strings, Languages, Chomsky’s Classification of Formal Languages, *

* Finite State Machines as transducers (i.e. with output), as Recognizes *

* (automata i.e. without output), the Semigroup of an Automaton*

* *

**Semigroups an Groups***:*

* Properties of Semigroup and Group, Group of Small Order, Subgroup, Normal** Subgroup, Congruence Relation, Homomorphism and Isomorphism, Product **and Quotient of Semi-Groups, and of Groups, Homomorphism Theorems for **Semigroups and Groups, Cosets, Quotient group, Symmetric Group S n and **Alternating Group A n .*

* *

**Groups and Error Correcting Codes***:*

* Hamming distance, Encoding function, Minimum Distance of an Encoding *

* Functions, Group Code, Parity Check Matrix, Decoding function, Maximum *

*Likelihood Decoding Function, Decoding Table, Syndrome of Coset Leader*

* *

Any student who has a need for accommodation based on the impact of a disability should contact me privately to discuss the specific situation as soon as possible. Contact Disability Resources and Services at (215) 204-1280, 100 Ritter Annex, to coordinate reasonable accommodations for students with documented disabilities.

Freedom to teach and freedom to learn are inseparable facets of academic freedom. The University has adopted a policy on Student and Faculty Academic Rights and Responsibilities (Policy # 03.70.02) which can be accessed here.

*Students will be charged for a course unless a withdrawal form is processed by a registration office of the University by the Drop/Add deadline date. The Drop/Add deadline date is published in the Class Schedule each semester. A student may not withdraw from the same course more than once. Students who miss the final exam and do not make alternative arrangements before the grades are turned in will be graded F.*

* *