MAT1348A Winter 2016

Discrete Mathematics for Computing
Classes: Mondays 14:30-16:00 and Thursdays 16:00-17:30, MNT202
DGDs:

Wednesdays, 10:00-11:30, SITE A0150, B0138 and G0103
Math Help Centre (Marion 021):


MTW 10:00-19:00
Th 10:00-17:00
F 10:00-15:00
Professor Tanya Schmah
Department of Mathematics and Statistics
Office 203, 555 King Edward Avenue
(613) 562-5800, ext. 3489
e-mail: tschmah@uottawa.ca
Important: Please include MAT1348 in the subject line of every email you send me and sign your message. Please do not use Blackboard to send me messages.
Office Hours Tuesdays 10-12, Thursdays 10-11, or by appointment.
All course information appears on this website. (There is no separate outline/syllabus document.)
You are responsible for this information, and for checking this page at least weekly, as new or updated information will appear throughout the session.

Course Outline: Introduction to discrete structures as a foundation to computing. Propositional logic. Fundamental structures: functions, relations, sets. The basics of counting: counting arguments, the pigeonhole principle, permutations and combinations. Introduction to proofs: direct, by contradiction, by cases, induction.  Topics in graph theory: isomorphism, cycles, trees, directed graphs.  Whenever possible applications from computing and information technology will be included.

Coursework Evaluation: The final grade will be calculated as follows:

9 homework assignments :      10%
Midterm exam 1 (Feb 8):         20% 
Midterm exam 2 (Mar 21):      20%          
Final exam:                               50%        

A mark of 40% or higher on the final exam is required for a pass in the course. In the exceptional case that the student missed a midterm exam for a valid reason, the weight of the final exam will increase to 70%. The two lowest assignment marks may be replaced by the percentage earned on the final exam if this is to the student's advantage.

Assignment Due Dates: All of the homework assignments are due Wednesdays at 3:00pm. You can submit during your DGD or in the appropriate submission box in the math department. Late submissions will not be accepted.

Required Textbook:
Kenneth H. Rosen, Discrete Mathematics and Its Applications, 7th Edition.
A customized electronic copy of the textbook (~$50) can be purchased here:
https://create.mheducation.com/shop/#/catalog/details/?isbn=9781308663203
A customized electronic copy of the solution manual (~$20) can be purchased here:
https://create.mheducation.com/shop/#/catalog/details/?isbn=9781308663210
The hard copies sell at the UO bookstore at about twice the price of the electronic copies.

Additional course notes will be made available on this webpage.

General Advice: Prepare for the lecture by reading ahead in the course text. You should take detailed notes in lectures. The only way to learn mathematics is by working on problems. Being able to follow the instructor solve a problem does not mean you can solve it yourself. In the DGD you work on problems, and the TA will provide feedback and suggestions for how to write down solutions. The DGD should not be regarded as another lecture, and you should prepare for the DGD by trying problems beforehand.

In the following table, "SE" refers to the Supplemental Exercises, for which solutions have been posted on Blackboard.

