MATHEMATICS 223
LOGIC AND MATHEMATICAL REASONING
Spring 2001
Instructor:
Steven E. Rigdon, Ph.D. 1325 Science Building Phone: 6186502193 email: srigdon@siue.edu web: www.siue.edu/~srigdon.html 
Office Hours: Tuesday: 3:205:00 Thursday: 1:002:00 and 5:006:00 
Prerequisite: CS 140 or 141. Just because there are no mathematics prerequisites doesn't mean that this is an easy course. On the contrary, it is a difficult course, but it does not use any ideas from other mathematics courses like calculus.
Textbook: Discrete Mathematics and Its Applications, by K. H. Rosen, Published by WCB McGrawHill
Grading:
Points 

Exams (Best 3 of 4 @ 50 points each) 
150 
Projects (35 @ 10 points each) 
3050 
Final Exam 
100120 
TOTAL 
300 
All midterm exams (i.e., all exams except the final exam) will be given at 2:30 on the assigned days. During the first 30 minutes of class we will cover new material that will not be on the exam.
Course Outline:
Week 
Dates 
Tuesday 
Thursday 
1 
January 9 & 11 
Í 1.1 Logic Í 1.2 Propositional Equivalences 
Í 1.3 Predicates and Quantifiers 
2 
January 16 & 18 
Í 1.4 Sets Í 1.5 Set Operations 
Í 1.6 Functions

3 
January 23 & 25 
Í 1.7 Sequences and Summations Í 1.8 The Growth of Functions 
Í 2.1 Algorithms EXAM #1 
4 
Jan 30 & Feb 1 
Í 2.1 Algorithms

Í 2.2 Complexity of Algorithms 
5 
February 6 & 8 
Í 2.3 The Integers and Division

Í 2.4 Integers and Algorithms 
6 
February 13 & 15 
Í 2.5 Applications of Number Theory

Í 3.1 Methods of Proof EXAM #2 
7 
February 20 & 22 
Í 3.2 Mathematical Induction 
Í 3.2 Mathematical Induction Í 3.3 Recursive Definitions 
8 
Feb 27 & Mar 1 
Í 3.4 Recursive Algorithms

Í 3.5 Program Correctness Í 4.1 Counting 
9 
March 6 & 8 
Í 4.2 The Pigeonhole Principle Í 4.3 Permutations and Combinations 
Í 4.4 Discrete Probability EXAM #3 
Spring Break ! ! 

10 
March 20 & 22 
Í 5.1 Recurrence Relations

Í 5.2 Solving Recurrence Relations 
11 
March 27 & 29 
Í 5.3 Divide and Conquer 
Í 7.1 Introduction to Graphs Í 7.2 Graph Terminology 
12 
April 3 & 5 
Í 7.3 Graph Isomorphisms Í 7.4 Connectivity 
Í 7.5 Euler and Hamilton Paths EXAM #4 
13 
April 10 & 12 
Í 7.6 Shortest Path Problems

Í 7.7 Planar Graphs Í 8.1 Introduction to Trees 
14 
April 17 & 19 
Í 8.2 Applications of Trees 
Í 8.3 Tree Traversal Í 8.4 Trees and Sorting 
15 
April 2426 
Í 8.5 Spanning Trees 
Í 8.6 Minimal Spanning Trees

16 
Final Exam: 12:00  1:40 pm on Monday, April 29, 2001

