Math 374, Discrete Structures

Discrete Structures - Mathematics 374, Section 1

Frank Thorne - Fall 2017

University of South Carolina

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: Tuesdays 9:00-10:00 and Thursdays 3: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 course will be taught out of Judith Gersting, Mathematical Structures for Computer Science, sixth edition. This is not the most recent edition. As of this writing, inexpensive used copies could be bought at Amazon, AbeBooks, half.com, and elsewhere. The book is also available at the campus bookstore, albeit at an astronomical price. Additional course materials may be chosen from free online sources including the following:

Mathematics for Computer Science, by Lehman, Leigton, and Meyer. Download.
Mathematical Reasoning and Proof, by Sundstrom. Book homepage (with download links).
A Gentle Introduction to the Art of Mathematics, by Fields. Book homepage, with download links (and even source code!)

Another good commercially available book is Epp's Discrete Mathematics with Applications; this has a reputation for being gentler than Gersting. Once again, look for used copies of previous editions on the internet.

Meeting schedule : MWF, 9:40-10:30 am, Gambrell 201.

Exam schedule :

Midterm Exam 1: October 4.
Midterm Exam 2: November 8.
Final Exam: Wednesday, December 13 at 9:00 a.m.

All exams will be held in the usual classroom, and the midterms will be held during class meetings.

Homework and Quizzes :

Homework will generally be due on Fridays, and there will be a quiz on the same material on the homework due dates. Homework assignments consist of three components. Problems labeled do are to be turned in. Problems labeled understand are problems you should know how to do -- most of the quiz and exam questions will be very similar to these problems (and often will be taken from these problems directly). Extra credit problems will reward anyone seeking out an additional challenge.

Late homework will not be accepted, and (except in case of a documented university conflict) makeup quizzes will not be given. Instead, your lowest two quiz scores and homework scores will be dropped.

Extra reward for perfect quizzes: If you earn a perfect score on a quiz, you'll automatically get a perfect score on that week's homework too.

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

Homework: 15%

Quizzes: 15%

Two in-class exams: 20% x 2

Final exam: 30%

Previous course: You may wish to see the course website for the previous time I taught this course, complete with old quizzes and exams (with solutions). This year's course might not cover exactly the same topics, but it will not be too far away.

You can also see Linyuan Lu's course website; he is also teaching Math 374 this term.

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.

Disability accommodations : If you require special accommodations due to a disability, please see the Student Disability Resource Center; they will make recommendations to me and I will follow them. It is your responsibility to inform me of needed accommodations at least a week in advance.

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 : The Math Tutoring Center is available for drop-in help 10:00-4:00, M-F, on the first floor of LeConte. Disclaimer: This is only intended for 100-level math classes. If you go, be aware that tutors might not be familiar with all the 374 subject matter, and they are likely to have never seen Gersting's book.

Private tutors .

Rough schedule of topics:

Formal logic: Gersting, Chapter 1; Sundstrom, Chapter 2.
Induction and recursion: Gersting, Chapter 2; Sundstrom, Chapter 4; LLM, Chapter 5; Fields, Chapter 5.
Sets and counting: Gersting, Chapter 3; Sundstrom, Chapter 5; Fields, Chapters 4 and 7.
Functions and relations: Gersting, Chapter 4.
Introduction to graph theory: Gersting, Chapter 5; LLM, Chapter 12.
Additional topics may be covered as time permits.

Detailed schedule of lectures, homeworks, and exams:

8/25: Introduction.
8/28: 1.1, Statements and Truth Tables.
8/30: 1.1, Statements and Truth Tables.
9/1: 1.2, Propositional Logic.
Homework, due 9/1: Chapter 1.1. Do: 1-3, 8, 9, 13, 17(a-d), 20(c, e, f). Understand: 1-17, 19, 20. Extra Credit: 36.
Quiz 1.
[9/4: Labor Day.]
9/6: 1.2, Propositional Logic.
9/8: 1.3, Quantifiers and Predicates.
Here is a list of equivalences and inference rules. You may print it out and bring it to quizzes and exams to refer to.
Homework, due 9/8: Do: Chapter 1.2: 1, 2, 5, 6, 9, 12-17, 42-45. Understand: Chapter 1.2, all.
Extra credit: Exercise 23, but use only the axioms given in the book.

