DISCRETE STRUCTURES FOR COMPUTING, CS2214A, FALL 2016-2017

Instructor

Professor Lila Kari

Department of Computer Science

Middlesex College, MC385

www.csd.uwo.ca/~lila

Announcements

Course Outline

Class schedule

Monday 1:30pm-3:30pm, SH3345, Wednesday, 2:30am- 4:30pm, SH3345

Assignments

All assignment submissions are hard-copy (paper) submissions, to be dropped in the CS2214 locker (see info below) by 6pm on the due date.

Please place the stapled pages of your assignment in an open letter-size envelope, and write your name and student number clearly, both on the envelope and on the first page of the assignment.

CS2214 Locker: 300/301, Middlesex College Building, 3rd floor

Teaching Assistants

Gurjit Randhawa grandha8@uwo.ca
Zihao Wang zwang688@uwo.ca
Zhao Lin zlin45@uwo.ca

Office hours

Office hours begin the week of September 26.

Tuesday, 11:30pm - 12:30pm, Zihao Wang, MC4A
Wednesday, 10:30am-12:20pm, Lila Kari, MC385
Wednesday, 12:30pm - 1:30pm, Gurjit Randhawa, MC4A
Wednesday, 4:30pm - 5:30pm, Zhao Lin, MC4A

Course Notes

(The exercises in boldface to be solved in class.)

# Date Notes Topic Textbook reading Textbook exercises

L01 Mon.Sep.12 Notes Introduction

Notes, pp.1-19 Propositional logic Section 1.1 Exercises pp. 13-15: 11, 13, 15 , 21,

L02 Wed.Sep.14 Notes, pp.20-57 Propositional logic contd. Section 1.1, 1.2, 1.3 Exercises pp. 13-15: 22 , 23, 25, 27, 28, 29, 37, 42

L03 Mon.Sep.19 Notes, pp.1-41 Predicate logic Section 1.4 Exercises 9/p.53, 12/p.53, 13/p.53, 23/p.53 , 25/p.54, 62/p.57

L04 Wed.Sep.21 Notes, pp.42-63 Predicate logic, nested quantifiers Section 1.5 Exercises 10/p.65, 13/p.66

Notes, pp.1-14 Introduction to proofs: direct proof Section 1.7 Exercises 3, 4, 5, 7, 9, 13, 15, 16, 17, 22 (page 91)

L05 Mon.Sep.26 Notes, pp. 15 - 34 Proof methods and strategies: proof by contraposition, contradiction, "iff" proofs, proof by cases Section 1.7, 1.8 Exercises: 3, 4, 5 , 7, 9, 13, 15, 16, 17 , 22 (page 91), 3, 7 (p.108), 39/p.113

L06 Wed.Sep.28 Notes 1, pp.35-47, Proof methods and strategies: nonconstructive existence proofs, additional proof methods Section 1.8 Exercises: 7 (p.108)

Notes 2, pp. 1-80. Basic Structures: Sets (computer representation of sets), Set operations, Functions (floor and ceiling function); Section 2.1, 2.2, 2.3 Exercises: 52, 53, 54, 55 (p. 137)

L07 Mon.Oct.3 Notes, pages 80-84 Floor and ceiling functions Section 2.3 Exercises: 59, 60, 61 (page 155)

Notes, pages 1-46 Sequences and summations, Cardinality of sets Section 2.4, 2.5 Exercises: 4, 7, 9, 11, 17, 18, 19, 20 (page 168)

L08 Wed.Oct. 5 Notes, pages 47-75 Cardinality of sets; Matrices Section 2.5, 2.6 Exercises: 1 (page 176), 3 (page 183)

L09 Wed.Oct. 12 Notes, pages 1-47 Divisibility and modular arithmetic, Integer representations Section 4.1, 4.2 Exercises: 3, 4, 11 , 13, 21, 29, 31, (page 244); 1, 3, 5, 7, 9, 11, 21, 31 (page 255)

L10 Mon.Oct. 17 Notes, pages 48- 79 Primes and greatest common divisors, Solving congruences Section 4.3, 4.4 Exercises: 1, 3, 25, 27, 30, 31, 33, 39 (page 272); 5, 9, 11 (page 285);

L11 Wed.Oct. 19 Notes, pages 80 - 99 Applications of congruences, Cryptography Section 4.5, 4.6 Exercises: 3, 5, 7, 15, 17, 19 (page 292); 3, 5, 11 (page 305).

L12 Mon.Oct. 24 Midterm Review

L13 Wed.Oct. 26 In-class Midterm Exam

L14 Mon.Oct. 31 Notes, pages 1-16 Mathematical induction Section 5.1 Exercises: 3, 4, 5, 11 , 15, 19, 20, 21, 34, 50, 51, 56 (page 329);

L15 Wed. Nov.2 Notes, pages 17-37 Induction, strong induction Section 5.1, 5.2 Exercises 3, 4, 5, 11 , 15, 19, 20, 21, 34 , 50, 51, 56 (page 330), 3 (page 341)

