## CPS420 |
## Lecture Material | |

Lecture | Topic | Textbook Chapters | Handouts | Other | Practice Exercises |
---|---|---|---|---|---|

1-4 | Sequences and Recursion | 5.1. 5.6, 5.7 | 1-1 Sequences and Recurrence Relations | 5.1: All the exercises with solutions (in blue) between 10 and 69
5.6: 1, 3, 5, 7, 9, 11, 13, 17ac, 18ab, 21, 37 5.7: 7b, 9, 12, 14, 19, 24, 50 | |

4-6 | Review of Proof Methods from MTH110 | 4 | 1-2 Proof Template:
pdf,
word
1-3 Proof Methods | See MTH110 | |

6-11 | Proofs by Induction | 5.2, 5.3, 5.4, 5.7 | 1-4 Induction | 5.2: 1, 3, 5, 6, 10, 13, 20, 28, 34, 35
5.3: 3, 4, 6, 11, 16, 19, 24, 30, 5.4: 1, 4, 11, 16, 29 5.6: 26, 27, 32, 41 5.7: 18, 26, 46, 48, 49 | |

12-13 | Graphs | 10.1 | 2-1 Graphs | 10.1: 1,3,5,8,14,17,18,21,24,27,35,39,41 | |

13-16 | Paths and Circuits | 10.2 | 2-2 Paths and Circuits | - Floor plan
- Eulerian curcuit?
- Bridges of Konigsburg: then and now
- Wikipedia: Eulerian Path
- Polyhedras: simple, Hamiltonian
- Wikipedia: Hamiltonian Path
- AGO Floor plans
| 10.2: 1,3,4,6,7,8,9,12-17,19,22,23,28-31 |

18 | Matrix Representation of Graphs | 10.3 | 2-4 Matrix Representation of Graphs | 10.3: 2,3,4,5,6,7,19,20,22 | |

17,19 | Trees | 10.5, 10.6, 10.7 (excluding algorithms) | 2-3 Trees | 10.5: 1,3, 7, 8-14, 22, 25-28
10.6: 1, 2, 3, 4-11, 20a 10.7: 1-4, 11 | |

20-22 | Formal Languages and Regular Expressions | 12.1 | 3-1 Formal Languages and Regular Expressions | 12.1: 1, 2, 3, 4, 7-12, 13-18, 19-21, 22-24, 25, 26, 28, 31, 34, 37, 39 | |

23-25 | Deterministic Finite State Automata | 12.2 | 3-2 Finite State Automata | 12.2: 1, 2-7, 8, 10, 12, 14-18, 20, 21, 23, 25, 26, 28, 29, 31, 33, 36, 39, 42, 45 | |

26-28 | Non-Deterministic Finite State Automata | CSC445 Course Notes on NFAs | 3-2 Finite State Automata | Exercises on NFAs in CSC445 Course Notes on NFAs | |

29-33 | Counting | 9.2, 9.3, 9.4, 9.5, 9.6, 9.7 | 4-1 Counting | Pascal's Triangle: Wikipedia, with a twist, remainders, and primes. | 9.2: 1, 8, 9, 11, 14, 15, 161-d, 19, 21, 23, 24, 27, 32, 34, 35, 39
9.3: 1, 3, 4, 6, 8a, 9, 11, 14, 9.4: 1, 3, 5, 7, 10, 12, 14, 17, 25, 26, 31 9.5: 1, 3, 6, 8, 9, 13, 15, 19 9.6: 1, 3, 5, 8, 10, 11, 16, 18, 19 9.7: 1-4, 6, 10, 13, 14, 19, 23, 25, 29-34, |

34-36 | Probabilities | 9.1, 9.8, 9.9 (excluding Bayes Theorem) | 4-2 Probabilities | 9.1: 1-12, 14, 16, 18, 21, 24
9.8: 1, 2, 4, 7, 9, 14, 16, 19, 20, 9.9: 1, 3, 5, 6, 17, 23, 31 |

Last modified Tuesday, 11-Apr-2017 19:04:52 EDT