Discrete Structures

Welcome to Discrete Structures! Our texts will be my notes, together with other material available online.

Click here for printer/mobile device-friendly version

Discrete Structures

Complete only these tasks before our first class:

* Watch this video: Welcome!
* How to be a student in a flipped classroom (about 11 minutes - our class will not be entirely flipped, but enough that this is worth watching).
* Read the Carthage Mask and Vaccination Policy.

You do not need to do an of the assignments outside of this box until after our first class.

1/6: These exercises are due on 1/7. (Yes, they are due tomorrow at the beginning of class, before I take questions over the assignment. Have them ready to turn in when you enter the classroom!) FINALIZED (Never start on an assignment that isn't FINALIZED. I may change it!)

* DO THIS BEFORE OUR NEXT CLASS: Read Chapter 0 in the text. This is an important part of your assignment. Highlight items that you believe could be useful in the future. You are responsible for knowing the information contained in Chapter 0.
* DO THIS BEFORE OUR NEXT CLASS: Read Section 1.1 in the text
* DO THIS BEFORE OUR NEXT CLASS: Re-read your class notes from the worksheet.
* DO THIS BEFORE OUR NEXT CLASS: Do exercises 2acd, 3, 7 from Section 1.1 in the notes. These exercises will be collected at the beginning of our next class on Friday. They should be written neatly on a piece of paper that can be turned in, not in your notes.
* DO THIS BEFORE OUR NEXT CLASS: If you haven't done this already for another class, create your account on user.wolfram.com using your Carthage email address. If you already have an account, make sure that you remember your password. If you don't have a user.wolfram account, you can create one here with your Carthage e-mail address.
* DO THIS BEFORE OUR NEXT CLASS: I am willing to print copies of the notes handout for you if you wish, but I don't want to waste piles of paper printing handouts for folks who don't want them. Please complete this Google form. I will be checking at around 7:30 am, so if you answer "Yes" after 7:30 I might not have a copy ready for you.
* Check the blog for new entries. Even if I fail to put this in your assignment, it would be a good idea to check the blog at least every other day. As I read your homework or think about how class went, I will post insights and hints in the blog.

* Watch these videos before class on Friday. Take notes while watching the videos, either in the handout. They will prepare you for class.
(1) Factorials
(2) Properties of Functions
(3) Sets
(4) Important Sets

* While you are watching the videos or immediately after watching the videos, take this short quiz. You should take this quiz before our next class starts! If I don't have your response by 9:00 am, your quiz will be counted as late, and your score will be reduced, perhaps to 0. This will count as a quiz. You should also receive an email confirmation so you can check your answers.

The exercises below are due on 1/10.They are due at the beginning of class, before I take questions over the assignment. Have them ready to turn in when you enter the classroom!

* Do exercises 2bef, 6, 8 from Section 1.1 in the text. These exercises will be collected at the beginning of our class on Monday. They should be written neatly on a piece of paper that can be turned in, not in your notes. Turn them in as you enter the classroom or shortly thereafter. Don't wait for me to ask!
* Check the blog for new entries.

Optional Material

* If you wish, you can download copies of the following two Discrete Structures texts which I will reference from time to time. Both are available for no cost over the internet, or for a very reasonable price in hard copy.
- The Book of Proof by Hammack
- Discrete Structures in Five Chapters by Witno

* Think about the function \(f(x)=4x(1-x)\) with \(D=T=[0,1]\). Can you find two points \(a\neq b\) such that \(f(a)=b\) and \(f(b)=a\)?

* For the function \(p(x):=x(k-x)\) with \(p:\mathbb Z \rightarrow \mathbb R\), can you predict the number of elements of the range of \(p\) that are integers and also perfect squares?

Today's VQ for In-Class Use (You can't take the quiz here - take the quiz using the link above.)

1/7: These exercises are due on 1/10. These will prepare you for our next class. - FINALIZED

* Watch these videos before our next class.
(1) Introduction to Iteration
(2) Periodic Points
(3) The Shift Function and Connected Components

