Department of Mathematics and Statistics

Dan Yasaki

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.)