## MTH210 |
## Course Outline | |

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
- 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
- 4.1 (except for programming section), 4.2, 4.3, some of 4.4
- 8.1, 8.2, 8.4
- 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

#### Topics

#### Textbook Sections

#### Handouts

#### Recommended Exercises

## 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

- 12.1, 12.2, Handout, 5.4, 7.5.

#### 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

- 3.8,
- Groups Handout (To Appear)
- Finite Fields Handout, 10.4

#### 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

Last modified Wednesday, 06-Jan-2010 08:26:02 EST