# (ECEN 2703) Discrete Mathematics

This course will focus on the fundamentals of Discrete Math. The topics will include (i) mathematical reasoning and proof, (ii) sets, functions, and relations, (iii) combinatorics and probability theory, and (iv) graph theory. We will present motivating examples from both the engineering and social sciences.

**Term:** Fall Semester, 2013

**Lecture:** Monday, Wednesday, and Friday, 10:00-10:50, ECEE 1B32

**Office Hours:**Monday 11:00-12:00 in ECOT 332, Thursday 9:00-10:00 in ECEE 1B32, or by email appointment

**Text:** *Discrete Mathematics: Mathematical Reasoning and Proof with Puzzles, Patterns, and Games*,
Ensley and Crawley.

**Teaching Assistant:** Holly Borowski

**Teaching Assistant Recitation:** Tuesday, 8:00-9:15, ECEE 1B32

**Teaching Assistant Office Hours:** Tuesday, 4:30-5:30, ECEE 1B93

**Syllabus:** [pdf]

# Announcements:

- 11/30/2013: There will be no quiz this Wednesday to give you extra time to finish the tetris project. HW will still be due. Please turn in HW in class on Wednesday.
- 11/8/2013: Quiz #9 will cover Sections 5.1, 5.2, and 5.3.
- 10/7/2013: Note the following protocol for midterm regrades. If you got below a 69 on the exam, you can take the following steps to improve your grade to a 69. The steps are as follows:
- Redo the midterm exam and turn in by Friday (10/11/2013) at 2:00 pm in my office. Exam must be 100% perfect.
- Redo all HW problems from Chapters 1 and 2. This must be submitted by Friday at 2:00 pm as well.
- For the rest of the semester, complete all HW problems on a weekly basis and turn them in every Tuesday by 2:00 pm in my office. Each HW will cover the problems assigned on Monday's lecture as well as the previous week's Wednesday and Friday lectures.

- 9/18/2013: The first computer project is now posted. Furthermore, the first midterm will be in class on Wednesday, October 2.
- 9/16/2013: There will be a quiz scheduled on Wednesday 9/18/2013. The quiz will cover lectures 6,7, and 8, and their respective problems.
- 9/14/2013: I hope everyone is safe given the current state of Boulder. I will be on travel Monday and Tuesday of the coming week. The lecture on Monday 9/16/2013 will be given by Dr. Ragavendran Gopalakrishhnan. Office hours on Monday will be given by Holly is office ECEE 1B93 from 11:00-12:00. As of now, there will still be a quiz scheduled for Wednesday 9/18/2013.
- 8/30/2013: The questions on the quiz will be drawn from the following sources:
- Definitions from the sections reviewed in the previous week.
- Examples from the sections reviewed in the previous week.
- Problems assigned in the previous week.

- 8/28/2013: There will be a quiz on Wednesday, September 4. This quiz will cover lectures 2 and 3.
- 8/26/2013: Welcome to the course website for ECEN 2073 - Discrete Mathematics.

# Lectures

