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.
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 :
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% |
You can also see Linyuan Lu's course website; he is also teaching Math 374 this term.
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.
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.
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.
Homework, due 9/15: Do: Chapter 1.3: 1, 3, 5, 8, 10, 14, 15, 17, 21, 22. Understand: Chapter 1.3, all.
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.
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.
No quiz or homework due this week.
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.
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.
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.
Homework: Do: 3.5, 6-12, 17-24, 53-59.
Understand: 3.5, 1-59.
Extra Credit: 3.5, 62-63.
Homework: None.
Homework: Do: 5.1, 2-7, 11-14, 20-22, 24, 26, 27.
Understand: 5.1, 2-34.
Extra Credit: 5.1, 79.
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.