| Instructor | James Muir, Herzberg Laboratories (HP) 5135, x1431 (phone extension), jamuir at scs dot carleton dot ca | |
| lectures | 7:05pm--9:55pm Monday & Wednesday in |
|
| office hours | 6:00pm--7:00pm Monday & Wednesday in HP 5135 (I am also available by appointment) | |
| TA | Abbas Shamsi, arsshams at connect dot carleton dot ca | |
| office hours | 6:00pm--8:00pm Tuesdays in HP 1175 |
Introduction to discrete mathematics and discrete structures. Topics include: propositional and predicate calculus, Boolean algebra, introduction to complexity of algorithms, mathematical reasoning, counting, recurrences, relations, introduction to graphs.
Two OACs in Mathematics or two Grade 12 university preparation Mathematics courses (after Summer 2002), and one of COMP 1405, COMP 1005, COMP 1007 or Engineering SYSC 1100 (which may be taken concurrently).
Obtaining permission to register. If Carleton's online registration system will not allow to you register for this course and you feel you have the necessary background, then please contact our Undergraduate Advisor, Joni Campbell, to obtain the necessary permissions.
The required text is Discrete Mathematics and its Applications, Sixth Edition by Kenneth H. Rosen.
The text is available from amazon.ca for $99.50 (19 April 2007).
Amazon.ca no longer has new copies of the text available for order (7 May 2007).
It is available from chapters.indigo.ca for $151.95 (19 April
2007).
It is available from the Carleton University Bookstore for
$144.50 (new) and $108.50 (used) (19 April 2007).
A copy of the text has been placed on 2 hour course reserve in the library.
Using previous editions of the text. I strongly recommend that you use the 6th edition. Although most of the material we will cover can be found in earlier editions of the text, chapter, section and exercise numbers will not necessarily match up; there is also new material in the 6th edition not found in earlier ones (including over 400 new exercises). Using an old edition will be particularly confusing when I assign problems from the text. Again, I strongly recommend that you use the 6th edition.
The sections of the text we will cover are listed below.
Your final mark will be computed using the following formula:
30% Assignments (a total of six) 20% Midterm (2-hours, evening of June 5) 50% Exam (3-hours, scheduled by the University)
Any bonus marks that you've earned during the course will be added to your exam score (e.g., if your raw exam score was 85/100 and you received a total of 6 bonus marks, then your adjusted exam score will be 91/100). Note that each bonus question is marked out of 2 (i.e., a solution to a bonus question receives a mark of either 0,1 or 2).
To compute your assignment mark, I will take the five assignments which maximize your mark according to the following formula:
Let A1, A2, A3, A4, A5, A6 be your assignment marks.
The total marks available on each of the six assignments respectively were 60, 68, 70, 74, 100, 28. The sum of these is 400.
Let A=A1+A2+A3+A4+A5+A6.
Your mark is computed as:
max{ (A-A1)/(400-60), (A-A2)/(400-68), (A-A3)/(400-70), (A-A4)/(400-74), (A-A5)/(400-100), (A-A6)/(400-28) }
Final Marks Here is a list of all class marks which does not include any identifying information.
There will be six assignments in total. Each assignment will be posted here when it is available.
Assignment 1 (due 23 May)
Bonus Question 1
Assignment 2 (due 28 May)
Bonus Question 2
Assignment 3 (due 4 June)
Assignment 4 (due 13 June)
Bonus Question 3
Assignment 5 (due 20 June)
Assignment 6 (due 25 June) Bonus Question 4
Assignment Policy. Assignments must be submitted at the beginning of the lecture on the due date. Late assignments will not be accepted. You are permitted to discuss assignment questions with your classmates, but solutions must be written up individually using your own words. If you copy a classmate's assignment or permit a classmate to copy your assignment, then this is a violation of Carleton's Academic Integrity Policy and will be reported to the faculty Dean. If you have received help with an assignment problem (e.g., from a classmate, TA, prof, book, web page, paper, etc.) you must acknowledge your sources in your write-up.
There will be a two-hour midterm the evening of June 5 (Tuesday).
Time & Place: Tuesday, June 5, 7pm--9pm, 518 Southam Hall
Here are some notes about the midterm.
Here are solutions to the midterm.
Here is a list of the scores on the midterm which does not include any identifying information.
The exam schedule for the Summer term can be found here. The information for our final exam is as follows:
Time & Place: Saturday, June 30, 9am--12pm, Southam Hall
Here are some notes about the final examination.
Here is a list of the scores on the exam which does not include any identifying information.
Note: our schedule for the summer term is compressed. Normally, the format of this course is 3 hours of lecture per week. This semester, we will have 6 hours of lecture per week.
Content. The following list is an approximate outline of the text sections we will cover, subject to time constraints. This list is also available as a text file.
1.1 Propositional Logic 1.2 Propositional Equivalences 11.1 Boolean Functions 11.2 Representing Boolean Functions 1.3 Predicates and Quantifiers 1.4 Nested Quantifiers 1.5 Rules of Inference 1.6 Introduction to Proofs 1.7 Proof Methods and Strategy 2.1 Sets 2.2 Set Operations 2.3 Functions 2.4 Sequences and Summations 3.1 Algorithms 3.2 The Growth of Functions 3.3 Complexity of Algorithms 3.4 The Integers and Division 3.5 Primes and Greatest Common Divisors 3.6* Integers and Algorithms 3.8 Matrices 4.1 Mathematical Induction 4.2 Strong Induction and Well-Ordering 4.3 Recursive Definitions and Structural Induction 5.1 The Basics of Counting 5.2 The Pigeonhole Principle 5.3 Permutations and Combinations 5.4 Binomial Coefficients 5.5 Generalized Permutations and Combinations 7.1 Recurrence Relations 7.2 Solving Linear Recurrence Relations 7.3 Divide-and-Conquer Algorithms and Recurrence Relations 7.5* Inclusion-Exclusion 7.6* Applications of Inclusion-Exclusion 8.1 Relations and Their Properties 8.2 n-ary Relations and Their Applications 8.3 Representing Relations 8.5 Equivalence Relations 8.6 Partial Orderings 9.1 Graphs and Graph Models 9.2 Graph Terminology and Special Types of Graphs 9.3 Representing Graphs and Graph Isomorphism 9.4 Connectivity 9.5 Euler and Hamilton Paths 9.8* Graph Coloring 10.1 Introduction to Trees *time permitting