## MAT 253-01 (Discrete Mathematical Structures) Fall 2016

A rigorous introduction to discrete mathematical structures, proof techniques, and programming. Topics include sets, functions, sequences, relations, induction, propositional and predicate logic, modular arithmetic, and mathematical programming.

- Pr. grade of at least C in MAT 151 or MAT 191.

The class meets TR 2:00 - 3:15 pm in Petty 303. The final exam is Saturday, December 10, 2016 at 3:30 am.

All announcements and handouts will be posted on Canvas. Be sure to check your UNCG email regularly.

### Documents (pdf)

### Homework

The exercise list in the course notes on Canvas will be updated as the semester progresses.

Make sure the assignments you turn in are in compliance with the Homework Guidelines for Mathematics.

### Lecture log

**Tuesday, 8/23/2016:** I gave out the syllabus and lectured on 1.1 and
1.2. I will do some more examples before moving on to 1.3 next time, but you should be able to
complete most of the exercises in 1.1. and 1.2. Read 1.1-1.3 for
Thursday. If you plan on using your laptop for the programming
assignments, install Python 3.* from the The official home of
the Python Programming Language, and bring your laptop to class.

**Thursday, 8/25/2016:**I finished 1.2, 1.3, and introduced the programming project. HW 1.1-1.3 are due on Tuesday. P0 is due Thursday. Be sure to keep up with due dates in Canvas. Read 1.4 for Tuesday.

**Tuesday, 8/30/2016:** I lectured on 1.4 and started
1.7. I will continue 1.7 next time, leaving some time for P1. Read 1.7-1.8 for
Thursday. If you plan on using your laptop for the programming
assignments, install Python 3.* from the The official home of
the Python Programming Language, and bring your laptop to class.

**Thursday, 9/01/2016:** I completed 1.7 and showed some
Python to help with P1. The exercises are due Tuesday. I added a
folder to the main Canvas page where I will put solutions and
handouts. Read 2.1 for Tuesday.

**Tuesday, 9/06/2016:** I gave out a proofs sheet and
introduced sets (2.1 and 2.2). I will finish 2.2 next time. Bring
your laptop, as we will cover P2.

**Thursday, 9/08/2016:** I gave out a P2 and finished 2.2.
I will collect 2.2 on Tuesday.

**Tuesday, 9/13/2016:** I finished 2.3. I will lecture
on 2.4 on Thursday. If time permits, I will do some Python on
Thursday as well. The homework 2.3 exercises are due
Thursday. Read 2.4 for Thursday. I updated the shared folder
with more HW solutions and a sample test. Test 1 is next Thursday.

**Thursday, 9/13/2016:** I almost finished 2.4. I will
complete some proofs on Tuesday, then we will review for Test 1. Test
1 is next Thursday.

**Tuesday, 9/20/2016:** I did some proofs about summation
and showed how to define functions in Python. Then we reviewed for Test 1.

**Thursday, 9/22/2016:** Test 1: average 77

**Tuesday, 9/27/2016:** I returned graded tests and
covered 4.1 on divisibility and modular arithmetic.

**Thursday, 9/29/2016:** I finished 4.1 and covered most
of 4.2. You should work on 4.2 exercises, but I will not collect them
on Tuesday. On Tuesday, I will give the algorithm for fast
exponentiation before moving on to 4.3.

**Tuesday, 10/04/2016:**
We finished 4.2 looking at divisibility proofs. Then we went through
the base b expansion and fast exponentiation algorithms in detail.
Sample Python code can be found in the shared folder on Canvas in the
file algorithms.py. I will collect 4.2 on Thursday. The programming
assignment P4 can be submitted on Canvas. Read 4.3 for Thursday.

**Thursday, 10/06/2016:** I covered extended Euclidean
algorithm and Bezout's theorem. I handed out P5. We are slipping a bit behind the
schedule in the syllabus. Continue to remind me to push deadlines.
Read 4.4 for Tuesday.

**Tuesday, 10/11/2016:**
We covered solving linear congruences by computing modular inverses
and Chinese Remainder Theorem. Complete 4.4 for Thursday. Read about
crytpography 4.6 for Thursday.

**Thursday, 10/13/2016:** I covered RSA encryption and
shift ciphers. I handed out P6 and an RSA worksheet. I will collect
4.6 and P6 on Thursday. There is no class on Tuesday because of Fall
break. Read 5.1 for Thursday.

