Last updated:
Wednesday, 06-Jan-2010 08:26:02 EST
This outline may be updated
during the term so please check regularly
We will be covering some subjects in more depth than the textbook, and
some subjects not covered at all in the text. Please be sure to check the Handouts page for additional material.
Supplementary notes may or may note be referenced on this page.
The topics will not necessarily be covered in the exact order below.
Times given are rough guides only. Some topics will be covered as they come up in other sections.
Some topics will only be covered if time permits.
All Chapter references are from
Discrete Mathematics by Epp.
Please note that the current printing of this book contains mistakes.
Please check the errata in doubt.
Weeks 1-3:
- Sequences and Mathematical Induction - Chapter 4
- Recursion - Chapter 8
Topics
- Sequences and their various representations.
- Recursively defined sequences and examples.
- Solving recurrence relation by iteration.
- Series, products and changes of variables.
- Arithmetic and Geometric sequences.
- Proving conjectured solutions using mathematical induction.
- Using weak induction to solve other problems.
- Strong mathematical induction
- Structural induction
Textbook Sections
- 4.1 (except for programming section), 4.2, 4.3, some of 4.4
- 8.1, 8.2, 8.4
Handouts
Recommended Exercises
- 4.1: 1, 3, 10, 11, 12, 14, 20, 27, 29, 32, 35, 36, 40, 42, 45 ,46, 48, 49,
53, 54, 55, 58,
- 4.2: 3, 6, 8, 10, 13, 19, 21, 23, 24, 27, 32
- 4.3: 3, 4, 6, 8, 11, 13, 14, 16, 19, 24, 30, 31
- 4.4: 1, 4, 7, 10, 15
- 8.1: 1, 3, 5, 7, 9, 11, 13, 18, 20, 26, 27, 34, 39, 51
- 8.2: 1, 2, 3, 5, 6, 9, 10, 12, 14, 18, 19, 24, 26, 28, 30, 43, 46, 48, 50
- 8.4: 19, 20, 22, 23
Weeks 4-6:
Graphs and Trees - Chapter 11
Topics
- Graphs definitions.
- Paths and circuits
- Trees
- Isomorphism of graphs and trees
Textbook Sections
-
11.1, 11.2, 11.4, 11.5, 11.6
Recommended Exercises
- 11.1: 1, 3, 5, 8, 12, 13, 14, 15, 16, 19, 22, 24a, 28, 33, 35, 37, 39, 41, 42.
- 11.2: 1, 3, 4, 6, 8, 9, 10, 11, 12, 14, 18, 19, 22, 23, 26, 28, 29, 30, 42, 43, 49
- 11.4: 1, 2, 6, 8, 10, 12, 14, 16, 18, 19, 23
- 11.5: 1, 2, 3, 5, 8, 9, 10, 11, 12, 13, 14, 22, 25, 27, 28, 32
- 11.6: 1, 3, 5, 7, 13, 15, 19, 23
Weeks 7-8:
Computation
Strings and Finite State Automata
Topics
- Strings and formal languages.
- Regular expressions and regular languages.
- Pumping Lemma
- Finite State Automata.
- Turing Machines
- The Halting Problem and Computability
Textbook Sections
Recommended Exercises
- 12.1: 1, 3, 4, 7, 10, 13, 16, 19, 22, 25, 28, 29, 31, 33, 34, 37, 39
- 12.2: 2, 5, 7, 8, 10, 12, 15, 17, 20, 21, 23, 25, 26, 28, 29, 36, 39, 42
- 5.4: 1, 3, 5, 7, 9, 11, 13, 14
- 7.5: 1, 2, 3, 6, 8, 11, 15, 18, 20, 21, 22, 23, 28, 29, 30, 31, 34
Week 9-10:
Number Theory
Topics
- GCD, Euclid's Algorithm (Review)
- Groups and Fields
- Finite Fields
- Modular arithmetic with applications to cryptography
Textbook Sections
Recommended Exercises
- 3.8: 9, 13, 19, 25
- Handout: Ex 1, Ex 2, Ex 3 (all)
- 10.4: 1, 3, 7, 12, 15, 16, 19, 22, 26, 28, 31, 32, 34, 36, 39, 44, 45, 46
Weeks 11-12:
Counting and Probability - Chapter 6 (as time permits)
Topics
- Review of probability concepts:
addition and multiplication rules, permutations and combinations
Pascal's triangle.
- The binomial Theorem
- Probability axioms - Expectation
Textbook Sections
- 6.1, 6.2, 6.3, 6.4, 6.5, 6.6, 6.7, 6.8.
Recommended Exercises
- 6.1: 5, 9, 14, 16, 17, 21, 23, 26, 28, 31, 33
- 6.2: 6, 8, 9, 11, 16, 17, 18, 19, 24, 28, 31, 34, 38
- 6.3: 1, 3, 7, 8, 9, 11, 12, 13, 17, 19, 24, 26, 28, 30, 31
- 6.4: 5, 6, 8, 15, 19, 21, 24
- 6.5: 1, 3, 5, 8, 10, 11, 18
- 6.6: 1, 5, 6, 9, 12, 14, 15, 19
- 6.7: 1, 5, 11, 17, 18, 19, 24, 28, 34, 36,
- 6.8: 1, 2, 4, 7, 9, 14, 16, 19, 20, 22
This page is maintained by Peter Danziger.
Last modified
Wednesday, 06-Jan-2010 08:26:02 EST