* While you are watching the videos or immediately after watching the videos, take this short quiz. You should take this quiz before our next class starts! If I don't have your response by 9:00 am, your quiz will be counted as late, and your score will be reduced, perhaps to 0. This will count as a quiz. You should also receive an email confirmation so you can check your answers.

These exercises are due on 1/11. They are due at the beginning of class, before I take questions over the assignment. Turn them in when you enter the classroom!

* Do Exercises 4 and 5 from Section 1.1 in the notes.
* Read Section 1.2 in the text.
* Re-read the in-class worksheet for Section 1.2.
* Do exercises 1, 3, 4, 5, 6 from Section 1.2 in the notes.

Optional Material

* Can a rectangle have a square gnomom? Under what conditions?
* Can a rectangle have a gnomon that is a scaled-down version of the original rectangle? Under what conditions?

Today's VQ for In-Class Use (take the quiz at the link above)


Week 2

1/10: These exercises are due on 1/11. These will prepare you for our next class. - FINALIZED

* Watch these videos before our next class.
(1) Propositions
(2) Compound Propositions
(3) Basic Set Operations
(4) Two More Definitions

* While you are watching the videos or immediately after watching the videos, take this short quiz. You should take this quiz before our next class starts! If I don't have your response by 9:00 am, your quiz will be counted as late, and your score will be reduced, perhaps to 0. This will count as a quiz. You should also receive an email confirmation so you can check your answers.

The exercises assigned today are due on 1/12. You can generate circle graphs at this link, once you log in to your user.wolfram (Mathematica) account. Here is a Mathematica file that you can download and run, or run in Mathematica online. Here is a file that works on older versions of Mathematica.

* Do Exercises 2, 7, 8 from Section 1.2 in the notes.
* Use Exercise 3 from Section 1.2 to prove that \(f:\mathbb R\rightarrow\mathbb R\) by \(f(x)=15x+8\) is one-to-one. Do not prove this directly using the definition! You must use Exercise 3. Make sure that all of the assumptions of the exercise are satisfied.
* Read Section 1.3 in the text.
* Re-read the in-class worksheet for Section 1.3.
* Do exercises 1, 2, 4, 8, 11 from Section 1.3.
* Read Section 1.4 in the text.
* Re-read the in-class worksheet from Section 1.4.
* Do exercises 1, 2, 4, 8 from Section 1.4.

Optional Material

* Think about the function \(f(x)=4x(1-x)\) with \(D=T=[0,1]\). Can you find and points of least period 2? Least period 3? Least period 4? What about for the function \(f(x)=5x(1-x)\) with \(D=T=\mathbb R\)? You could also try \(f(x)=3.3x(1-x)\) with \(D=T=[0,1]\).

* For a circle graph with \(n\) vertices, can you predict the number of connected components in the graph of \(f^k\)?

Today's VQ for Class Use

1/11: These exercises are due on 1/12. These will prepare you for our next class. - FINALIZED

* Watch these videos before our next class.
(1) Quantifiers and Propositional Functions
(2) The Multiplication Principle
(3) The Addition Principle
(4) The Inclusion-Exclusion Principle

* While you are watching the videos or immediately after watching the videos, take this short quiz. You should take this quiz before our next class starts! If I don't have your response by 9:00 am, your quiz will be counted as late, and your score will be reduced, perhaps to 0. This will count as a quiz. You should also receive an email confirmation so you can check your answers.

The exercises assigned today are due on 1/13.

* Do Exercises 5, 10, 12 from 1.3 in the text.
* Do exercises 9, 11 from Section 1.4.
* Read Section 1.5 in the text.
* Re-read the in-class worksheet from Section 1.5.
* Do exercises 7ace and 8ab from Section 1.5.
* Read Section 1.6 in the text.
* Re-read the in-class worksheet from Section 1.6.
* Do exercises 1, 6 from Section 1.6.

Optional Material

* Good advice in Discrete Structures.
* Graph Paper to use if you wish for logic exercises.

Today's VQ for Class Use

1/12: These exercises are due on 1/13. These will prepare you for our next class. FINALIZED

