| Lecture | Office Hours | ||
| Time: | 1:10-2:00pm MWF | Time: | 11:00am-12:00pm M | 11:00am-12:30pm W | 12:00-12:30pm F | (Or by appointment) |
| Room: | Horticulture 118 | Office: | 416 Carver |
| Teaching Assistants: (Office Hours in Pearson 0145) | Peter Dixon | Zhenbi Hu | tooplark@iastate.edu | zhenbihu@iastate.edu | Office Hours: R 12:00-2:00pm | Office Hours: W 1:30-3:30pm |
Your entire life, you have been presented with a mathematics curriculum that builds you towards one goal: to be a physicist. Really. That is the point of all the geometry, algebra, trigonometry, calculus, differential equations, and even much of linear algebra. This reflects much of the historial roots of mathematics as being developed alongside physics and other sciences. (These days, you could also be an engineer, applying physics to real-life situations.)
However, with the advent of the digital computer, a completely different type of mathematics is necessary! This is the broadly-interpreted field of Discrete Mathematics. It includes topics such as Logic, Sets, Combinatorics, Graph Theory, Discrete Probability, and Number Theory.
Our goal is to introduce you into this very different mathematical landscape. We begin by developing an overly-formal method of proof, so you can be very concrete in how you discover mathematical truths. We then transition to using those proof skills to investigate discrete structures such as sets, graphs, trees, etc. Finally, we will close with some other helpful mathematics such as discrete probability and number theory (very important when investigating randomized behavior or encrypting data).
From the course catalog: Concepts in discrete mathematics as applied to computer science. Logic, proof techniques, set theory, relations, graphs, combinatorics, discrete probability and number theory.
We will pursue these concepts in our own order, with an emphasis in the following areas:
Items marked with '*' will be covered if time permits.
Mathematical writing is hard. Since you must type your homework, you need to learn how to properly type mathematical notation. While you can use Microsoft Word and its Equation Editor, I personally recommend that you use LaTeX. With that in mind, all handouts will be given in both PDF and TeX format.
TeX/LaTeX format is a plain-text file that is "compiled" into a PDF. You can use editors to edit the plain-text file (such as TeX Shop for Mac (will also need Mac TeX)), or TeX Maker for all platforms (Windows users will need MikTeX) or a WYSIWYG editor such as Lyx.
Instead of starting from scratch, it is recommended that you start from one of the supplied TeX files and modify it accordingly, looking at the existing file for hints on how to write your document.
| Name | TeX | Description | |
| Course Syllabus | TeX | The contract for the course, including grading policies. | |
| Logic Cheat Sheet | TeX | This sheet will be provided on any exam that requires use of these rules. | |
| Exam 1 Topics | TeX | Types of problems that may appear on Exam 1. | |
| Functions and Compositions | TeX | A table to complete about types of functions and their compositions. |
Here is a short list of the topics covered in each lecture. See the lecture notes (posted week-by-week, below) for more information on these topics.
| Date | TeX | Reading | Topics | |
| M 01/12 | TeX | Syllabus | Course policies, Introduction to propositional logic | |
| Rosen 1.1 | ||||
| W 01/14 | Rosen 1.2 | Applications of propositional logic | ||
| LLM 1.1, 1.2 | ||||
| F 01/16 | Rosen 1.3 | Propositional equivalences | ||
| LLM 3.1, 3.4, 3.5 | ||||
| Latin Squares and KenKen | ||||
| W 01/21 | TeX | Rosen 1.4, 1.5 | Quantified Boolean statements, nested quantifiers. | |
| LLM 3.6 | ||||
| F 01/23 | Rosen 1.6 | Rules of inference, formal proofs. | ||
| LLM 1.3, 1.4, 1.5 | ||||
| M 01/26 | TeX | Rosen 1.7 | Introduction to proof, Direct Proof, Proof by Contrapositive, Proof by Contradiction. | |
| LLM 1.3, 1.4, 1.5. | ||||
| Ducks 1.4. | ||||
| W 01/28 | Rosen 1.8 | Proof Strategies, Case Analysis. | ||
| LLM 1.5, 1.6, 1.7, 1.8, 1.9 | ||||
| F 01/30 | Rosen Chapter 1 | Chapter 1 Review | ||
| M 02/02 | TeX | Rosen 2.1 | Sets. | |
| LLM 4.1 | ||||
| Ducks 2.1, 2.2 | W 02/04 | Rosen 2.2 | Set operations. | |
| LLM 4.1, 4.4 | ||||
| Ducks 2.2.4 | F 02/06 | Rosen 2.3 | Functions. | |
| LLM 4.3 | ||||
| Ducks 3.1, 3.2 | ||||
| M 02/09 | TeX | Rosen 2.4 | Sequences. | |
| LLM | ||||
| Ducks | W 02/11 | Rosen 5.1 | Mathematical induction. Sums. | |
| LLM | ||||
| Ducks | F 02/13 | Exam 1 | ||
| M 02/16 | TeX | Rosen 5.1, 5.2 | Induction (continued), Strong Induction. | |
| LLM | ||||
| Ducks | W 02/18 | Rosen 5.2 | Exam 1 Discussion, Function handout, Triangulations of Polygons | |
| LLM | ||||
| Ducks | F 02/20 | LLM 5.4 | State machines, Invariant Principle, Monotonicity Principle, Reversibility Principle. | |
| M 02/23 | TeX | LLM 5.4 | State Machines, Greatest Common Divisor Algorithm. | |
| Rosen... | ||||
| Ducks... | W 02/25 | ... | GCD Runtime, Strings, Structural Induction | |
| LLM | ||||
| Ducks | F 02/27 | ... | Canceled. | |
| M 03/02 | TeX | Rosen 5.3, 6.1 | Structural Induction, Basics of Counting. | |
| LLM 10.1 | ||||
| Ducks 10.5 | W 03/04 | Rosen 6.1 | Basics of Counting | |
| LLM 14.8 | ||||
| Ducks 1.5 | F 03/06 | Rosen 6.3 | Permutations and Combinations | |
| LLM 14.3, 14.4 | ||||
| Ducks 6.1-6.5 | ||||
| M 03/09 | TeX | Rosen 6.2 | Pigeonhole Principle | |
| W 03/11 | Rosen 6.4 | Binomial Coefficients and Identities | ||
| LLM 14.8 | ||||
| Ducks 1.5 | F 03/13 | Exam 2 | ||
| M 03/23 | TeX | Rosen 6.5 | Generalized Combinations and Permutations, Stars and Bars | |
| W 03/25 | Rosen 10.1 | Graph Models and Definition of Graphs | ||
| F 03/27 | Rosen 10.2 | Graph Terminology and Types of Graphs | ||
| LLM | ||||
| Ducks | ||||
| M 03/30 | TeX | Rosen 10.2 | Subgraphs, Unions and Disjoint Unions, Matchings | |
| W 04/01 | Rosen 10.2, 10.3 | Matchings of Bipartite Graphs, Representations of Graphs | ||
| F 04/03 | Rosen 10.3, 10.4 | Isomorphism | ||
| LLM | ||||
| Ducks | ||||
| M 04/06 | TeX | Rosen 10.4 | Connectivity | |
| W 04/08 | Rosen 10.7 | Planar graphs | ||
| F 04/10 | Rosen 10.8 | Coloring | ||
| LLM | ||||
| Ducks |
Homework assignments will be due every Thursday, and will cover material from the previous Wednesday, Friday, and Monday lectures.
All homework must be typed and turned in via Blackboard, using PDF! Even if you use Microsoft Word, you should use the "Print to PDF" feature in order to turn in a PDF file. DO NOT TURN IN .doc OR .docx FILES! Failure to follow this policy may result in a score of zero on the assignment.
In addition, there will be one problem completed during the recitation session. These can be hand-written and must be turned in by the end of class. Problems will typically be selected from the recommended homework problems (see lecture notes).
| Name | Problems | Due | Covers | Solutions | ||
| HW01 | TeX | Jan 15 | Course Preliminaries, Propositional Sentences | TeX | ||
| HW02 | TeX | Jan 22 | Compound Propositions, Logic Puzzles, Logical Equivalences | TeX | ||
| HW03 | TeX | Jan 29 | Quantified Boolean Expressions, Proofs using Rules of Inference | TeX | ||
| HW04 | TeX | Feb 05 | Proofs and Proof Methods, Tiling problems. | TeX | ||
| HW05 | TeX | Feb 12 | Sets, Set Operations, Set Identities, Functions. | TeX | ||
| HW06 | TeX | Feb 19 | Sequences, Mathematical Induction. | TeX | ||
| HW07 | TeX | Feb 26 | Sequences and Sums, Strong Induction, State Machines. | TeX | ||
| HW08 | TeX | Mar 8 | State Machines, Structural Induction. | TeX | ||
| HW09 | TeX | Mar 12 | Basics of Counting, Double-Counting. | TeX | ||
| HW10 | TeX | Mar 26 | Counting. | TeX | ||
| HW11 | TeX | Mar 8 | Generalized Combinations, Graphs. |
There will be three in-class exams and one final exam. All exams are located in the regular lecture room. Your final exam score can replace your lowest in-class exam score (and hence no make-up exams will be allowed). The dates are as follows:
| Exam | Date | Covers |
| Exam 1 | February 13th | Propositional Sentences, Compound Propositions, Logic Puzzles, Logical Equivalences, Quantified Boolean Expressions, Proofs using Rules of Inference, Proofs and Proof Methods, Tiling problems, Sets, Set Operations, Functions. |
| Exam 2 | March 13th | Sequences, Mathematical induction, sums, strong induction, state machines (invariance principle, monotonicity principle, reversibility principle), Strings, Structural Induction, Basics of Counting, Pigeonhole Principle, Permutations and Combinations. |
| Exam 3 | April 17th | |
| Final Exam | Wednesday, May 6th | Comprehensive |
| 2:15-4:15pm |
Periodically, I will make videos to give extra examples for things we study in class. Here are some videos to help. All videos will be posted to the StoleeMath Youtube Page.
Also, there are lots of videos online, so I will link a few here that you may enjoy.
To assist learning TeX, all handouts will be available in TeX format as well as PDF.
You may also find the following resources helpful.
Keep in mind that before asking a question about LaTeX, you should first use a Google search for "latex (thing I want to do)".
For example, search "latex table multiple rows" to find out how to make a table cell span multiple rows.
To reach the instructor, send an email to dstolee [at] iastate [dot] edu with "330" somewhere in the subject heading. By placing 330 in the subject heading, it helps me organize the emails so that I can be sure to respond within 2 business days.
Email is a professional, written communication medium and thus what you write in an email is part of the official record. Please treat every email as if it were a graded assignment.
Academic Dishonesty The class will follow Iowa State University's policy on academic dishonesty. Anyone suspected of academic dishonesty will be reported to the Dean of Students Office.
Disability Accommodation Iowa State University complies with the Americans with Disabilities Act and Sect 504 of the Rehabilitation Act. If you have a disability and anticipate needing accommodations in this course, please contact (instructor name) to set up a meeting within the first two weeks of the semester or as soon as you become aware of your need. Before meeting with (instructor name), you will need to obtain a SAAR form with recommendations for accommodations from the Disability Resources Office, located in Room 1076 on the main floor of the Student Services Building. Their telephone number is 515-294-7220 or email disabilityresources@iastate.edu . Retroactive requests for accommodations will not be honored.
Dead Week This class follows the Iowa State University Dead Week policy as noted in section 10.6.4 of the Faculty Handbook.
Harassment and Discrimination Iowa State University strives to maintain our campus as a place of work and study for faculty, staff, and students that is free of all forms of prohibited discrimination and harassment based upon race, ethnicity, sex (including sexual assault), pregnancy, color, religion, national origin, physical or mental disability, age, marital status, sexual orientation, gender identity, genetic information, or status as a U.S. veteran. Any student who has concerns about such behavior should contact his/her instructor, Student Assistance at 515-294-1020 or email dso-sas@iastate.edu, or the Office of Equal Opportunity and Compliance at 515-294-7612.
Religious Accommodation If an academic or work requirement conflicts with your religious practices and/or observances, you may request reasonable accommodations. Your request must be in writing, and your instructor or supervisor will review the request. You or your instructor may also seek assistance from the Dean of Students Office or the Office of Equal Opportunity and Compliance.
Contact Information If you are experiencing, or have experienced, a problem with any of the above issues, email academicissues@iastate.edu.