CPS420 Lecture References and Practice Exercises

CPS420	Lecture References and Practice Exercises

Explanation

Lecture numbers are by hour and are approximate. They may be modified slightly during the semester.
The practice exercises are completely optional. The list is long and you are not expected to do them all. They have been chosen from the textbook as representative exercises with solutions. To get the full benefit of these exercises, work on them by yourselves before checking the solutions.
For each textbook reference, the editions of the textbook (4, 5, or both) is specified. Next to the exercises the annotations (4) and (5) indicate that the exercise is only in the 4th edition, or the 5th respectively. The exercises without such annotations are the same in both editions.

Lecture	Topic	Textbook Chapters	Summaries	Links	Practice Exercises
1-6	Sequences and Recursion	Both Editions: 5.1. 5.6, 5.7	1-1 Sequences and Recurrence Relations	On-line Encyclopedia of Integer Sequences Wikipedia: Tower of Hanoi, Interactive version Fibonacci: Rabbits, Growth, Wikipedia: Golden Ratio Wikipedia: Animation of right Riemann sum Sequences Examples For loops Basic Reproduction Number	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: 1, 2, 3, 6, 9, 10, 12, 14, 19, 24, 50
7-9	Review of Proof Methods from MTH110	4th Ed: 4.1 to 4.7 5th Ed: 4.1 to 4.8	1-2 Proof Template: pdf, word 1-3 Proof Methods	None	See MTH110
10-12	Proofs by Induction	Both Editions: 5.2, 5.3, 5.4, 5.7	1-4 Induction Notes on proofs by induction	Domino Designer Dominos	5.2: 1(4), 3, 5, 6, 10, 13, 20, 28, 30(5) 34(4), 35(4), 37(5), 38(5) 5.3: 1(5), 3(4), 4, 6(4), 11, 16, 19, 24, 30(4),45(5) 5.4: 1, 4, 11, 16, 29(4), 34(5) 5.6: 26, 27, 32, 41 5.7: 18, 26, 46, 48, 49
13-14	Graphs	4th Ed: 10.1, 10.4 5th Ed: 1.4, 4.9, 10.3	2-1 Graphs	Wikipedia: Graph Theory Monsters and Munchkins Air routes map Wikipedia: Complete graphs	4th Ed: 10.1: 1,3,5,8,14,17,18,21,24,27,39,42 5th Ed: 1.4: 1,3,5,8,14 5th Ed: 4.9: 5, 6, 9, 12, 16 5th Ed: 10.1: 24, 27 10.4(4)=10.3(5): 1,2,6,8,10,12,14,18
15-16	Paths and Circuits	4th Ed: 10.2 5th Ed: 10.1	2-2 Paths and Circuits	Floor plan Eulerian curcuit? Bridges of Konigsburg: then and now Wikipedia: Eulerian Path Building an Euler circuit Polyhedras: simple, Hamiltonian Wikipedia: Hamiltonian Path AGO Floor plans	4th Ed: 10.2: 1,3,4,6,7,8,9,12-17,19,22,23,28-31 5th Ed: 10.1: 1,3,4,6,7,8,9,12-17,19,22,29,34-37
17-18	Matrix Representation of Graphs	4th Ed: 10.3 5th Ed: 10.2	2-4 Matrix Representation of Graphs	Wikipedia: Adjacency Matrix	4th Ed: 10.3: 2,3,4,5,6,7,19,20,22 5th Ed: 10.2: 2,3,4,5,6,7,19,20,22
18-19	Trees	4th Ed: 10.5, 10.6 5th Ed: 10.4, 10.5	2-3 Trees	Wikipedia: Tree Data Structure Wikipedia: Binary Tree Wikipedia: Phylogenetic Tree	10.5(4)=10.4(5): 1,3, 7, 8-14, 22, 25-28 10.6(4)=10.5(5): 1, 2, 3, 4-11, 20a
20-22	Formal Languages and Regular Expressions	5th Ed: 1.2.8 Both Editions: 12.1	3-1 Formal Languages and Regular Expressions	Wikipedia: Formal Language Wikipedia: Regular Expression	1.2: 15(5), 16(5) 12.1: 1, 2, 3, 4, 7-12, 13-21, 22-24, 25, 26, 28, 31, 34, 37, 39
22-24	Deterministic Finite State Automata	Both Editions: 12.2	3-0 Automata Examples 3-2 Finite State Automata	Wikipedia: Finite State Machine Automaton Simulator	12.2: 1, 2-7, 8, 10, 12, 14-18, 20, 21, 22(5) 23(4), 25, 26, 28, 29, 31, 33, 36, 39, 42, 45
25-27	Non-Deterministic Finite State Automata	CSC445 Course Notes on NFAs	3-0 Automata Examples 3-2 Finite State Automata	Wikipedia: Non-deterministric Finite State Automaton Building a DFA from an NFA Automaton Simulator	Exercises on NFAs in CSC445 Course Notes on NFAs
28-31	Counting	Both Editions: 9.2, 9.3, 9.4, 9.5, 9.6, 9.7	4-1 Counting Counting Problem Set	Loop Iterations Pascal's Triangle: Wikipedia, with a twist, remainders, and primes.	9.2: 1, 8, 9, 11, 14, 15, 16a-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
32-36	Probabilities	Both Editions: 9.1, 9.8, 9.9	4-2 Probabilities Probabilities Problem Set	Wikipedia: Sample space The Bayesian Trap a video on Bayes Theorem. There are some useful clarifications in some of the comments.	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

This page is maintained by Sophie Quigley (cps420@cs.torontomu.ca)
Last modified Wednesday, 06-Mar-2024 11:35:54 EST