* Watch these videos before our next class.
(1) Truth Table Proofs
(2) Using a Spreadsheet
(3) Proofs of Argument Forms
(4) Making a Bijection
(5) The Set \(\mathbb N\) is Not Finite

* While you are watching the videos or immediately after watching the videos, take this short quiz. You should take this quiz before our next class starts! If I don't have your response by 9:00 am, your quiz will be counted as late, and your score will be reduced, perhaps to 0. This will count as a quiz. You should also receive an email confirmation so you can check your answers.

The exercises assigned today are due on 1/14.

* Do exercises 3 and 13 from Section 1.3.
* Do exercises 2, 4 from Section 1.6.
* Read Section 1.7 in the text.
* Re-read the in-class worksheet from Section 1.7.
* Do exercises 1ace, 2ace from Section 1.7.
* Read Section 1.8 in the text.
* Re-read the in-class worksheet from Section 1.8
* Do exercises 1bcd, 3, 5, 6, 8, from Section 1.8.

Optional Material

* I finished the problems on the handout and scanned them in. See the Help Page for the link.

Today's VQ for Class Use

1/13: These exercises are due on 1/14. These will prepare you for our next class.

* Watch these videos before our next class.
(1) The First Nine Rules
(2) Which Rule Was Used?
(3) Filling in the Rules
(4) Writing a Proof

* While you are watching the videos or immediately after watching the videos, take this short quiz. You should take this quiz before our next class starts! If I don't have your response by 9:00 am, your quiz will be counted as late, and your score will be reduced, perhaps to 0. This will count as a quiz. You should also receive an email confirmation so you can check your answers.

The exercises assigned today are due on 1/17.

* Do exercises 6 and 14 from Section 1.3
* Do exercises 1bde, 2bde from Section 1.7.
* Do exercises 2, 4, 9 from Section 1.8.
* Read Section 2.1 in the text.
* Re-read the in-class handout over Section 2.1.
* Do exercise 1 from Section 2.1 as follows. If your last name begins with the letters A-K, prove logic rules Disjunctive Syllogism, Constructive Dilemma, Conjunction, and Double Negation. If your last name begins with the letters L-Z, prove logic rules Destructive Dilemma, Simplification, Addition, and Tautology (both parts).
* Read Section 1.9 in the text.
* Re-read the in-class handout over Section 1.9.
* Do exercises 1abg from Section 1.9.

* Proofs of the 19 rules.

Optional Material

* Think about infinity.

Today's VQ for Class Use

1/14: Exam 1 will be given today. It will cover the material from in-class work on 1/6-1/12. That includes Sections 1.1, 1.2, 1.3, 1.4, 1.5, 1.6, 1.7, and 1.8. Expect to work for around 45 minutes, maybe less. The exam will be open book and open notes. All of you are expected to be in class to take the exam unless you are ill or in COVID quarantine. If I have not given you permission to take the exam remotely, you should be in class! If you did not receive an email from me, you should be in class for the exam.

For those taking the exam online, the exam will open just before 9:00 am and be open for around 45 minutes. If your answers are not submitted by 10:00 am today, your score will be significantly reduced, perhaps to zero.

This is an exam, and whether you are taking the exam in class or elsewhere, you should not do anything that you would not do if you were taking the exam in class in person. You may use anything on my website www.marksnavely.us, including the text . However, do not stray from my website!

You are not permitted to communicate with any human being by any means, including but not limited to, talking, phone conversations, text messages, email messages, hand signals, smoke signals, semaphore, Morse code, Norse code (used to communicate with vikings), social media, antisocial media, or any other means that I've omitted. You are not permitted to use any other internet resource whatsoever. You are not permitted to use any text other than mine, any app on your phone, any app that's not on your phone, Google, WolframAlpha, or any other print or internet resource that I've omitted.

These exercises are due on 1/17. These will prepare you for our next class. FINALIZED

* Watch these videos before our next class.
(1) Rules of Replacement
(2) Applying the Rules
(3) Definition of Divides
(4) Types of Proofs

