Related Links
Instructor:
Top
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Text
Discrete and Combinatorial Mathematics, Ralph P. Grimaldi, Addison Wesley,
Fourth Edition. This is available in the Dalhousie bookstore.
Top
Outline of course:
- Fundamentals of Logic - Truth tables, logical equivalence, quantifiers,
laws of logic. Sections 2.1, 2.2
- Elementary Proof Techniques - rules of inference, contradiction, contrapositive.
Sections 2.3, 2.4
- Set Theory - Notation, Venn diagrams, elementary proofs with sets, Cartesian
product, introduction to relations. Sections 3.1, 3.2, 5.1
- Elementary Mathematical Concepts - sum notation, elementary probability,
mod function, division and primes, bit strings. Sections 1.3 (in part), 3.4, 4.4, 4.3, 6.1
- Mathematical Induction and Recurrence - recurrent definitions (e.g. fibonacci
numbers), recursive algorithms, recurrence relations, induction proofs. Sections 4.1, 4.2, part of 10.1
- Introduction to the Analysis of Algorithms - use of induction to prove
running time results, big Oh notation. Sections 5.7, 5.8
- Graphs and Trees - basic definitions, inductive proofs using graphs and trees,
algorithms based on graphs and trees and their analysis. Chapters 11, 12
Top
Assessment
The course mark will be based on assignments, quizzes, two midterm
tests, and a three hour final. Every other week, a number of homework
questions are assigned, which must be handed in the next week on the
day indicated (usually Wednesday for Section 1 and Thursday for
Section 2) before the beginning of class . On alternate
weeks, a list of short questions is handed out. These should be
completed and studied, as a number of these or very similar questions
will appear on a short in-class quiz which will be held the week after.
The midterm tests are two 90 minutes tests, held in the evening of
October 17 and November 14. The final is scheduled for the exam period
by the registrar, and lasts three hours.
The final mark is calculated as follows:
| Assignments |
20% |
| Quizzes (4) |
20% |
| Tests (2) |
30% |
| Final exam |
30% |
At Dalhousie, the final grade is a letter grade, whereas throughout
the term you will be getting numerical grades. We will use the translation
A>79%, B>63%, C>50%; D>45%. We reserve the right to alter these slightly
for unforeseen circumstances.
Top
Links to some Discrete Mathematics sites
If you find any good pages let us know and we will add them to the list.