Quiz 2.
[9/11: Class cancelled due to Hurricane Irma.]
9/13: 1.3, Quantifiers and Predicates.
9/15: 1.4, Predicate logic. (Not to be covered on the exam).
Homework, due 9/15: Do: Chapter 1.3: 1, 3, 5, 8, 10, 14, 15, 17, 21, 22. Understand: Chapter 1.3, all.

Quiz 3.
9/18: 2.1, Introduction to proofs.
9/20: 2.1, Introduction to proofs.
9/22: 2.2, Proofs by induction.
Homework, due 9/22: Do: Chapter 2.1: 1, 2, 3, 5, 7-12, 21-25, 51-53, 56-58.
Understand: Chapter 2.1, all.
Quiz 4.
9/25: 2.2, Proofs by induction.
9/27: 2.2, Proofs by induction.
9/29: 2.4, Recursive Definitions I. (Integer sequences)
Homework, due 9/29: Do: Chapter 2.2: 5-8, 14, 16, 18, 29-33, 43-44.
Understand: Chapter 2.2, all.
Extra Credit: Chapter 2.2, 61.
Quiz 5.
10/2: Questions and Review.
10/4: Midterm Exam 1. Material covered: Above plus 2.4, 1-30. Exam and solutions.
[10/6: No class due to building closure.]
No quiz or homework due this week.
10/9: 2.4, Recursive Definitions II. (Non-numerical examples)
10/11: 2.4; 2.5, Solving Recurrence Relations.
10/13: (No quiz.) 2.5; 2.6, Analysis of Algorithms.
Homework, due Wednesday, October 18 (quiz on same day):
Do: 2.4, 38, 39, 41, 43, 45, 47, 48; 2.5, 1, 3 (*), 5, 8 (*), 12, 19 (*); 2.6, 1, 3, 4, 11, 13.
Understand: As above, plus 2.4, 39-54; 2.5, 1-20, 38-41; 2.6, 1-5, 11-14.
Instructions: For asterisked problems in 2.5, prove your formula by induction; for other problems, this is optional.
Extra Credit: 2.6, 18-21.
10/16: 2.6 continued; Last day to drop without a "WF" grade.
10/18: 3.1, Set theory.
[10/20: Fall Break.]
Quiz 6.
10/23: 3.1; 3.2, Introduction to counting.
10/25: 3.2, More about counting.
10/27: 3.3, Inclusion-Exclusion and pigeonhole.
Homework: Do: 3.1, 4, 7, 10-12, 23, 38; 3.2, 2-12 even.
Understand: Above plus 3.1, 1-13, 22-28, 39-40, 43-46, 50; 3.2, 1-27.
Extra Credit: 3.2, 30.
Quiz 7.
10/30: 3.4, Permutations and combinations I.
11/1: 3.4, Permutations and combinations II.
11/3: 3.4, Permutations and combinations III: Counting with repetition; wrapping up.
Homework: Do: 3.2, 31-51 (they're short!); 3.3, 1, 4, 17, 18, 19; 3.4, 1-18 even, 29-37.
Understand: 3.2, 3.3, 3.4, all.
Quiz 8.
11/6: Review.
11/8: Midterm Exam 2.
11/10: 3.6, Pascal's Triangle.
11/13: 3.5, Probability.
11/15: 3.5, Probability.
11/17: Examples of probability and expected value.
Homework: Do: 3.5, 6-12, 17-24, 53-59.
Understand: 3.5, 1-59.
Extra Credit: 3.5, 62-63.
Quiz 9.
11/20: Examples of probability and expected value.
[11/22: Thanksgiving]
[11/24: Thanksgiving]
Homework: None.
11/27: 5.1, Introduction to graph theory.
11/29: 5.1, Introduction to graph theory.
12/1: 5.2, Introduction to trees.
Homework: Do: 5.1, 2-7, 11-14, 20-22, 24, 26, 27.
Understand: 5.1, 2-34.
Extra Credit: 5.1, 79.
Quiz 10.
12/4: 5.3, Decision trees, searching and sorting.
12/6: 5.4, Huffman codes, the format of ZIP files. (Reference.)
12/8: Last day of class.
Quiz 11.
Homework: Do: 5.2, 1, 2, 19, 32; 5.3, 7-11; 5.4, 2, 4, 5, 8, 13.
Understand: 5.2, 1-21, 32-33, 39; 5.3, 1-20; 5.4, All.
Extra Credit: 5.2, 40.
Final extra credit assignment.
12/13 (W): FINAL EXAM, 9:00-11:30.

	% of grade
Homework:	15%
Quizzes:	15%
Two in-class exams:	20% x 2
Final exam:	30%