* While you are watching the videos or immediately after watching the videos, take this short quiz. You should take this quiz before our next class starts! If I don't have your response by 9:00 am, your quiz will be counted as late, and your score will be reduced, perhaps to 0. This will count as a quiz. You should also receive an email confirmation so you can check your answers.

The exercises assigned today are due on 1/18.

* Do exercise 2 from Section 2.1.
* Read Section 2.2 in the text.
* Re-read the in-class handout from Section 2.2.
* Do exercises 1, 2, 3abcd from Section 2.2. (If you have trouble with problem 1, don't try problem 2! Ask for help in office hours or on the blog. If you have a lot of trouble with problem 2 (having a few problems isn't a big deal), don't move on to problem 3! Ask for help.)

Optional Material

* You do not have to memorize the logic rules, but I recommend that you study them in detail so you know what they say. It's hard to figure out what rule to use if you're not very familiar with them.

Today's VQ for Class Use


Week 3

1/17: These exercises are due on 1/18. These will prepare you for our next class. FINALIZED

* Watch these videos before our next class.
(1) Induction, Part I
(2) Induction, Part II
(3) An Example of an Induction Proof
(4) The Word Graph
(5) Important Graphs
* While you are watching the videos or immediately after watching the videos, take this short quiz. You should take this quiz before our next class starts! If I don't have your response by 9:00 am, your quiz will be counted as late, and your score will be reduced, perhaps to 0. This will count as a quiz. You should also receive an email confirmation so you can check your answers.

The exercises assigned today are due on 1/19.