L16 Mon. Nov.7 Notes, pages 38-78 Recursion, structural induction Section 5.3, 5.4 Exercises 5, 12, 13, 36, 37, 41, 43 , 44 (page 358)

L17 Wed. Nov.9 Notes, pages 1-31 The basics of counting Section 6.1 Exercises 1, 3, 5, 7, 11, 13, 17, 19 , 21, 41, 43, 49 , 55 , 57, 59, (pages 396-398)

L18 Mon. Nov.14 Notes, pages 32- 56 The pigeonhole principle, Permutations and combinations Section 6.2, 6.3 Exercises 1 , 3, 5 , 9, 15, 31, 33 , 35, 37 (pages 405-406); 1, 5, 11 , 15, 17, 19, 25 , 31 (page 413)

L19 Wed. Nov.16 Notes, pages 57-65 Binomial coefficients and identities Section 6.4 Exercises 1, 5, 7, 9, 21, 23 , 25 (page 421)

Notes, pages 1-20 Introduction to discrete probability Section 7.1 Exercises 1, 3, 5, 7, 9, 11 , 13 , 15, 25, 29 (page 451)

L20 Mon. Nov.21 Notes, page 21- 39 Probability theory Section 7.2 Exercises 1, 5, 7, 9, 13, 23 , 25 , 31, 35 (page 466)

L21 Wed. Nov.23 Notes, page 40-61 Bernoulli trials, Bayes' Theorem Section 7.2, 7.3 Exercises 1, 3, 5, 7, 9 , 11, 19 , 21 (page 475)

L22 Mon. Nov.28 Notes, page 62-68 Bayesian spam filters Section 7.3 Exercises 1, 3, 5, 7, 9, 11, 19 , 21 (page 475)

Notes 1-45 Relations Section 9.1, 9.3 Exercises 1, 3, 5, 7 , 33, 39, 41, 45 (page 581); 1, 3, 9, 15, 19, 21, 23, 25, 31 (page 596)

L23 Wed. Nov.30 Notes, page 46-71 Equivalence relations, Partial orderings Section 9.5, 9.6 Exercises 3, 5, 7, 9, 11, 13, 15, 21, 25, 29, 35, 37, 41, (page 615); 1, 3, 5, 7, 9, 11 , 17, 19, 21 (page 631).

L24 Mon. Dec.5 Notes, pages 1-59 Graphs, Special types of graphs, Representing graphs and graph isomorphism Section 10.1, 10.2, 10.3 Exercises 3, 5, 7, 9, 11, 13, 15, 19, 29 (page 650); 1, 3, 5, 7, 9, 13, 21, 30 , 35 (page 665); 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 27, 35 , 39 , 41 (page 676)

L25 Wed. Dec.7 Notes, pages 60-98 Connectivity, Euler and Hamiltonian paths Section 10.4, 10.5 Exercises 1, 3, 5, 9 (page 689); 1, 3, 5, 7, 13, 14, 15, 31, 37 (page 703).

#	Date	Notes	Topic	Textbook reading	Textbook exercises
L01	Mon.Sep.12	Notes	Introduction
		Notes, pp.1-19	Propositional logic	Section 1.1	Exercises pp. 13-15: 11, 13, 15 , 21,
L02	Wed.Sep.14	Notes, pp.20-57	Propositional logic contd.	Section 1.1, 1.2, 1.3	Exercises pp. 13-15: 22 , 23, 25, 27, 28, 29, 37, 42
L03	Mon.Sep.19	Notes, pp.1-41	Predicate logic	Section 1.4	Exercises 9/p.53, 12/p.53, 13/p.53, 23/p.53 , 25/p.54, 62/p.57
L04	Wed.Sep.21	Notes, pp.42-63	Predicate logic, nested quantifiers	Section 1.5	Exercises 10/p.65, 13/p.66
		Notes, pp.1-14	Introduction to proofs: direct proof	Section 1.7	Exercises 3, 4, 5, 7, 9, 13, 15, 16, 17, 22 (page 91)
L05	Mon.Sep.26	Notes, pp. 15 - 34	Proof methods and strategies: proof by contraposition, contradiction, "iff" proofs, proof by cases	Section 1.7, 1.8	Exercises: 3, 4, 5 , 7, 9, 13, 15, 16, 17 , 22 (page 91), 3, 7 (p.108), 39/p.113
L06	Wed.Sep.28	Notes 1, pp.35-47,	Proof methods and strategies: nonconstructive existence proofs, additional proof methods	Section 1.8	Exercises: 7 (p.108)
		Notes 2, pp. 1-80.	Basic Structures: Sets (computer representation of sets), Set operations, Functions (floor and ceiling function);	Section 2.1, 2.2, 2.3	Exercises: 52, 53, 54, 55 (p. 137)