**Thursday, 10/20/2016:** I handed out an RSA problem and
Test 2 study guide today. Both can be found in the shared folder on
Canvas. I covered 5.1 on mathematical induction. I will collect
5.1 on Tuesday. Test 2 is on Thursday, so Tuesday is a review day if
you come in with questions.

**Tuesday, 10/25/2016:** Review for Test 2. Be sure to
bring a calculator that can do arithmetic with 8 digit numbers.

**Thursday, 10/27/2016:**
Test 2. Office hours are cancelled next week. Cliff Smyth will
lecture next Tuesday and Thursday.

**Tuesday, 11/01/2016:**
Cliff Smyth lectured on strong induction and returned graded tests.
Solutions are in the shared folder.

**Thursday, 11/03/2016:**
Cliff Smyth lectured on product and sum rule for counting and gave the
programming assignment.

**Tuesday, 11/08/2016:**
We covered 6.2 on the Pigeonole Principle. Read 6.3 for Thursday.

**Thursday, 11/10/2016:**
We covered 6.3 on permutations and combinations. We learned about
Python loading files and dictionaries. Read 9.1 for Tuesday.

**Tuesday, 11/15/2016:**
We covered 9.1 on relations.
Read 9.5 for Tuesday.

**Thursday, 11/17/2016:**
We covered 9.5 on equivalence relations. The
old test with solutions is in the shared folder. Test 3 is Thursday
after break.

**Tuesday, 11/22/2016:**
Introduction to turtle module in Python for optional programming
assignment. Revew worksheets. Solutions are in the shared folder.
No class Thursday due to Thanksgiving.

**Tuesday, 11/29/2016:**
Review for Test 3.

**Thursday, 12/01/2016:**
Test 3. Covers 5.1, 5.2, 6.1-6.3, 9.1-9.5 and Python.

**Tuesday, 12/06/2016:**
Reading Day. I will hold office hours as scheduled to review for the
final exam. The final exam is Saturday at 3:30 pm.

### Additional resources

- A Guide to Writing Mathematics, by Kevin P. Lee
- How large is 52 factorial? See this Youtube video by Vsauce for a visualization using a description by Scott Czepiel. Skip to around the 14:30 mark if you don't have time to watch the 20 minute video.
**Book of Proof**by Richard Hammock is an introduction to the standard methods of proving mathematical theorems. It has been approved by the American Institute of Mathematics' Open Textbook Initiative.**The Art of Proof**by Matthias Beck and Ross Geoghegan is an excellent introduction to writing good proofs. Go to the UNCG Library Catalog to find this book. You can download a free copy by entering your UNCG information.- Math Help Center: Tutoring is provided on a walk-in first come first serve basis. No appointment is necessary. See the webpage for the schedule.
- Textbook website has tips, advice, additional exercises, and other supplemental information.

**Python**is a great object-oriented, interpreted, and interactive programming language.

- The official home of the Python Programming Language: Downloads, documentation, and more.
- Learn Python the Hard Way: This book instructs you in Python by slowly building and establishing skills through techniques like practice and memorization, then applying them to increasingly difficult problems. By the end of the book you will have the tools needed to begin learning more complex programming topics.
- Non-Programmer's Tutorial for Python 3: The Non-Programmers' Tutorial For Python 3 is a tutorial designed to be an introduction to the Python programming language. This guide is for someone with no programming experience.
- Python 3 Tutorial: This tutorial does not attempt to be comprehensive and cover every single feature, or even every commonly used feature. Instead, it introduces many of Python’s most noteworthy features, and will give you a good idea of the language’s flavor and style. After reading it, you will be able to read and write Python modules and programs, and you will be ready to learn more about the various Python library modules described in The Python Standard Library.
- Python for Non-Programmers: If you've never programmed before, the tutorials on this page are recommended for you; they don't assume that you have previous experience.
- Python for Programmers: The tutorials on this page are aimed at people who have previous experience with other programming languages (C, Perl, Lisp, Visual Basic, etc.).
- The Python Wiki: This Wiki is a community place to gather and organize all things about Python. Feel free to exercise your editorial skills and expertise to make it a useful knowledge base and up-to-date reference on all Python-related topics.
- Codecademy: Online coursework to learn Python. (Note: This is Python 2.7.)