To Do Well: Here are some suggestions for doing well in this class:
(1) Come to class regularly
(2) Come to class PREPARED (read the sections before they are covered in class, do the first four assigned problems in each PROBLEM SET)
(3) Do all of the assigned homework.
(4) Write clear and concise solutions to the homework, so that when you are studying for an exam, you will be able to understand what you have done.
If you have difficulty, see the instructor, the tutors in the Tutor Lab (SL1224), or another student in the class. The Tutor Lab hours will be posted early in the term. No appointment is necessary, and the service is provided free of charge. The Student Solution Manual will be available in the Bookstore.
This is a difficult course. It takes time and effort to do well.
Important Notes: *** No make up exams ***
A grade of I (incomplete) can be given only under the following circumstances:
(1) the student is prevented by a medical or similar emergency from completing a small portion of the course requirements
(2) the student presents valid documentation of the emergency
(3) the student is passing the course at the time of the emergency.
A grade of I cannot be given as an alternative to an E or UW.
Computing Assignments: There will be 35 programming assignments. You may work together to develop an algorithm, but you must implement the algorithm and the code by yourself. Copying someone else’s program is plagiarism and will be penalized severely. It is easy to detect a copied program.
Homework Assignments: Although homework will not be collected for grading, you must do it anyway. You cannot pass the course without doing the homework. I will generally not work homework problems in class, unless I feel that there is widespread misunderstanding of a concept or a particular problem. If you have trouble with the homework, please see me or send me an email with a copy to the whole class. I may respond (to the whole class) with a hint in an email, or I may give a hint in class. Work the homework problems in a notebook, preferably an 8.5" x 11" wireless notebook, that is devoted exclusively to MATH 223 homework. I will collect notebooks periodically to assess whether you are keeping up with the homework. Bring your notebook to every class, because I will collect notebooks at random.
Section 
Assigned Problems 
# Problems 
Í 1.1 
1, 3, 4, 5, 9, 11, 13, 19, 21, 23, 25, 28, 39 
13 
Í 1.2 
17, 13, 15 
9 
Í 1.3 
1, 3, 5, 6, 9, 11, 19, 21, 25, 31, 35, 45 
12 
Í 1.4 
1, 3, 59, 11, 12, 15, 17, 22, 23, 24 
14 
Í 1.5 
16, 9, 10, 13, 17, 18, 22, 24, 25, 35 
15 
Í 1.6 
14, 711, 13, 15, 17, 19, 22, 28, 29, 31 
17 
Í 1.7 
1, 3, 5, 7, 13, 15, 17, 19, 20, 23, 2731 
15 
Í 1.8 
17, 9, 12, 15, 19, 21 
12 
Í 2.1 
110 
10 
Í 2.2 
14, 710 
8 
Í 2.3 
14, 812, 14, 15, 17, 24, 29 
14 
Í 2.4 
1, 3, 5, 7, 9, 11 
6 
Í 2.5 
1, 3, 4, 5, 11, 12, 18, 2124, 36, 37 
13 
Í 3.1 
1, 2, 3, 7, 11, 13, 15, 17, 19, 21, 23, 25, 64, 65 
14 
Í 3.2 
15, 7, 10, 12, 13, 19, 20, 21, 28, 41, 43, 47 
16 
Í 3.3 
111, 15, 20, 21, 22, 26, 27, 54 
18 
Í 3.4 
15, 8, 10, 11, 23 
9 
Í 3.5 
14 
4 
Í 4.1 
114, 19, 21, 25, 27, 31, 33, 37, 4952 
25 
Í 4.2 
25, 810, 16, 2326, 29 
13 
Í 4.3 
15, 7, 9, 11, 15, 17, 22, 25, 27, 31, 3542, 48, 53 
24 
Í 4.4 
117, 2125, 28 
22 
Í 5.1 
1, 3, 5, 6, 8, 11, 13, 17, 19, 21, 29, 31 
12 
Í 5.2 
1, 3, 5, 7, 8, 9, 11, 13, 15, 23, 25, 29 
12 
Í 5.3 
15, 7, 1416 
9 
Í 7.1 
110, 16 
11 
Í 7.2 
119, 21, 23, 25 
22 
Í 7.3 
1, 3, 5, 7, 9, 11, 12, 13, 15, 17, 19, 21, 23, 25, 35, 37, 39, 41, 43 
19 
Í 7.4 
16, 11, 1518 
11 
Í 7.5 
1, 2, 3, 5, 8, 9, 10, 16, 19, 21, 2426, 2931, 4043, 4750 
24 
Í 7.6 
15, 7, 9, 11 
8 
Í 7.7 
17, 9 
8 
Í 7.8 
17, 11, 12, 15 
10 
Í 8.1 
15, 11, 13, 15 
8 
Í 8.2 
17, 11 
8 
Í 8.3 
121 
21 
Í 8.4 
1, 5, 7, 1214 
6 
Í 8.5 
1, 3, 5, 7, 9, 13, 17 
7 
Í 8.6 
1, 2, 3, 5, 6, 7 
6 
TOTAL NUMBER OF PROBLEMS  > 
5 