Lecture/DGD Topics To Read Suggested exercises Assignments
Jan. 11 Introduction. Propositions, logical connectives, truth-tables. Rosen Section 1.1. Additional handouts: Logical connectives. Rosen 1.1: 1, 5, 7, 9, 15, 16, 17, 21, 23, 25, 27, 31, 33, 37 (1-42, 48)
Jan. 13 (DGD) Problems for DGD1
Jan. 14 Precedence, consistency, knights and knaves problems Rosen Section 1.2. Additional handouts: Conditional propositions, Consistency, Knights and Knaves method, Knights and Knaves examples;
Door Scene from Labyrinth (the movie)
Jan. 18 More knights and knaves, tautology, contradiction, logical equivalence Rosen Sections 1.3. Additional handouts: Equivalences, DeMorgan Examples, DNF Rosen 1.2 : 1, 3, 7, 11, 19, 21, 23, 25 (1-12, 15-39)
SE2: 1-19
Jan. 20 (DGD) Problems for DGD2 Assignment 1 Due (Solutions)
Jan. 21 Disjunctive normal form, Truth trees (Not in Rosen) DNF; Truth Trees; Truth Tree Examples
See also: Dr. Scott's DNF and CNF notes Dr. Scott's Truth Tree notes 		Rosen 1.3 : 5, 7, 9, 11, 15, 23, 31, 41, 43, 45, 55 (1-33, 40-45, 55-57) SE1: 2,3, 4a
Jan. 25 Truth trees SE1: 1, 4b, 7, 8
Jan. 27 (DGD) Problems for DGD3 Assignment 2 Due (Solutions)
Jan. 28 Formal proofs Rosen Section 1.6; Rules of Inference;
Dr. Scott's note on Rosen-style proofs		 R1.6: 3, 5, 9bc, 31, 35 (1-6, 10abf, 11-12, 30-32, 34-35)
Feb. 1 Methods of proof Rosen Section 1.7 R1.7: 3, 9, 15, 17 (1-10, 13-18)
SE3: 1-3, 5-9
Feb. 3
(DGD)		 Problems for DGD4 Assignment 3 Due (Solutions on Blackboard)
Feb. 4 Methods of proof Rosen Sections 1.7, 1.8 R1.7: 27, 31, 39 (26-42)
R1.8: 3 (4)
SE3: 10-12
Feb. 8 * Midterm Exam 1 * All material up to and including proof by contraposition and contradiction
Feb. 10
DGD		 Problems for DGD5
Feb. 11 Proof strategies, introduction to sets Rosen Sections 1.8, 2.1 R2.1: 5, 7, 9, 1, 19, 21, 23, 27, 35, 39 (1-40)
SE4: 2, 3, 8
Feb. 15-19 --------- Reading Week ---------
Feb. 22 Sets Rosen Sections 2.1, 2.2. Set Identities R2.2: 3, 17, 19, 24, 27, 29, 30, 31, 32, 35, 36 (1-43)
SE4: 1-12
Feb. 24
(DGD)		 Problems for DGD6
Feb. 25 Sets. Functions Rosen Section 2.3 Assignment 4 Due 11am
Feb. 29 Functions Rosen Section 2.3 R2.3: 1, 7, 10-12, 15, 21, 23 (1-7, 10-23), 29, 39, 69 (28-36, 38-44)
SE5: 1, 2, 4, 5-8, 9-11
Mar. 2
(DGD)		 Problems for DGD7
Mar. 3 Functions, relations Rosen Sections 2.3, 9.1 Assignment 5 Due 11am
Mar. 7 Relations Rosen Section 9.1, 9.5 R9.1: 3, 7, 11, 15, 25 (1-15, 17-22, 24-25, 42-45)
SE6: 1-3, 4a-c,5-7, 9
Mar. 9
(DGD)		 Problems for DGD8
Mar. 10 Equivalence classes, partitions. Rosen Section 9.5 R9.5: 1, 3, 16, 25, 26, 29, 35, 40, 41, 43, 47, 57, 61 (1-20, 25-48, 57-59, 61-62)
SE7: 1, 2, 3, 6, 9 (1-11)		 Assignment 6 (corrected) Due 11am
Mar. 14 Counting: Product and Sum Rules, PIE Rosen Section 6.1 R6.1: 3, 17, 23, 29, 33, 37, 47(1-37, 40-63,70)
SE8: 1-3, 4a-d, 5, 6, 7, 11, 12 (1-12)
Mar. 16
(DGD)		 Problems for DGD9
Mar. 17 Counting: PIE, Pigeonhole Principle Rosen Sections 6.1, 6.2 R6.2: 6, 9, 11, 12, 15, 19, 33(1-19, 23-24, 31-40)
SE9: 2, 4, 7, 11 (1-12)		 Assignment 7 Due 11am. This is a group assignment. See assignment for instructions.
Mar. 21 Midterm Exam 2 (in class)
* Topics included: proofs (proof by cases, proof of equivalence, mixed-type proofs); sets, functions, relations, basic counting, PIE (no Pigeonhole Principle)
* a table of set identities will be provided
* the format will be similar to the first midterm exam
* NO CALCULATORS
Mar. 23
(DGD)		 Problems for DGD10
Mar. 24 Permutations and Combinations Rosen Section 6.3 R6.3: 9, 11, 13, 21, 23, 25, 31 (1-41, 43-45);
SE10: 1, 2, 4, 6-11, 13
Mar. 28 Easter Monday (no class)
Mar. 30
(DGD)		 Problems for DGD11
Mar. 31 Binomial Theorem; Mathematical Induction Rosen Sections 6.4, 5.1; themathpage.com Assignment 8 Due 11am. This is a group assignment. See assignment for instructions.
Apr. 4 Introduction to Graphs Graph Theory Notes
Apr. 6
(DGD)		 Problems for DGD12
Apr. 7 Assignment 9 Due 11am.
(Not a group assignment)
Apr. 11 (Last class)