CS-23022
DISCRETE STRUCTURES FOR CS
Spring 2007

Monday, Wednesday  12:30 pm -01:45 pm.
MSB 121

Instructor Office Hours Email Telephone

Dr. Feodor Dragan  Room 254 MSB Mon, Wed 2:00 - 3:00 PM and by appointment  dragan at cs dot kent dot edu (330) 672-9058

Teaching Assistant Office Hours Email Telephone

Manas Hardas Room MSB 255 TR 3.00-4.00pm and by appointment mhardas@cs.kent.edu (330)672-7825

• WWW http://www.cs.kent.edu/~dragan/CS23022-DiSt.html
• Course Description:  Discrete Structures for Computer Scientists with a focus on: mathematical reasoning, combinatorial analysis, discrete structures, algorithmic thinking, application and modeling. Specific topics include: logic, sets, functions, relations, algorithms, proof techniques, counting, graphs, trees, Boolean algebra, grammars and languages.
• Prerequisites: CS 10051; a grade of C (2.0) or better in MATH 12001, or in MATH 11022 and one of 11010 or 11011, or appropriate placement  test score into MATH 12002.
• Text:  Kenneth H. Rosen,  Discrete Mathematics and Its Applications, McGraw-Hill, 2003. (Web Site)
• Topics will include (in various depth):

- Logic, Sets, and Functions:
Logic, Propositional Equivalences, Predicates and Quantifiers, Nested Quantifiers, Methods of proof,  Sets, Set Operations, Functions. 
- Algorithms, the Integers, and Matrices:
Algorithms, The Growth of Functions, Complexity of Algorithms, The Integers and Division, Integers and Algorithms, Applications of Number Theory, Matrices.  
- Mathematical Reasoning, Induction, and Recursion:
Art and Strategy of Proof, Sequences and Sums, Mathematical Induction, Recursive Definitions and Structural Definition, Recursive Algorithms, Program Correctness.
- Counting:
The Basics of Counting, The Pigeonhole Principle, Permutations and Combinations, Binomial Coefficients, Generalized Permutations and Combinations, Generating Permutations and Combinations. 
- Discrete Probability:
An Introduction to Discrete Probability, Probability Theory, Expected Value and Variance
- Advanced Counting Techniques:
Recurrence Relations, Solving Recurrence Relations, Divide-and-Conquer Relations, Generating Functions, Inclusion-Exclusion, Applications of Inclusion-Exclusion.
- Relations:
Relations and Their Properties, n-ary Relations and Their Applications, Representing Relations, Closures of Relations, Equivalence Relations, Partial Orderings.
- Graphs:
Introduction to Graphs, Graph Terminology, Representing Graphs and Graph Isomorphism, Connectivity, Euler and Hamilton Paths, Shortest Path Problems, Planar Graphs, Graph Coloring.
- Trees:
Introduction to Trees, Applications of Trees, Tree Traversal, Spanning Trees, Minimum Spanning Trees.
- Boolean Algebra:
Boolean Functions, Representing Boolean Functions, Logic Gates, Minimization of Circuits.
- Modeling Computation:
Languages and Grammars, Finite-State Machines with Output, Finite-State Machines with No Output, Language Recognition, Turing Machines.

• Course Requirements

Attendance	-	-	-	5%
Homework	-	-	-	20%
Midterm Exam1	TBA	February ??, 2007	12:30 - 01:45 pm	25%
Midterm Exam2	TBA	April ??, 2007	12:30 - 01:45 pm	25%
Final Exam	Monday	May 7, 2007	10:15 - 12:30 p.m.	25%

• Milestone for successful completion of the course
• Attend the classes regularly,
• Perform the homework thoroughly and independently,
• Read the book carefully and several times. 
• Plagiarism statement:  Copying the solution from another student or jointly writing up the solution of a problem constitutes plagiarism. You are not permitted to use solutions to assigned problems from earlier terms.  Such activities and other unapproved or anti-intellectual behavior violates the University's plagiarism rules and can result in severe penalties. Behavior of this type is unfair to both yourself (in missed learning opportunities) and to the other students. University rules on plagiarism are given in the KSU Telephone Directory. You can print those rules here , too.
• Students with Disabilities: University policy 3342-3-18 requires that students with disabilities be provided reasonable accommodations to ensure their equal access to course content. If you have a documented disability and require accommodations, please contact the instructor at the beginning of the semester to make arrangements for necessary classroom adjustments. Please note, you must first verify your eligibility for these through Student Disability Services (contact 330-672-3391 or visit www.kent.edu/sds for more information on registration procedures).

---

F. F. Dragan
Spring 2007