MATHEMATICS 223
LOGIC AND MATHEMATICAL REASONING
Spring 2001
Instructor:
|
Steven E. Rigdon, Ph.D. 1325 Science Building Phone: 618-650-2193 e-mail: srigdon@siue.edu web: www.siue.edu/~srigdon.html |
Office Hours: Tuesday: 3:20-5:00 Thursday: 1:00-2:00 and 5:00-6: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 McGraw-Hill
Grading:
|
Points |
|
|
Exams (Best 3 of 4 @ 50 points each) |
150 |
|
Projects (3-5 @ 10 points each) |
30-50 |
|
Final Exam |
100-120 |
|
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 24-26 |
Í 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:
(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-5 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 e-mail with a copy to the whole class. I may respond (to the whole class) with a hint in an e-mail, 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 |
1-7, 13, 15 |
9 |
|
Í 1.3 |
1, 3, 5, 6, 9, 11, 19, 21, 25, 31, 35, 45 |
12 |
|
Í 1.4 |
1, 3, 5-9, 11, 12, 15, 17, 22, 23, 24 |
14 |
|
Í 1.5 |
1-6, 9, 10, 13, 17, 18, 22, 24, 25, 35 |
15 |
|
Í 1.6 |
1-4, 7-11, 13, 15, 17, 19, 22, 28, 29, 31 |
17 |
|
Í 1.7 |
1, 3, 5, 7, 13, 15, 17, 19, 20, 23, 27-31 |
15 |
|
Í 1.8 |
1-7, 9, 12, 15, 19, 21 |
12 |
|
Í 2.1 |
1-10 |
10 |
|
Í 2.2 |
1-4, 7-10 |
8 |
|
Í 2.3 |
1-4, 8-12, 14, 15, 17, 24, 29 |
14 |
|
Í 2.4 |
1, 3, 5, 7, 9, 11 |
6 |
|
Í 2.5 |
1, 3, 4, 5, 11, 12, 18, 21-24, 36, 37 |
13 |
|
Í 3.1 |
1, 2, 3, 7, 11, 13, 15, 17, 19, 21, 23, 25, 64, 65 |
14 |
|
Í 3.2 |
1-5, 7, 10, 12, 13, 19, 20, 21, 28, 41, 43, 47 |
16 |
|
Í 3.3 |
1-11, 15, 20, 21, 22, 26, 27, 54 |
18 |
|
Í 3.4 |
1-5, 8, 10, 11, 23 |
9 |
|
Í 3.5 |
1-4 |
4 |
|
Í 4.1 |
1-14, 19, 21, 25, 27, 31, 33, 37, 49-52 |
25 |
|
Í 4.2 |
2-5, 8-10, 16, 23-26, 29 |
13 |
|
Í 4.3 |
1-5, 7, 9, 11, 15, 17, 22, 25, 27, 31, 35-42, 48, 53 |
24 |
|
Í 4.4 |
1-17, 21-25, 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 |
1-5, 7, 14-16 |
9 |
|
Í 7.1 |
1-10, 16 |
11 |
|
Í 7.2 |
1-19, 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 |
1-6, 11, 15-18 |
11 |
|
Í 7.5 |
1, 2, 3, 5, 8, 9, 10, 16, 19, 21, 24-26, 29-31, 40-43, 47-50 |
24 |
|
Í 7.6 |
1-5, 7, 9, 11 |
8 |
|
Í 7.7 |
1-7, 9 |
8 |
|
Í 7.8 |
1-7, 11, 12, 15 |
10 |
|
Í 8.1 |
1-5, 11, 13, 15 |
8 |
|
Í 8.2 |
1-7, 11 |
8 |
|
Í 8.3 |
1-21 |
21 |
|
Í 8.4 |
1, 5, 7, 12-14 |
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 |