- 08/26/2013 - Lecture 1: Overview
- 08/28/2013 - Lecture 2: Sequences [Lecture Notes]
- Section: 1.2, Problems: 7 (b,d), 18, 26 (a-e), 28 (b), 29 (a,b), 30 (a,b) [Problems] [Solutions]
- 08/30/2013 - Lecture 3: Propositions [Lecture Notes]
- Section: 1.3, Problems: 3 (a-c), 4 (a-d), 7 (b,d), 8 (b,d), 11 (b,c,e), 17 [Problems] [Solutions]
- 09/4/2013 - Lecture 4: Predicates [Lecture Notes]
- Section: 1.4, Problems: 4,5,9,12,14,15 [Solutions]
- 09/6/2013 - Lecture 5: Implications [Lecture Notes]
- Section: 1.5, Problems: 4 (b,d,f), 5 (b,d,e), 8 (a,b,c,d), 17 (a,b,c,d), 18, 25 (b,d,e), 30 (b,d,f,g) [Solutions]
- 09/9/2013 - Lecture 6: Proofs [Lecture Notes]
- Section: 2.1, Problems: 5 (a,b,c), 6, 7, 10 (a,b,c), 11(a,b,c), 12 (b,d,e), 13 (b,d) [Solutions]
- 09/11/2013 - Lecture 7: Proofs [Lecture Notes]
- Section: 2.1, Problems: (same as above)
- 09/16/2013 - Lecture 8: Proofs about numbers [Lecture Notes]
- Section: 2.2, Problems: 3 (b,d,f (for part f, let k be a positive integer)), 10, 12, 13 (b), 15, 17, 19 [Solutions]
- 09/18/2013 - Lecture 9: Project Review
- 09/20/2013 - Lecture 10: Induction [Lecture Notes]
- Section: 2.3, Problems: 8 (b,d,f), 9 (a), 12, 13 [Solutions]
- 09/23/2013 - Lecture 11: Induction and Contradiction [Lecture Notes]
- Section 2.4: 12, 14 (a,b), 15, 17, 19 (a,b,c) [Solutions]
- 09/25/2013 - Lecture 12: Contradiction and Pigeon Hole Principle [Lecture Notes]
- Section 2.5: 3, 12, 17, 24, 28, 34 (a,b) [Solutions]
- 09/27/2013 - Lecture 13: Finish Previous Lecture.
- 09/30/2013 - Lecture 14: Dynamic Programming [Lecture Notes]
- 10/2/2013 - Lecture 15: Midterm #1
- 10/4/2013 - Lecture 16: Introduction to Sets [Lecture Notes]
- Section 3.1: 18 (a-e), 21 (a-f), 23 (a,b)
- Section 3.2: 1 (a-ef), 5, 12, 13 (a-e), 17 (a-d)
- [Solutions]
- 10/7/2013 - Lecture 17: Proofs about sets [Lecture Notes]
- 10/9/2013 - Lecture 18: Proofs about sets (cont) [Lecture Notes]
- Section 3.3: 2 (b), 3 (a), 10 (a,d), 15, 16 (a-c), 17 (a-c) [Solutions]
- 10/11/2013 - Lecture 19: Finish sets. Introduction to functions [Lecture Notes]
- Section 4.1: 5, 11(a-d), 15(a-d), 20, 25(b,d) [Solutions]
- 10/14/2013 - Lecture 20: The Composition Operation [Lecture Notes]
- Section 4.2: 2(a-c), 7(a-d), 9, 12, 16 [Solutions]
- 10/16/2013 - Lecture 21: Inverses, Function definitions [Lecture Notes]
- 10/18/2013 - Lecture 22: Inverses, Cardinality, Cantor's Theorem [Lecture Notes]
- Section 4.3: 4(b,c), 6(a-c), 8, 9, 13, 15, 20 (a-d), 22, 23, 26, 30, 31 [Solutions]
- 10/21/2013 - Lecture 23: Cardinality, Cantor's Theorem (Finish Previous Lecture)
- 10/23/2013 - Lecture 24: Dynamic Programming [Lecture Notes]
- 10/25/2013 - Lecture 25: Relations, Orderings [Lecture Notes]
- Section 4.4: 3(b-c), 4(b-c), 12, 14(a-c), 18(a-c), 22 [Solutions]
- 10/28/2013 - Lecture 26: Equivalences [Lecture Notes]
- Section 4.5: 2(b), 3(b,d), 5, 14(a-c), 17(a-b), 20(a-b) [Solutions]
- 10/30/2013 - Lecture 26: Equivalences [Lecture Notes]
- 11/01/2013 - Lecture 27: Combinatorics [Lecture Notes]
- 11/03/2013 - Lecture 28: Permutations and Sets [Lecture Notes]
- 11/08/2013 - Lecture 29: Binomial Theorem [Lecture Notes]
- Section 5.1: 14(b,d), 15(b), 17(a-c)
- Section 5.2: 7(a-d), 11(a-c), 15(a-c), 24(a-d), 35
- Section 5.3: 8, 13, 18(a-c), 28(a-b), 36, 37
- [Solutions]
- 11/11/2013 - Lecture 30: Probability [Lecture Notes]
- Section 6.1: 8(a-c),13(a-c), 18 [Solutions]
- 11/13/2013 - Lecture 31: Independence and Conditional Probabilities [Lecture Notes]
- 11/15/2013 - Lecture 32: Bernoulli Trials [Lecture Notes]
- Section 6.2: 6(a-c), 16, 20 (a-c), 22(a-d)
- Section 6.3: 10,15,23
- Extra: [Problem]
- [Solutions]
- 11/18/2013 - Lecture 33: Expected Values [Lecture Notes]
- Section 6.3: 21 (a,b)
- Section 6.4: 2,7,10,16,24
- [Solutions]
- 11/20/2013 - Lecture 34: Stochastic Dynamic Programming [Lecture Notes]
- 11/22/2013 - Lecture 35: Graph Theory [Lecture Notes]
- Section 7.1: 3 (a-d), 8,10, 16, 22
- [Solutions]
- 12/2/2013 - Lecture 35: Proofs about graphs [Lecture Notes]
- 12/4/2013 - Lecture 36: Spanning trees [Lecture Notes]
- 12/6/2013 - Lecture 37: Planar graphs [Lecture Notes]
- 12/6/2013 (late) - Lecture 38: Adjacency graphs [Lecture Notes]
- Section 7.2: 3(f), 12, 16, 18, 24
- Section 7.3: 4 (a,b,c),6,8,9,11,13 (a,b,c), 16
- Section 7.4: 2 (b,c), 3(b,c,d), 9 (b,d), 10 (b,d), 11(b,d), 15(b,d),16
- [Solutions]

