Instructor:
Dr. John R. Sullins
Office hours: MW
Office: 333 Meshel Hall
Phone: 941-1806
Email: john@cis.ysu.edu
Web site: http://cis.ysu.edu/~john/
Check the web site regularly, as assignments and announcements will be posted here.
Objectives:
1. Introduce the mathematical concepts that form the basis of computer science, including Boolean logic, sets and relations, proofs, number theory, permutations and combinations, and graph theory.
2. Demonstrate how these concepts are applied to areas of computer science, including program specification and validation, encryption, generating functions, databases, and networking.
Prerequisites:
MATH 1571: Calculus 1 and CSIS
2610: Programming and Problem Solving.
It is assumed that you have done some programming, as programming assignments
may be given in this course.
Textbook:
Discrete Math and its Applications, Fifth Edition, Kenneth H. Rosen, McGraw-Hill.
Grading:
|
Homework assignments |
30% |
(6-7 biweekly assignments) |
|
Exam 1 |
15% |
Wednesday, Feb. 18 |
|
Exam 2 |
15% |
Wednesday, March 17 |
|
Exam 3 |
15% |
Wednesday, April 7 |
|
Final Exam |
25% |
Monday, May 3, |
Last day to withdraw with a "W": Saturday, March 20
Homework Assignments:
The homework assignments will for the most part be written problems (including some proofs), usually from the textbook. However, I may also assign some programming projects in order to emphasize the applications of discrete mathematics.
As with any other course, work on these assignments must be your own. See the policy sheet for more details.
Tentative Course Outline:
|
WEEK |
TOPICS |
TEXTBOOK |
|
1/12 |
Introduction to logic |
1.1-1.2 |
|
1/19 |
Circuit design, Predicate Logic, |
10.3, 10.4, 1.3 |
|
1/26 |
Introduction to sets and functions |
1.6, 1.7, 1.8, |
|
2/2 |
Algorithm complexity |
2.1, 2.2, 2.3 |
|
2/9 |
Division and integers, the Euclidean algorithm |
2.4, 2.5 |
|
2/16 |
The Chinese Remainder Theorem, RSA Encryption (Exam 1 Wednesday) |
2.6 |
|
2/23 |
Proof techniques, Mathematical Induction and Recursion |
3.1, 3.2, 3.3 |
|
3/1 |
Program validation |
3.6 |
|
3/8 |
SPRING BREAK |
|
|
3/15 |
Counting Theory (Exam 2 Wednesday) |
4.1, 4.3 |
|
3/22 |
Permutations and Combinations, Discrete probability |
4.5, 4.6, 5.1 |
|
3/29 |
Set relations and properties |
7.1-7.4 |
|
4/5 |
Equivalence and Partial-order relations (Exam 3 Wednesday) |
7.5, 7.6 |
|
4/12 |
Graph concepts and representations, Isomorphism |
8.1-8.3 |
|
4/19 |
Graph connectivity, Planar graphs, Graph coloring |
8.4, 8.7, 8.8 |
|
4/26 |
Trees |
9.1, 9.2, 9.4 |