Welcome to Math 374! Discrete Mathematics is a beautiful, important, and fascinating subject. This course is designed to give you a broad background in topics such as propositional logic, proof by induction, elementary combinatorics, and asymptotic analysis. The course is designed to be especially useful for students majoring in computer science and related topics.

It is also challenging. Please plan on a lot of hard work; I am here to help you succeed.

Instructor : Frank Thorne, LeConte 317O, thorne [at] math.sc.edu.

Office Hours: M 9:30-10:30, T 2:30-3:30, W 4:00-5:00 (or by appointment).

Learning outcomes:

"Education is what survives when what has been learned has been forgotten." -- B.F. Skinner

Successful students will learn the basics of a variety of topics within discrete mathematics (please see the schedule below for a complete list), with an eye towards their applications in computer science. The course will involve and further develop some proof-writing ability, but this will not be the principal focus of this course.

Text: The required text is Susanna Epp, Discrete Mathematics with Applications, 4th edition.

The campus bookstore has committed to selling the book for $150.00. You should be able to purchase this book for $150.00, although it was not available for this price on the first day of class. I will be in touch once the book is available at this price.

Meeting schedule : MWF, 10:50-11:40 am, Gambrell 152.

Exam schedule :

• Midterm Exam 1: February 18.
• Midterm Exam 2: March 25.
• Final Exam: Monday, May 4 at 9:00 a.m.

Homework and Quizzes : Weekly homework will be assigned but not collected. You are always welcome, and strongly encouraged, to come to office hours or stick around after class, show me your written up solutions to homework problems, and ask whether they are correct.

Each Monday there will be a quiz first thing in class. All quiz questions will come verbatim from the homework. There will be no opportunity to make up missed quizzes; instead, your three lowest quiz scores will be dropped.

Grading :

You will be graded both on correctness and on quality of exposition. The standard is that someone who doesn't know the answer should be able to easily follow your work. Any work that is confusing, ambiguous, or poorly explained will not receive full credit.

You are guaranteed at least the following grades: A for 90%, B+ for 85%, B for 78%, C+ for 72%, C for 64%, and D for 50%.

	% of grade
Quizzes:	15%
Two in-class exams:	25% x 2
Final exam:	35%

The Fine Print:

Make-up policy :

If you have a legitimate conflict with any of the exams it is your responsibility to inform me at least a week before the exam. Otherwise, makeups will only be given in case of emergency.

Calculators :

Calculators will not be needed or allowed for the exams or quizzes.

Attendance : Skipping class is unwise, but no attendance policy will be enforced. You are responsible for all the material covered in all lectures and homework problems, and you must be present in class for a quiz to take it.

Some help resources : Math lab, Private tutors .

Material in the future is a rough guideline. Note that all quizzes are accompanied by solutions.

The schedule:

• 1/12: Introduction.
• 1/14: Ch. 1.1, Introductory set theory.
• 1/16: Ch. 1.2-1.3, Introductory set theory.

  Homework: Ch. 1.1, all; Ch. 1.2, all; Ch. 1.3, 13-20.

  Quiz 1, January 21.

• [1/19: Martin Luther King Holiday and Service Day]
• 1/21: Ch. 2.1, Introduction to Logic.
• 1/23: Ch. 2.2, Conditional statements.

  Homework: Ch. 2.1, all; Ch. 2.2, through 21.

  Quiz 2, January 26.

• 1/26: Ch. 2.2 and 2.3.
• 1/28: Ch. 2.3, Validity of arguments.
• 1/30: Finish Ch. 2.3; brief introduction to Ch. 2.4-2.5.

  Homework: Through the end of Ch. 2.3.

  Quiz 3, February 2.

• 2/2: Ch. 3.1; Logic and quantified statements.
• 2/4: Ch. 3.1; Logic and quantified statements (cont.)
• 2/6: Ch. 3.2; Logic and quantified statements (cont.)

  Homework: Through 3.2.

  Quiz 4, February 9.

• 2/9: Ch. 3.3; Multiple quantifiers.
• 2/11: Ch. 3.3-3.4; Validity of quantified arguments.
• 2/13: Ch. 3.4; Validity of quantified arguments.

  Homework: Through 3.4.

  Quiz 5, February 16.

• 2/16:
• 2/18: Midterm Examination 1.
• 2/20: Ch. 5, Sequences, Induction, and Recursion

  Homework:

• 2/23:
• 2/25:
• 2/27:

  Homework: Ch. 5.1-5.3 (all).

  Quiz 6 (including Second Chance Quiz 6b).

• 3/2:
• 3/4:
• 3/6:

• [3/9: Spring Break.]
• [3/11: Spring Break.]
• [3/13: Spring Break.]

  Homework: Ch. 5.1-5.3, 5.4 (as below).

  Quiz 7.

• 3/16: Ch. 5.6, Defining Sequences Recursively
• 3/18: Ch. 5.7, Solving Recurrence Relations
• 3/20: Ch. 5.4, 5.7, Solving Recurrence Relations

  Homework: 5.4, 1-9. 17-18, but it is okay to use regular induction. 5.6: 1-31, 37, 38, 39, 40; 5.7: 1-15 and 28-40, 18, 21, 25, 43-51.

  Quiz 8.

• 3/23: Ch. 5.9, Structural induction
• 3/25: Ch. 5.9, Review, class notes.
• 3/27: Midterm Examination 2 (exam and solutions, covering all of Chapter 5).

  Homework: None, except as above.

• 3/30: Ch. 9.1, Introduction to counting and probability. (No quiz.)
• 4/1: Ch. 9.1-9.2, Counting and probability.
• 4/3: Ch. 9.2, The multiplication rule.

  Homework: Ch. 9.1-9.2.

  Quiz 9.

• 4/6: Ch. 9.3, Counting disjoint sets. The addition rule.
• 4/8: Ch. 9.3, The Inclusion-Exclusion Principle.
• 4/10: Ch. 9.4, The Pigeonhole Principle.

  Homework: Ch. 9.3-9.4. Ignore proofs, starred problems, and questions asking for recurrence relations.

  Quiz 10.

• 4/13: Ch. 9.4, The Pigeonhole Principle.
• 4/15: Ch. 9.5, 9.7: Counting problems, binomial theorem.
• 4/17: Ch. 9.5, 9.7: Counting problems, binomial theorem.

  Homework: Ch. 9.5, all except 32-38 on the Stirling numbers.

  Quiz 11.

• 4/20: Introduction to graph theory.
• 4/22: Ch. 10.1, Graph theory.
• 4/24: Ch. 10.2, Graph theory.

  Homework: 10.1: 1-9, 17-25; 10.2 (omit 25-27, 32-35); possibly more

  Quiz 12.

• 4/27: Trees and artificial intelligence.
• TBD: Review Session.
• 5/4: Final Exam, 9:00 a.m.