CMPS/MATH 2170: Discrete Mathematics Spring 2019

• Bert Lindenhovius: CMPS-2170-01 and MATH-2170-01
• Nicholas Mattei: CMPS-2170-02 and MATH-2170-02

We will attempt to run these courses in parallel but attendance for lectures and labs must be in the sections for which you have signed up.

# Course Description

This course is an introduction to several areas of mathematics that are particularly useful in computer science. The following topics will be covered:

1. Propositional and predicate logic
2. Set theory
3. Mathematical induction and recursion
4. Number theory
5. Counting
6. Discrete probability
7. Graphs?

# Learning Outcomes

Upon completion of the course, successful students will be able to:

• establish the logical equivalence of two mathematical statements;
• use rules of inference to construct proofs;
• prove theorems using proof by contraposition, proof by contradiction, and mathematical induction;
• understand the definitions and operations of sets, functions, and sequences;
• understand recursive definitions and model with recurrence relations;
• understand basic number theory and its applications in cryptography;
• apply basic counting techniques;
• find the distribution of a discrete random variable;
• understand conditional probability and Bayes' theorem.

# Course Webpage

http://www.nickmattei.net/cmps2170-spring-2019/

# Time, Place, and Instructor

## CMPS-2170-01 and MATH-2170-01

Instructor: Bert Lindenhovius

• Email: alindenh@tulane.edu
• Office: Stanley Thomas 314
• Office Hours: MW 1100 - 1200, and by appointment.

• Lectures: MWF 1000 - 1050 in Stanley Thomas Hall 302
• Labs: R 1400 - 1515 in Norman Mayer Building 118

## CMPS-2170-02 and MATH-2170-02

Instructor: Nicholas Mattei

• Email: nsmattei@tulane.edu
• Office: Stanley Thomas 303E
• Office Hours: MW 1500 - 1600, and by appointment.

• Lectures: MWF 1200 - 1250 in Stanley Thomas Hall 302
• Labs: R 1700 - 1815 in Stanley Thomas Hall 302

Teaching Assistant: Aram Bingham

• Email: abingham@tulane.edu
• Office: Gibson Hall 309E
• Office Hours: WF 1100 - 1200, and by appointment.
• Aram will be instructing both lab times above.

# Schedule

This schedule is subject to change.

 Week Date Topic Link 1 1/14 Course Overview, Propositional Logic (§1.1) Overview Slides 1/16 Propositional Logic 2 (§1.1, 1.2) Logic Slides 1/17 Lab 1: Quiz 1 and Homework 1 Distributed Homework 1 1/18 Propositional Logic 3 (§1.3, 12.2) 2 1/21 MLK - No Class 1/23 Predicate Logic 1 (§1.4) Predicate Logic 1/24 Lab 2: Quiz 2, Homework 1 Collected, Homework 2 Distributed Homework 2 1/25 Predicate Logic 2 (§1.5), Inference 1 (§1.6) Proofs Slides 3 1/28 Inference 2, Proofs 1 (§1.6, 1.7) Bad Proof Techniques 1/30 Proofs 2 (§1.7, 1.8) 1/31 Lab 3: Quiz 3, Homework 2 Collected, Homework 3 Distributed Homework 3 2/1 Proofs 3 (§1.8) 4 2/4 Proofs 4 (§1.8) 2/6 Sets (§2.1) Sets+Functions Slides 2/7 Lab 4: Quiz 4, Homework 3 Collected, Homework 4 Distributed Homework 4 2/8 Sets (§2.1) 5 2/11 Set Operations (§2.2) 2/13 Set Operations / Functions ((§2.2, 2.3) 2/14 Lab 5: Quiz 4, Homework 4 Collected, Homework 5 Distributed Homework 5 2/15 Functions 6 2/18 Functions 2/20 Cardinality 2/21 Lab 6: Quiz 5, Homework 5 Collected, Homework 6 Distributed 2/22 Cardinality 7 2/25 Review for Midterm 2/27 Midterm Exam in Class - Logic, Proofs, Sets 2/28 Lab 7: Homework 7 Collected 3/1 Sequences 8 3/4 Spring Break - No Class 3/6 Spring Break - No Class 3/7 Spring Break - No Class 3/8 Spring Break - No Class 9 3/11 Induction 3/13 Induction 3/14 Lab 8: 3/15 Induction 10 3/18 Strong Induction 3/20 Recursion 3/21 Lab 9: 3/22 Recursion 11 3/25 Division and Primes 3/27 Primes 3/28 Lab 10: 3/29 CGD 12 4/1 Euclid’s Algorithm 4/3 Congruences 4/4 Lab 11: 4/5 Congruences 13 4/8 Counting 4/10 Pigeonhole Principle 4/11 Exam 2: In Lab. 4/12 Permutations and Combinations 14 4/15 Permutations and Combinations 4/17 Intro to Probability 4/18 Lab 12: 4/19 Good Friday - No Class 15 4/22 Easter Monday - No Class 4/24 Independence, Random Variables 4/25 Lab 13: 4/26 Expected Value 16 4/29 Last Class - Review for Midterm 5/4 Final Exam: 1300 - 1700

# Textbook

Kenneth H. Rosen, Discrete Mathematics and Its Applications, 7th edition, McGraw-Hill, 2012. Older editions of the book contain most of the covered material, but not all. Students are responsible for identifying the differences.

• Homework - 30%
• Quizzes - 10%
• Midterm - 25%
• Final Exam - 35%

The weighted average will determine your letter grade roughly as follows: A >= 90%; B >= 80%; C >= 70%; D >= 60%; F < 60% +/- grades will be given for borderline cases.

All grades will be posted on Canvas.

# Attendance

Students are required to attend all classes and labs unless they are ill or prevented from attending by exceptional circumstances and with a valid excuse note. Students are responsible for notifying instructors about absences that result from serious illnesses, injuries, or critical personal problems.  Students with frequent absences will be removed from the course according to university policy.

# Homework

Homework will be assigned in most weeks and will be due at the beginning of Thursday labs. All homework assignments will be posted on the course webpage one week before the due date. You may discuss homework problems with your classmates. However, what you turn in must be your own. You may not read another classmate’s solutions or copy a solution from the web. There will be no late homework allowed. Requests for a homework extension (with a valid reason) must be given to the instructor before the homework is due.

Part of your Homework grade (5%) will be determined by working and presenting problems and homework solutions in the lab sections.

# Labs and Quizzes

Attendance in the labs is required. There will be short quizzes in most of the labs. No make-up quizzes will be allowed, but the two lowest quiz scores will be dropped.

During lab each week we will:

1. Hand in homework that is due that week.
2. Take a short quiz.
3. Ask questions and present problems from the homework.
4. Group time to work on next week’s homework.

Exams

There will be a midterm and a final exam. Both will be closed-book and closed-notes, but you will be allowed to bring a cheat sheet to each exam (one letter page single-sided -- must be hand-written!). The final exam will be comprehensive. Missing an exam will result in a grade of zero. A request for a make-up exam must be given to the instructor prior to the exam date (documentation may be required).