MATHEMATICS 223
LOGIC AND MATHEMATICAL REASONING
Summer 2001
Instructor:
Steven E. Rigdon, Ph.D. 1325 or 1330 Science Building Phone: 6186502193 email: srigdon@siue.edu web: www.siue.edu/~srigdon.html 
Office Hours: Monday Wednesday Friday: 1:002:00

Prerequisite: CS 140 or 141.
Textbook: Discrete Mathematics & Its Applications, by K. H. Rosen, Published by WCB McGrawHill
Grading:
Points 
Total Points 
Grade 

Exams (Best 2 of 3 @ 50 points each) 
100 
225  250 
A 

Projects (3 @ 10 points each) 
30 
200  224 
B 

Final Exam 
100 
175  199 
C 

Homework (see below) 
20 
150  174 
D 

TOTAL 
0  149 
E 

Course Outline:
Week 
Dates 
Monday 
Wednesday 
Friday 
1 
May 21, 23, 25 
Í 1.1 Logic Í 1.2 Propositional Equivalences 
Í 1.3 Predicates and Quantifiers 
Í 1.4 Sets Í 1.5 Set Operations 
2 
May 28, 30 June 1 
Í 1.6 Functions

Í 1.7 Sequences and Summations Í 1.8 The Growth of Functions 
Í 2.1 Algorithms 
3 
June 4, 6, 8 
Í 2.2 Complexity of Algorithms 
Í 2.3 The Integers and Division 
EXAM #1

4 
June 11, 13, 15 
Í 2.4 Integers and Algorithms 
Í 2.5 Applications of Number Theory

Í 3.1 Methods of Proof

5 
June 18, 20, 22 
Í 3.2 Mathematical Induction 
Í 3.2 Mathematical Induction Í 3.3 Recursive Definitions

Í 3.4 Recursive Algorithms Í 3.5 Program Correctness 
6 
June 25, 27, 29 
Í 4.1 Counting 
Í 4.2 The Pigeonhole Principle 
EXAM #2 
7 
July 2, 4, 6 
Í 4.3 Permutations and Combinations 
NO CLASS INDEPENDENCE DAY 
Í 4.4 Discrete Probability Í 5.1 Recurrence Relations 
8 
July 9, 11, 13 
Í 5.1 Recurrence Relations Í 5.2 Solving Rec. Relations 
Í 5.2 Solving Recurrence Relations

Í 5.3 Divide and Conquer Í 7.1 Introduction to Graphs 
9 
July 16, 18, 20 
Í 7.2 Graph Terminology 
Í 7.3 Graph Isomorphisms Í 7.4 Connectivity 
Í 7.5 Euler Paths

10 
July 23, 25, 27 
EXAM #3 
Í 8.1 Introduction to Trees Í 8.2 Applications of Trees 
Í 8.2 Applications of Trees Í 8.3 Tree Traversal 
11 
Final Exam Week 
Final Exam: 11:00 am  12:40 pm Tuesday, July 31, 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 3 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: Work the homework problems in a wireless notebook, preferably 8.5" x 11", that is devoted exclusively to MATH 223 homework (i.e., excluding lecture notes). The notebooks will be collected on test days (including the final exam) and I will grade the homework while you are taking the test. Grades will be assigned as follows
5. 
All (or nearly all) homework done correctly, thoroughly, and neatly. This includes clear, concise explanations in English sentences when explanations are asked for. 
4. 
Most homework done correctly. Clear explanations. 
3. 
More than half of the homework done. 
2. 
About half of the homework done. 
1. 
Less than half, but more than one fourth, of the homework done. 
0. 
Less than one fourth of the homework done. 
If you would like help on homework problems, contact me by email at least one hour before class. I may give you a hint by email, or I may give the whole class a hint during class time.
Section 
Assigned Problems 
Í 1.1 
1, 3, 4, 5, 9, 11, 19, 21, 23, 25, 28 
Í 1.2 
17, 11, 13, 15 
Í 1.3 
1, 3, 5, 6, 9, 11, 19, 21, 22, 25, 31, 35, 45 
Í 1.4 
1, 3, 59, 11, 12, 15, 17, 22, 23, 24 
Í 1.5 
16, 9, 10, 13, 17, 18 
Í 1.6 
14, 711, 13, 15, 17, 19, 22 
Í 1.7 
1, 3, 5, 7, 13, 15, 17, 19, 20, 23, 2730 
Í 1.8 
17, 9, 12, 15, 19, 21 
Í 2.1 
110 
Í 2.2 
14, 710 
Í 2.3 
14, 812, 14, 15, 17, 24, 29, 42, 43, 45 
Í 2.4 
1, 3, 5, 7, 9, 11, 35, 36 
Í 2.5 
1, 3, 4, 5, 11, 12, 18, 21, 22, 26, 27, 28, 36, 37 
Í 3.1 
17, 19, 21, 23, 25, 64, 65 
Í 3.2 
15, 7, 10, 12, 13, 19, 20, 21, 28, 31, 41, 43, 47 
Í 3.3 
111, 15, 26, 27 
Í 3.4 
15, 10, 11, 23 
Í 3.5 
14 
Í 4.1 
114, 19, 21, 25, 27, 31, 33, 37 
Í 4.2 
25, 810, 23 
Í 4.3 
15, 7, 9, 11, 15, 17, 22, 25, 27, 31, 3542, 
Í 4.4 
117, 2125, 28 
Í 5.1 
1, 3, 5, 6, 8, 11, 13, 17, 19, 21, 29, 31 
Í 5.2 
1, 3, 5, 7, 8, 9, 11, 13, 15 
Í 5.3 
1, 2, 7, 8, 10, 11, 1316 
Í 7.1 
110, 16 
Í 7.2 
119, 21, 23, 25 
Í 7.3 
1, 3, 5, 7, 9, 11, 12, 13, 15, 17, 19, 21, 23, 25, 35, 37, 39, 41, 43 
Í 7.4 
16, 1518 
Í 7.5 
1, 2, 3, 5, 8, 9, 10, 16, 19, 21 
Í 8.1 
15, 11, 13, 15 
Í 8.2 
17, 11 
Í 8.3 
121 