Derrick Stolee, Assistant Professor
Department of Mathematics
Department of Computer Science
Iowa State University

COM S 330 - Discrete Computational Structures
Course Information
 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
Course Goals

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

Course Topics

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:

1. Logic: Logial statements, truth tables, predicates, propositions, tautologies.
2. Proof Techniques: Rules of inference, direct proofs, proof by contradiction, induction.
3. Sets: Set definitions, set operations, functions and bijections.
4. Relations: binary relations, orders, partial orders.
5. Combinatorics: combinations, permutations, counting, recurrence relations.
6. Graph Theory: graphs, trees, distance, isomorphism.
7. Discrete Probability*: random variables, expected value.
8. Number Theory*: prime numbers, factoring, RSA encryption.

Items marked with '*' will be covered if time permits.

Handouts

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 PDF TeX Description Course Syllabus PDF TeX The contract for the course, including grading policies. Logic Cheat Sheet PDF TeX This sheet will be provided on any exam that requires use of these rules. Exam 1 Topics PDF TeX Types of problems that may appear on Exam 1. Functions and Compositions PDF TeX A table to complete about types of functions and their compositions.
Topic List

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 PDF TeX Reading Topics M 01/12 PDF 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 PDF 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 PDF 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 PDF 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 PDF 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 PDF 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 PDF 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 PDF 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 PDF 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 PDF 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 PDF 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 PDF TeX Rosen 10.4 Connectivity W 04/08 Rosen 10.7 Planar graphs F 04/10 Rosen 10.8 Coloring LLM Ducks
Assignments

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 PDF TeX Jan 15 Course Preliminaries, Propositional Sentences PDF TeX HW02 PDF TeX Jan 22 Compound Propositions, Logic Puzzles, Logical Equivalences PDF TeX HW03 PDF TeX Jan 29 Quantified Boolean Expressions, Proofs using Rules of Inference PDF TeX HW04 PDF TeX Feb 05 Proofs and Proof Methods, Tiling problems. PDF TeX HW05 PDF TeX Feb 12 Sets, Set Operations, Set Identities, Functions. PDF TeX HW06 PDF TeX Feb 19 Sequences, Mathematical Induction. PDF TeX HW07 PDF TeX Feb 26 Sequences and Sums, Strong Induction, State Machines. PDF TeX HW08 PDF TeX Mar 8 State Machines, Structural Induction. PDF TeX HW09 PDF TeX Mar 12 Basics of Counting, Double-Counting. PDF TeX HW10 PDF TeX Mar 26 Counting. PDF TeX HW11 PDF TeX Mar 8 Generalized Combinations, Graphs.
Exams

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
Other Resources

### Video Tutorials

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.

### LaTeX

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.

Contact Information and Email Policy

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.

University Policies

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.