# Quizzes

- 09/04/2013 - Quiz #1 [PDF] [Solutions]
- 09/11/2013 - Quiz #2 [PDF] [Solutions]
- 09/18/2013 - Quiz #3 [PDF] [Solutions]
- 09/25/2013 - Quiz #4 [PDF] [Solutions]
- 10/9/2013 - Quiz #5 [PDF] [Solutions]
- 10/16/2013 - Quiz #6 [PDF] [Solutions]
- 10/23/2013 - Quiz #7 [PDF] [Solutions]
- 10/30/2013 - Quiz #8 [PDF] [Solutions]
- 10/30/2013 - Quiz #9 [PDF] [Solutions]
- 10/30/2013 - Quiz #10 [PDF] [Solutions]

# Midterms

- Midterm #1 (date: October 2, 2013) [PDF]
- Midterm from last term: [PDF]
- Note: This midterm may not reflect the topics covered on this year's midterm.

- Midterm #2 (date: November 6, 2013)
- Midterm from last term: [PDF] [Solutions]
- Note: This midterm may not reflect the topics covered on this year's midterm.

- Final Exam (date: Monday, December 16, 2013, 4:30 - 7:00)
- Final from last term: [PDF]
- Note: This final may not reflect the topics covered on this year's final.

# Computer Projects

- Computer Project #1 (due September 27, 2013 at 5:00 pm) [PDF]
- Typed reports due at ECEE Main Office by 5:00 pm
- No late work accepted
- Working Code with nested for loops [Version 1]
- Working Code with recursive functions [Version 2]
- Computer Project #2 (due October 18, 2013 at 5:00 pm) [PDF]
- No late work accepted
- Computer Project #3 (due November 15, 2013 at 5:00 pm) [PDF]
- Computer Project #4 (due December 6, 2013 at 11:59 pm) [PDF]
- Submit project: [Here]
- Student Numbers [PDF]
- Tetris Simulator [Zip File]
- No late work accepted