L07	Mon.Oct.3	Notes, pages 80-84	Floor and ceiling functions	Section 2.3	Exercises: 59, 60, 61 (page 155)
		Notes, pages 1-46	Sequences and summations, Cardinality of sets	Section 2.4, 2.5	Exercises: 4, 7, 9, 11, 17, 18, 19, 20 (page 168)
L08	Wed.Oct. 5	Notes, pages 47-75	Cardinality of sets; Matrices	Section 2.5, 2.6	Exercises: 1 (page 176), 3 (page 183)
L09	Wed.Oct. 12	Notes, pages 1-47	Divisibility and modular arithmetic, Integer representations	Section 4.1, 4.2	Exercises: 3, 4, 11 , 13, 21, 29, 31, (page 244); 1, 3, 5, 7, 9, 11, 21, 31 (page 255)
L10	Mon.Oct. 17	Notes, pages 48- 79	Primes and greatest common divisors, Solving congruences	Section 4.3, 4.4	Exercises: 1, 3, 25, 27, 30, 31, 33, 39 (page 272); 5, 9, 11 (page 285);
L11	Wed.Oct. 19	Notes, pages 80 - 99	Applications of congruences, Cryptography	Section 4.5, 4.6	Exercises: 3, 5, 7, 15, 17, 19 (page 292); 3, 5, 11 (page 305).
L12	Mon.Oct. 24	Midterm Review
L13	Wed.Oct. 26	In-class Midterm Exam
L14	Mon.Oct. 31	Notes, pages 1-16	Mathematical induction	Section 5.1	Exercises: 3, 4, 5, 11 , 15, 19, 20, 21, 34, 50, 51, 56 (page 329);
L15	Wed. Nov.2	Notes, pages 17-37	Induction, strong induction	Section 5.1, 5.2	Exercises 3, 4, 5, 11 , 15, 19, 20, 21, 34 , 50, 51, 56 (page 330), 3 (page 341)
L16	Mon. Nov.7	Notes, pages 38-78	Recursion, structural induction	Section 5.3, 5.4	Exercises 5, 12, 13, 36, 37, 41, 43 , 44 (page 358)
L17	Wed. Nov.9	Notes, pages 1-31	The basics of counting	Section 6.1	Exercises 1, 3, 5, 7, 11, 13, 17, 19 , 21, 41, 43, 49 , 55 , 57, 59, (pages 396-398)
L18	Mon. Nov.14	Notes, pages 32- 56	The pigeonhole principle, Permutations and combinations	Section 6.2, 6.3	Exercises 1 , 3, 5 , 9, 15, 31, 33 , 35, 37 (pages 405-406); 1, 5, 11 , 15, 17, 19, 25 , 31 (page 413)
L19	Wed. Nov.16	Notes, pages 57-65	Binomial coefficients and identities	Section 6.4	Exercises 1, 5, 7, 9, 21, 23 , 25 (page 421)
		Notes, pages 1-20	Introduction to discrete probability	Section 7.1	Exercises 1, 3, 5, 7, 9, 11 , 13 , 15, 25, 29 (page 451)
L20	Mon. Nov.21	Notes, page 21- 39	Probability theory	Section 7.2	Exercises 1, 5, 7, 9, 13, 23 , 25 , 31, 35 (page 466)
L21	Wed. Nov.23	Notes, page 40-61	Bernoulli trials, Bayes' Theorem	Section 7.2, 7.3	Exercises 1, 3, 5, 7, 9 , 11, 19 , 21 (page 475)
L22	Mon. Nov.28	Notes, page 62-68	Bayesian spam filters	Section 7.3	Exercises 1, 3, 5, 7, 9, 11, 19 , 21 (page 475)
		Notes 1-45	Relations	Section 9.1, 9.3	Exercises 1, 3, 5, 7 , 33, 39, 41, 45 (page 581); 1, 3, 9, 15, 19, 21, 23, 25, 31 (page 596)
L23	Wed. Nov.30	Notes, page 46-71	Equivalence relations, Partial orderings	Section 9.5, 9.6	Exercises 3, 5, 7, 9, 11, 13, 15, 21, 25, 29, 35, 37, 41, (page 615); 1, 3, 5, 7, 9, 11 , 17, 19, 21 (page 631).
L24	Mon. Dec.5	Notes, pages 1-59	Graphs, Special types of graphs, Representing graphs and graph isomorphism	Section 10.1, 10.2, 10.3	Exercises 3, 5, 7, 9, 11, 13, 15, 19, 29 (page 650); 1, 3, 5, 7, 9, 13, 21, 30 , 35 (page 665); 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 27, 35 , 39 , 41 (page 676)
L25	Wed. Dec.7	Notes, pages 60-98	Connectivity, Euler and Hamiltonian paths	Section 10.4, 10.5	Exercises 1, 3, 5, 9 (page 689); 1, 3, 5, 7, 13, 14, 15, 31, 37 (page 703).