MATHEMATICS 223

LOGIC AND MATHEMATICAL REASONING

Summer 2001

Instructor:

 Steven E. Rigdon, Ph.D. 1325 or 1330 Science Building Phone: 618-650-2193 e-mail: srigdon@siue.edu web: www.siue.edu/~srigdon.html Office Hours: Monday Wednesday Friday: 1:00-2:00

Prerequisite: CS 140 or 141.

Textbook: Discrete Mathematics & Its Applications, by K. H. Rosen, Published by WCB McGraw-Hill

 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 e-mail at least one hour before class. I may give you a hint by e-mail, 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 1-7, 11, 13, 15 Í 1.3 1, 3, 5, 6, 9, 11, 19, 21, 22, 25, 31, 35, 45 Í 1.4 1, 3, 5-9, 11, 12, 15, 17, 22, 23, 24 Í 1.5 1-6, 9, 10, 13, 17, 18 Í 1.6 1-4, 7-11, 13, 15, 17, 19, 22 Í 1.7 1, 3, 5, 7, 13, 15, 17, 19, 20, 23, 27-30 Í 1.8 1-7, 9, 12, 15, 19, 21 Í 2.1 1-10 Í 2.2 1-4, 7-10 Í 2.3 1-4, 8-12, 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 1-5, 7, 10, 12, 13, 19, 20, 21, 28, 31, 41, 43, 47 Í 3.3 1-11, 15, 26, 27 Í 3.4 1-5, 10, 11, 23 Í 3.5 1-4 Í 4.1 1-14, 19, 21, 25, 27, 31, 33, 37 Í 4.2 2-5, 8-10, 23 Í 4.3 1-5, 7, 9, 11, 15, 17, 22, 25, 27, 31, 35-42, Í 4.4 1-17, 21-25, 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, 13-16 Í 7.1 1-10, 16 Í 7.2 1-19, 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 1-6, 15-18 Í 7.5 1, 2, 3, 5, 8, 9, 10, 16, 19, 21 Í 8.1 1-5, 11, 13, 15 Í 8.2 1-7, 11 Í 8.3 1-21