CIS 242 Course Outline

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

--- E. W. Dijkstra

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 HolePrinciple, 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.