# (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, 2014

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

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

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

**Teaching Assistant:** Philip Brown, (first-name.last-name *at * colorado * dot * edu)

**Teaching Assistant Recitation/Office Hours:**

- Tuesday, 5:00-6:00pm, ECEE 1B45
- Thursday 3:00-4:00, ECEE 1B93
- Thursday, 5:00-6:00pm, ECEE 265

**Syllabus:**[pdf]

# Announcements:

- 9/29/2014: I will be on travel from Tuesday (9/30/2014) to Friday (10/3/2014). Philip will cover lecture. My office hours for Thursday are cancelled for this week.
- 8/25/2014: Welcome to the course website for ECEN 2073 - Discrete Mathematics.

# Lectures

- 08/25/2014 - Lecture 1: Overview
- 08/27/2014 - Lecture 2: Sequences [pdf]
- 08/29/2014 - Lecture 3: Truth Tables and Propsotions [pdf]
- 09/01/2014 - No Class
- 09/03/2014 - Lecture 4: Propositions and Predicates [pdf]
- 09/05/2014 - Lecture 5: Implications [pdf]
- 09/08/2014 - Lecture 6: Proofs [pdf]
- 09/10/2014 - Lecture 7: Proofs about numbers [pdf]
- 09/12/2014 - Lecture 8: Induction [pdf]
- 09/15/2014 - Lecture 9: Induction and Examples [pdf]
- 09/17/2014 - Lecture 10: Induction, Contradiction [pdf]
- 09/19/2014 - Lecture 11: Contradiction and Pigeon Hole Principle [pdf]
- 09/22/2014 - Lecture 12: Dynamic Programming [pdf]
- 09/29/2014 - Lecture 13: Introduction to sets [pdf]
- 10/01/2014 - Lecture 14: Proofs about sets [pdf]
- 10/03/2014 - Lecture 15: Introduction to functions [pdf]
- 10/06/2014 - Lecture 16: Functions, compositions, and inverses [pdf]
- 10/08/2014 - Lecture 17: Inverses [pdf]
- 10/10/2014 - Lecture 18: Cardinality [pdf]
- 10/13/2014 - Lecture 19: Cardinality (Continue previous lecture)
- 10/15/2014 - Lecture 20: Relations and Orders [pdf]
- 10/17/2014 - Lecture 21: Orders and Equivalence Relations [pdf]
- 10/20/2014 - Lecture 21: Equivalence Relations [pdf]
- 10/22/2014 - Lecture 22: Combinatorics [pdf]
- 10/24/2014 - Lecture 23: Counting sets, Binomial Theorem [pdf]
- 11/3/2014 - Lecture 24: Probability [pdf]
- 11/5/2014 - Lecture 25: Conditional Probabilities [pdf]
- 11/7/2014 - Lecture 26: Bernoulli Trials [pdf]
- 11/12/2014 - Lecture 27: Stochastic Dynnamic Programming [pdf]
- 11/17/2014 - Lecture 28: Expectations and Issues [pdf]
- 11/19/2014 - Lecture 29: Introduction to Graph Theory [pdf]
- 11/21/2014 - Lecture 30: Proofs about graphs [pdf]
- 12/1/2014 - Lecture 31: Finish previous lecture
- 12/3/2014 - Lecture 32: Spanning Trees [pdf]
- 12/5/2014 - Lecture 33: Planar graphs [pdf]
- 12/8/2014 - Lecture 34: Adjacency Matrices [pdf]

# Homeworks

