Mathematics 501-01
Discrete Mathematics

MWF 3:30-4:35, LS 103

Fall 2017





Professor: Peter Pacheco
Office: Harney 406
Phone: 422-6630
Email: user: peter, domain: usfca.edu
Office Hours: MW 4:45-5:45, F 12-1, and by appointment


Prerequisites: There are no official prerequisites. However, students will be expected to have a working knowledge of both a high-level programming language and the material in a course similar to Precalculus (Math 108).


Course Description: This course is an intensive introduction to algebraic structures, graph theory, combinatorics, and symbolic logic. Topics include logic, proofs, sets, relations, functions, counting, and probability, with an emphasis on applications in computer science.


Text: zyBooks, Discrete Mathematics. You should go to https://learn.zybooks.com, create an account, and enter the code USFCAMath201PachecoFall2017, and subscribe. A subscription is $48, and it will last until Dec 28, 2017.
Class Website: http://cs.usfca.edu/~peter/discrete


Class Mailing List: You can post to the class mailing list by sending email to user math501 in the domain cs.usfca.edu. Note that this will only work from your usfca.edu account.


Coursework and Grades: I will base your final grade on 10 homework assignments, a midterm, and a final exam, weighted as follows.
Homework 10 @ 3.5% each 35%
Midterm 25%
Final Exam 40%
Total 100%
I will assign grades on a straight scale. Roughly, 90-100% is an A, 80-89% is a B, 70-79% is a C, 60-69% is a D, and 0-59% is an F. Averages within 2% of the cutoffs will have a plus or minus. For example, if the cutoff between B's and A's is exactly 90%, then 88-89 will be a B+ and 90-91 will be an A-.


Attendance and Lateness: There is no attendance requirement. However, if you miss a class you will still be responsible for all the material covered, regardless of whether it is covered in the text. If you must be late to class, you should be sure that you do not disrupt class when you come in.


Academic Honesty: As a Jesuit institution committed to cura personalis - the care and education of the whole person - USF has an obligation to foster the values of honesty and integrity. The University requires all the members of the academic community to follow its standards of honesty and integrity. All students are expected to know and follow the University's Honor Code. You can find the full text of the code online at http://www.usfca.edu/fogcutter.
From a practical standpoint it is fine for you to discuss homework with your classmates. Any other collaboration is unacceptable. In particular, copying another person's work is unacceptable. Students who violate these rules will receive an F in the course. Repeat violators may be subject to more severe penalties.


Learning Outcomes: In this course students will learn aspects of logic, set theory, mathematical proof, algorithm analysis, combinatorics, and graph theory. After completing this course, the student will be able to
  1. Analyze a proposition and determine its truth given information on the truth values of its components.
  2. Read various types of proofs and determine their validity.
  3. Construct valid proofs.
  4. Use sets to model fundamental problems in computer science.
  5. Use relations and functions to implement and study various computer operations.
  6. Use algorithm analysis to determine the space- and time-complexity of standard computer algorithms.
  7. Use combinatorics to analyse more complex algorithms.
  8. Use probability theory to analyse algorithms involving randomness.
  9. Use graph theory to model and solve various problems in computer science.
Tentative Course Outline


Week Material
8/22-8/25 Preliminaries. What is discrete math.
8/28-9/1 Basic logic.
Homework 1 due Fri, 9/1.
9/5-9/8 Biconditionals, tautologies, contradictions.
Homework 2 due Fri, 9/8.
9/11-9/15 Sets.
Homework 3 due Fri, 9/15.
9/18-9/22 Quantifiers.
Homework 4 due Fri, 9/22.
9/25-9/29 Methods of proof.
Homework 5 due Fri, 9/29.
10/2-10/6 Counterexamples, existence.
Homework 6 due Fri, 10/6.
10/9-10/13 Mathematical induction.
Midterm, Fri, 10/13.
10/18-10/20 Sequences and series.
Homework 7 due Fri, 10/20.
10/23-10/27 Relations and equivalence relations.
Homework 8 due Fri, 10/27.
10/30-11/3 Functions, cardinality.
Homework 9 due Fri, 11/3.
11/6-11/10 Algorithms and complexity.
Homework 10 due Fri, 11/10.
11/13-11/17 More on algorithms and complexity
Homework 11 due Fri, 11/17.
11/20-11/22 Basic combinatorics.
11/27-12/1 Discrete probability.
Homework 12 due Fri, 12/1.
12/4-12/6 Graphs, shortest path and spanning trees.



File translated from TEX by TTH, version 4.06.
On 22 Aug 2017, 20:05.