* Do exercises 3efghi from Section 2.2 in the text. (If you can't finish the proof, take a few legal steps!)
* Read Section 2.3 in the text.
* Re-read the in class handout and your notes from Section 2.3.
* Do exercises 1 and 2 from Section 2.3 in the text. (If you have trouble with problem 1, don't try problem 2! Ask for help in office hours or on the blog. If you have a lot of trouble with problem 2 (having a few problems isn't a big deal), don't move on to problem 3! Ask for help.)
* Do exercises 3a-d from Section 2.3 in the text. (If you can't finish the proof, take a few legal steps!)
* Read Section 3.1 in the text.
* Re-read the in class handout and your notes from Section 3.1.
* Do exercises 1, 3, 7, 9, 10 from Section 3.1 in the text. TYPE YOUR PROOFS FOR EXERCISES 1 AND 3! Your proofs for Exercises 7, 9, and 10 should also be written using complete sentences with correct punctuation. (You could type them all...)

Optional Material

* Nothing today.

Today's VQ for Class Use

1/18: These exercises are due on 1/19. These will prepare you for our next class. Use this link to see a file that shows you how to make graphs in Mathematica. FINALIZED

* Watch these videos before our next class.
(1) Conditional Proof

* While you are watching the videos or immediately after watching the videos, take this short quiz. You should take this quiz before our next class starts! If I don't have your response by 9:00 am, your quiz will be counted as late, and your score will be reduced, perhaps to 0. This will count as a quiz. You should also receive an email confirmation so you can check your answers.

The exercises assigned today are due on 1/20. (This assignment may change significantly depending on how class goes today.)

* Do exercises 3efg from Section 2.3 in the notes. (If you can't finish the proof, take a few legal steps!)
* Read Section 3.2 in the text.
* Re-read the in class handout and your notes from Section 3.2.
* Do exercises 1adfj from Section 3.2 in the text. TYPE at least one of these problems, maybe all of them. Cut and paste is a wonderful tool!
* Read Section 5.1 in the text.
* Re-read the in class handout and your notes from Section 5.1.
* Do exercises 1, 3, 8aceg, 9aceg at the end Section 5.1 in the notes.

Optional Material

* Nothing yet

Today's VQ for Class Use

1/19: These exercises are due on 1/20. These will prepare you for our next class. FINALIZED

* Watch these videos before our next class.
(1) The Division Algorithm
(2) Addition Modulo \(p\)
(3) Paths, Circuits, and Cycles
(4) Euler Circuits and Hamiltonian Cycles
* While you are watching the videos or immediately after watching the videos, take this short quiz. You should take this quiz before our next class starts! If I don't have your response by 9:00 am, your quiz will be counted as late, and your score will be reduced, perhaps to 0. This will count as a quiz. You should also receive an email confirmation so you can check your answers.

The exercises assigned today are due on 1/21.

* Do exercises 3jm from Section 2.3 in the notes. (If you can't finish the proof, take a few legal steps!)
* Do exercises 1ch, 6 and 7 from Section 3.2 in the notes. TYPE at least one part of question 1, and either 6 or 7. Any problems that are not typed should be written very neatly using complete sentences.
* Do exercises 4,7, 8bdf, 9bdf at the end Section 5.1 in the notes.
* Read this proof of how a contradiction can imply anything!
* Read Section 2.4 in the text.
* Do all of the exercises from Section 2.4 that were not done in class, or at least do problem 1-9.

Optional Material

* You may do Exercises 3q and 3s from Section 2.3 for a small amount of extra credit. Correct solutions need to be received by January 27 at 9:00. You may NOT use the method of conditional proof on these extra credit problems!
* An application of graph theory

Today's VQ for Class Use

1/20: These exercises are due on 1/21. These will prepare you for our next class. FINALIZED

* Watch these videos before our next class.
(1) Permutations
(2) Combinations

* While you are watching the videos or immediately after watching the videos, take this short quiz. You should take this quiz before our next class starts! If I don't have your response by 9:00 am, your quiz will be counted as late, and your score will be reduced, perhaps to 0. This will count as a quiz. You should also receive an email confirmation so you can check your answers.

The exercises assigned today are due on 1/24.

* Do exercises 9 and 10 from Section 3.2 in the notes. TYPE at least one of these exercises.
* Read Section 3.3 in the text.
* Re-read your in-class worksheet from Section 3.3.
* Do exercises 1, 2, 4 from Section 3.3. You may use the Mathematica code for constructing the zero-divisor graphs.a
* Read Section 5.2 in the text.
* Re-read your in-class worksheet from Section 5.2.
* Do exercises 3, 4, 5, 6, 7, 8 from Section 5.2.

Optional Material

* Zero Divisor Graphs Explore these! Can you find patterns? Can you determine when a zero-divisor graph will be bipartite?

* Multiplication Tables

Today's VQ for Class Use

1/21: Exam 2 will be given today. It will cover the material from in-class work on 1/13-1/19 except for induction proofs. That includes Sections 1.3, 1.7, 1.8, 1.9, 2.1, 2.2, 2.3, 2.4, 3.1, and 5.1. Expect to work for around 60 minutes, but no more than 75 minutes. (The quiz isn't any longer, but some of you may get stuck on the logic proof(s).) The exam will be open book and open notes. All of you are expected to be in class to take the exam unless you are ill or in COVID quarantine. If I have not given you permission to take the exam remotely, you should be in class! If you did not receive an email from me, you should be in class for the exam.

For those taking the exam online, the exam will open just before 9:00 am and be open for around 75 minutes. If your answers are not submitted by 10:30 am today, your score will be significantly reduced, perhaps to zero.

This is an exam, and whether you are taking the exam in class or elsewhere, you should not do anything that you would not do if you were taking the exam in class in person. You may use anything on my website www.marksnavely.us, including the text . However, do not stray from my website!

You are not permitted to communicate with any human being by any means, including but not limited to, talking, phone conversations, text messages, email messages, hand signals, smoke signals, semaphore, Morse code, Force code (used to communicate with Jedi knights), social media, antisocial media, or any other means that I've omitted. You are not permitted to use any other internet resource whatsoever. You are not permitted to use any text other than mine, any app on your phone, any app that's not on your phone, Google, WolframAlpha, or any other print or internet resource that I've omitted.

These exercises are due on 1/24. These will prepare you for our next class. FINALIZED

* Watch these videos before our next class.
(1) The Euclidean Algorithm
(2) The Chart Method
(3) Equivalent Graphs
(4) Planar Graphs

* While you are watching the videos or immediately after watching the videos, take this short quiz. You should take this quiz before our next class starts! If I don't have your response by 9:00 am, your quiz will be counted as late, and your score will be reduced, perhaps to 0. This will count as a quiz. You should also receive an email confirmation so you can check your answers.

The exercises assigned today are due on 1/25.

* Read Section 6.1 in the text.
* Re-read your class notes for Section 6.1
* No written exercises from Section 6.1 today, but you could start the problems that will be assigned on Monday!
* Type a proof of Exercise 1k from Section 3.2. Make it look really good. This is your only written homework assigned today!

Optional Material

* Nothing yet

Today's VQ for Class Use


Week 4

1/24: These exercises are due on 1/25. These will prepare you for our next class. - FINALIZED

* Watch these videos before our next class.
(1) Set Proofs
(2) An Example Proof

* While you are watching the videos or immediately after watching the videos, take this short quiz. You should take this quiz before our next class starts! If I don't have your response by 9:00 am, your quiz will be counted as late, and your score will be reduced, perhaps to 0. This will count as a quiz. You should also receive an email confirmation so you can check your answers.

The exercises assigned today are due on 1/26. (I may need to edit this after class.)

* Do exercises 1-9, 12, 13, 14, 15 from Section 6.1.
* Read Section 3.4 in the text.
* Re-read your notes from Section 3.4.
* Do exercises 1 (using the Euclidean Algorithm!) 2, 8, and 9 from Section 3.4.
* Re-visit Exercises 8-9 from Section 1.4. Using the insights that we have gained and the new concepts that we have explored, particularly modular arithmetic, greatest common divisor, and least common multiple, answer this question: Consider \(f_n\), the circle graph with \(n\) vertices. How many connected components will the graph of \(f_n^k\) have? Can you find one nice, neat formula? (This question will be graded on completion, so give it your best shot.)

Optional Material

* Nothing yet

Today's VQ for Class Use

1/25: These exercises are due on 1/26. These will prepare you for our next class.

* Watch these videos before our next class.
(1) Periodic Points (This is about 10 minutes long, but it's only one video!)

* While you are watching the videos or immediately after watching the videos, take this short quiz. You should take this quiz before our next class starts! If I don't have your response by 9:00 am, your quiz will be counted as late, and your score will be reduced, perhaps to 0. This will count as a quiz. You should also receive an email confirmation so you can check your answers.

The exercises assigned today are due on 1/27.

* Read Section 5.3 in the text.
* Re-read your notes from Section 5.3
* Read Section 4.1 in the text.
* Re-read your class notes from Section 4.1.
* Type proofs for problems 2 and 4 from Section 4.1. These should look like the proofs in the text! Make these look professional.
* Do exercises 2, 5, 7 from Section 5.3.

Optional Material

* Nothing yet

Today's VQ for Class Use

1/26: These exercises are due on 1/27. The Mathematica file for our next class.

No new videos planned, but check back later.

The exercises assigned today are due on 1/28.

*Study for the final exam, which will cover the entire course.

Optional Material

* Don't panic.

1/27: The exercises assigned today are due on 1/28.

*Study for the final exam, which will cover the entire course.

Optional Material

* Nothing yet

1/28: Our final exam is from 9:00-12:00 on Friday, January 28. This exam covers the entire course, except the material covered on January 27. You may start as early as 8:00 if you wish.

* The comprehensive final exam will cover all of the material in the course.

These exercises are due on 1/28. These will prepare you for our next class.

* Watch these videos before our next class.
(1)
* While you are watching the videos or immediately after watching the videos, take this short quiz. You should take this quiz before our next class starts! If I don't have your response by 9:00 am, your quiz will be counted as late, and your score will be reduced, perhaps to 0. This will count as a quiz. You should also receive an email confirmation so you can check your answers.

These exercises are due on 1/29. They are due at the beginning of class, before I take questions over the assignment. Turn them in when you enter the classroom!

* Do

Optional Material

* Nothing yet

Today's VQ for Class Use