- Homework 1 - Due 09/03/2014
- Read Sections 1.2 and 1.3
- Section: 1.2, Problems: 6(b,d), 20, 21(d,e), 22, 26(d,e,f), 28(a), 29(a,b)
- Section: 1.3, Problems: 4(a-d), 6(b,d), 9(a-d), 11(b,c,e), 16, 17, 18
- Solutions: [pdf]
- Homework 2 - Due 09/10/2014
- Read Sections 1.4 and 1.5
- Section: 1.4, Problems: 3, 5, 9, 12, 14, 15
- Section: 1.5, Problems: 4 (b,d,f), 6, 8 (c,d), 17 (a,b,c,d), 18, 21, 25 (d,e), 30 (d,f)
- Solutions: [pdf]
- Homework 3 - Due 09/17/2014
- Read Sections 2.1, 2.2, and 2.3
- Section: 2.1, Problems: 5 (a,b,c), 10 (a,b), 12 (b,c), 13 (b,d)
- Section: 2.2, Problems: 2 (b,d,f), 6 (a), 10, 13 (b), 15, 17, 19
- Section: 2.3, Problems: 7, 8(b,d,f), 9(b)
- Solutions: [pdf]
- Homework 4 - Due 09/22/2014 (Note: Monday instead of Wednesday)
- Read Sections 2.4 and 2.5
- Section: 2.3, Problems: 12, 13
- Section: 2.4, Problems: 13(a,b), 15, 17, 19 (a,b,c)
- Section: 2.5, Problems: 3, 6, 12, 17, 25, 27, 34 (a,b), 36 (a,b,c,d)
- Solutions: [pdf]
- Homework 5 - Due 10/08/2014
- Read Sections 3.1, 3.2, and 3.3
- Section: 3.1, Problems: 15 (b,d,f), 16 0(b,d), 18 (a-c), 24
- Section: 3.2, Problems: 1 (a-e), 2 (a,b), 6, 12, 13 (a-e), 17 (b,d), 20
- Section: 3.3, Problems: 6 (b,c), 7, 11 (b,d), 13 (b,c), 16 (a-c), 17 (a)
- Solutions: [pdf]
- Homework 6 - Due 10/15/2014
- Read Sections 4.1, 4.2, and 4.3
- Section 4.1: 3, 10(a-c), 13, 15, 17(b,c), 20
- Section 4.2: 4, 7(a-d), 11, 13(a,b), 15
- Section 4.3: 2(a-c), 6(a-c), 9, 13, 14(a-c), 20(a-d), 22, 29, 30, 31
- Solutions: [pdf]
- Homework 7 - Due 10/22/2014
- Read Sections 4.4 and 4.5
- Section 4.4: 3(b-c), 4(b-c), 11, 12, 14(a-c), 15(b,d), 17(a-c), 19
- Section 4.5: 2(b), 3(b,d), 5, 14(a-c), 17(a-b), 20(a-b)
- Solutions: [pdf]
- Homework 8 - Due 10/27/2014 (Note: Monday instead of Wednesday)
- Read Sections 5.1, 5.2, and 5.3
- Section 5.1: 14(b,d), 15(b)
- Section 5.2: 7(a-d), 10(a-b), 15(a-c), 24(a-b), 40(a-c)
- Section 5.3: 8, 13, 18(a-c), 28(a-b)
- Solutions: [pdf]
- Homework 9 - Due 11/12/2014
- Read Sections 6.1, 6.2, and 6.3
- Section 6.1: 8(a-c),13(a-c), 18
- Section 6.2: 6(a-c), 10, 16, 20(a-c), 22(a-d)
- Section 6.3: 15, 21(a,b), 23
- Solutions: [pdf]
- Homework 10 - Due 12/03/2014
- Read Sections 6.4, 7.1, and 7.2
- Extra: [Problem]
- Section 6.4: 2,4,7,10,16,22,24
- Section 7.1: 3 (a-d), 8, 10, 15, 16, 22
- Section 7.2: 3(d), 8, 12, 14, 16
- Solutions: [pdf]
- Homework 11 - Due 12/10/2014
- Read Sections 7.2, 7.3, and 6.3
- Section 7.2: 18, 24
- Section 7.3: 4 (a,b,c), 6, 8, 9, 11, 16
- Section 7.4: 2 (a,b,c), 3(b,c,d), 9 (b,d), 10 (b,d), 11(b), 15(b,d)
- Solutions: [pdf]

# Quizzes

- Quiz 1 - 09/12/2014 (end of class)
- Sections 1.2-1.5, 2.1
- Lectures 1-6
- Homeworks 1 and 2
- Quiz will be closed book and closed note. Remember to show your work.
- Quiz 2 - 10/15/2014 (end of class)
- Sections 3.1-3.3, 4.1-4.3
- Lectures 13-18
- Homeworks 5 and 6
- Quiz will be closed book and closed note. Remember to show your work.
- Quiz 3 - 12/05/2014 (end of class)
- Sections 6.1-6.4 and 7.1-7.2
- Lectures 24-32
- Homeworks 9 and 10
- Quiz will be closed book and closed note. Remember to show your work.

# Final Exam

- Time: Tuesday, December 16, 2014, 10:30 AM - 1:00 PM
- Sections: All
- Lectures: All
- Homeworks: All
- Final Review: 12/12/2014
- Old Midterms: [Practice Final 1] [Practice Final 2]
- Final Exam will be closed book and closed note. Remember to show your work.

# Midterms

- Midterm 1 - 09/26/2014 (in class)
- Sections: 1.2-1.5, 2.1-2.5
- Lectures: 1-11
- Homeworks: 1-4
- Midterm Review: 9/24/2014
- Old Midterms: [Practice Midterm 1] [Practice Midterm 2]
- Midterm will be closed book and closed note. Remember to show your work.
- Midterm 2 - 10/31/2014 (in class)
- Sections: 3.1-3.3, 4.1-4.5, 5.1-5.3, and dynamic programming on shortest path problems
- Lectures: 12-23
- Homeworks: 5-8
- Midterm Review: 10/29/2014
- Old Midterms: [Practice Midterm 1] [Practice Midterm 2]
- Midterm will be closed book and closed note. Remember to show your work.

# Challenge Problems

- Challenge Problem #1 - [pdf]
- Matlab Script files
- Script for running algorithm: [Algorithm Test]
- Sample function for bin update: [Sample Function]
- Do not update the Algorithm Test Script. You should update the sample function with your algorithm. Please email me your sample function and your desired n.
- Leaderboard
- n=8 : (Best Score = 14 - Dakota ) (my best = 14)
- n=16 : (Best Score = 45 - Ryan W.) (my best = 45)
- n=32 : (Best Score = 140 - Ryan W.) (my best = 140)
- n=64 : (Best Score = 420 - Ryan W.) (my best = 420)

# Computer Projects

- Computer Project #3 - Due 12/01/2014 - [Coin Problem] [Space Station]
- Submission: Submit your m-file through D2L by Monday, 12/01/2014 at 5:00 pm. The written report is due Friday, 12/01/2014 in class.
- You can select either project.
- Computer Project #2 - Due 10/13/2014 - [pdf]
- Submission: Submit your m-file through D2L by Monday, 10/13/2014 at 5:00 pm. The written report is due Monday, 10/13/2014 in class.
- Test Files - [zip]
- Computer Project #1 - Due 09/19/2014 - [pdf]