Math 114  Discrete Mathematics

• Clark Catalog Math 114 course description: Covers mathematical structures that naturally arise in computer science. Includes elementary logic and set theory, equivalence relations, functions, counting arguments, asymptotic complexity, inductively defined sets, recursion, graphs and trees, Boolean algebra and combinatorial circuits, finite state automata, and diagonalization and countability arguments. Emphasizes proofs and problem solving.

  Prerequisite: One semester of calculus (MATH 120 or 124), or CSCI 120, or permission.

• Course goals.
  • To provide students with a good understanding of the concepts and methods of discrete mathematics, described in detail in the syllabus.
  • To develop the formal methods of logical reasoning by studying symbolic logic in general and logical proofs in discrete mathematics in particular.
  • To introduce and/or review combinatorial principles and discrete mathematical structures that are central to mathematics, computer science, and statistics

• Course objectives. Students will be able to apply the specific concepts and methods described in the syllabus — logic, set theory, sequences and series, number theory, combinatorics, discrete probability, and graph theory. They will be able to solve problems using these various concepts and methods, they will know a number of applications of discrete mathematics, and they will be able to follow logical arguments and develop modest logical arguments. The text and class discussion will introduce the concepts, methods, applications, and logical arguments; students will practice them and solve problems on daily assignments, and they will be tested on quizzes, midterms, and the final.

• Textbook. Discrete Mathematics and its Applications, sixth edition, by Kenneth H. Rosen. (There is a seventh edition, but the sixth edition is widely available and less expensive. We'll use the sixth edition.)

• Course Hours. MWF 11:00-11:50. BP 316. Office hours before and after class.

• Time and study

  Besides the time for classes, you’ll spend time on reading the text, doing the assignments, and studying of for quizzes and tests. That comes to about five to nine hours outside of class on average per week, the actual amount varying from week to week. Here's a summary of a typical semester's 180 hours

  Regular class meetings, 14 weeks, 42 hours
  Reading the text and preparing for class, 5 hours per week, 70 hours
  Doing 28 daily homework assignments, 56 hours
  Meeting in study groups, variable
  Reviewing for midterms and finals, 12 hours

  For more detail about how to study mathematics, see About studying mathematics.

• Assignments & tests. There will be daily homework, occasional quizzes, two tests during the semester, and a two-hour final exam during finals week. You can use a calculator when you take the tests, but the tests are designed so that calculators are not required or even useful. The two test dates are yet to be determined, but one will be in February, the other in the last half of March.

• Course grade. The course grade will be computed as a weighted average:

  2/9 (homework, quizzes, & attendance) + 4/9 (midterm tests) + 3/9 (final exam)

  Although you will get comments on your homework, all that will be recorded and used for the course grade is the number of homework assignments completed. Homework will be collected at the beginning of the hour.

• Communication outside of class. Besides updating this course page, I will sometimes resort to email to update you on office hours and events that require immediate communication. You are welcome to email me, call my office, or stop by my office.

• General policies

  • Class attendance and class participation are obligatory. During the class meetings the text will be supplemented with more rigorous theory and special topics.

  • Cell phones and laptops should be turned off. There may be rare occasions where they be used for class-related purposes, otherwise no texting, no browsing, no email. Cell phones and laptops may not be used during tests.

  • Academic Integrity. Academic integrity is a basic value for all higher learning. Simply expressed, it requires that work presented must be wholly one's own and unique to that course. All direct quotations must be identified by source. Academic integrity can be violated in many ways: for example, by submitting someone else's paper as one's own; cheating on an exam; submitting one paper to more than one class; copying a computer program; altering data in an experiment; or quoting published material without proper citation of references or sources. Attempts to alter an official academic record will also be treated as violations of academic integrity.

    To ensure academic integrity and safeguard students' rights, all suspected violations of academic integrity are reported to the College Board. Such reports must be carefully documented, and students accused of the infraction are notified of the charge. In the case of proven academic dishonesty, the student will receive a sanction, which may range from an F in the assignment or course to suspension or expulsion from the University. The complete academic integrity policy is available with Academic Advising at http://www.clarku.edu/offices/aac/integrity.cfm.

  • Students with Disabilities. Clark University is committed to providing students with documented disabilities equal access to all university programs and facilities. If you have or think you have a disability and require academic accommodations, you must register with the office of Student Accessibility Services (SAS), which is located in room 430 on the fourth floor of Goddard Library. If you are registered with SAS, and qualify for accommodations that you would like to utilize in this course, please request those accommodations through SAS in a timely manner. For more information, see Student Accessibility Services.

  • Faculty Members are Responsible Employees. Faculty members are required by the Office of Civil Rights to report all alleged sexual offenses to the university's Title IX Coordinator, Lynn Levey, llevey@clarku.edu.

    The only exceptions to this reporting responsibility are the community members who have been designated and/or/ trained as "Confidential Sources." This includes the professional staff in Clark's Center for Counseling and Personal Growth including Director Megan Kersting, mkersting@clarku.edu and the medical providers at the Health Center. This also includes Professor James Cordova, jvc.confidential@clarku.edu, Professor Kathy Palm Reed, kpr.confidential@clarku.edu and Professor Andrew Stewart, als.confidential@clarku.edu.

    The Clark faculty believe in providing all students with an educational environment that is free from discrimination. The sexual harassment of students, including sexual violence, interferes with students' right to receive an education free from discrimination and, in the case of sexual violence, is a crime. The Clark faculty is committed to making Clark University a safe and inclusive environment for all.

1 The Foundations: Logic and Proofs

§ 1.1 Logic
§ 1.2 Propositional Equivalences
§ 1.3 Predicates and Quantifiers
§ 1.4 Nested Quantifiers
§ 1.5 Rules of Inference
§ 1.6 Intruduction to Proofs
§ 1.7 Proof Methods and Strategy

Topics in chapter 1: proposition, truth value, negation, logical operators, compound proposition, truth table, disjuction, conjunction, exclusive or, implication, converse, contrapositive, bit, Boolean variable, bit operation, bit string, bitwise operation; tautology, contradiction, contingency, logical equivalnce, propsitional function De Morgan's laws; predicates, existential quantifier, universal quantifier; nested quantifiers, free & bound variables; rules of inference; theorem, conjecture, proof, lemma, corollary, fallacy, circular reasoning (begging the question), vacuous & trivial proof, direct & indirect proof; proof by cases, counterexample.

2 Basic Structures: Sets, Functions, Sequences, and Summations

§ 2.1 Sets
§ 2.2 Set Operations
§ 2.3 Functions
§ 2.4 Sequences and Summations [optional]

Topics in chapter 2: set, axiom, paradox, element, empty set, set equality, subset, finite & infinite set, cardinality, power set,products of sets; union, intersection, disjoint sets, set difference, set complement, symmetric difference, Venn diagrams; function, domain, codomain, image, preimage, range, onto function, 1-1 function, 1-1 correspondence, inverse function, composition, floor, ceiling; sequence, string, summation notation, product notation.

3 The Fundamentals: Algorithms, the Integers, and Matrices

§ 3.1 Algorithms
§ 3.2 The Growth of Functions
§ 3.3 Complexity of Algorithms
§ 3.4 The Integers and Division
§ 3.5 Primes and Greatest Common Divisors
§ 3.6 Integers and Algorithms
§ 3.7 Applications of Number theory [optional]

Topics in chapter 3: algorithm, searching algorithm, linear search algorithm, binary search algorithm, time complexity, space complexity, worst-case time complexity, average-case time complexity; divisibility, prime & composite number, Mersenne prime, greatest common divisor, relatively prime, pairwise relatively prime integers, least common multiple, remainder & modulus, encryption & decryption, binary representation, hexadecimal represention, linear combination, inverse modulo n, linear congruence, pseudoprime, private and public key encryption; Euclidean algorithm.

4 Induction, and Recursion

§ 4.1 Mathematical Induction
§ 4.2 Strong Induction and Well-ordering
§ 4.3 Recursive Definitions and Structural Induction [optional]
§ 4.4 Recursive Algorithms [optional]

Topics in chapter 4: mathematical induction; recursive defined functions, sets, and structures; recursive algorithms; iteration.

5 Counting

§ 5.1 The Basics of Counting
§ 5.2 The Pigeonhole Principle
§ 5.3 Permutations and Combinations
§ 5.4 Binomial Coefficients

Topics in chapter 5: multiplicative and additive priciples of counting, principle of inclusion and exclusion, tree diagrams; basic and generalized pigeonhole principle; permutatations, r-permutations, combinations; binomial coefficients, Pascal's triangle.

6 Discrete Probability

§ 6.1 An Introduction to Discrete Probability
§ 6.2 Probability Theory
§ 6.3 Bayes' Theorem
§ 6.4 Expected Value and Variance

Topics in chapter 6: foundations of probability, frequency interpretation, symmetric situations, outcomes, events, sample space, sum rule, principle of inclusion and exclusion; uniform distribution, conditional probability, indepencence, Bernoulli trials, binomial distribution; definition of expected value, frequency interpretation, random variables, linearity of expectation, indepedent random variables, variance.

8 Relations

§ 8.1 Relations and Their Properties
§ 8.3 Representing Relations
§ 8.4 Closures of Relations
§ 8.5 Equivalence Relations
§ 8.6 Partial Orderings

Topics in chapter 8: binary relation, n-ary relation, symmetry, antisymmetry, reflexivity, transitivity, composition; graphs and relations, incidence matrices; closure of a relation, transitive closure; equivalence relation, equivalance class, partition; partial ordering, lexicographic order, Hasse diagrams.

9 Graphs

§ 9.1 Graphs and Graph Models
§ 9.2 Graph Terminology and Special Types of Graphs

Topics in chapter 9: definition of graphs, vertices (nodes), edges, directed and undirected graphs, applications of graphs; adjacency of vertices, degree (valence), isolated and pendant vertices, the handshaking theorem, complete graphs, cycles, bipartite graphs, local area networks, subgraphs.

1. Wednesday, Jan. 17
   Welcome! Discussion of the course.
   Discuss § 1.1. Introduction to symbolic logic of propositions. Concepts of proposition, truth value, compound proposition, logical operator, truth table, negation, conjunction, disjunction (inclusive and exclusive)
2. Friday, Jan. 19
   Continue discussion of symbolic logic. Concepts of conditional statement (implication), converse, contrapositive, inverse, precedence conventions of logical operators.
3. Monday, Jan. 22
   § 1.1. Exercises due: 1-4, 7, 10, 15, 16, 19, 21.
   Finish § 1.1, begin § 1.2. Propositional equivalences.
4. Wednesday, Jan 24
   § 1.1. Exercises due: 23, 31a-d, 32ace, 54, 62. Answers
   Continue § 1.2. Concepts of tautology, contradiction, contingency, logical equivalence, laws such as De Morgan's laws and distributive laws
5. Friday, Jan 26
   Discuss § 1.3. Predicates and quantifiers. Concepts of predicate (propositional function), universal and existential quantifier. Logical equivalence of propositions involving quantifiers.
6. Monday, Jan. 29
   § 1.2. Exercises due: 1, 2, 5-7, 12, 14, 17, 20, 27, 35, 46, 48, 50. Answers
   Continue § 1.3., Concepts of counterexample, negation and duality for quantified expressions.
   Begin § 1.4 on nested quantifiers. Concepts of scope of a quantifier, double universal quantifiers, double existential quantifiers, mixed quantifiers.
7. Wednesday, Jan 31
   Finish § 1.4: negating nested quantifiers.
   Begin § 1.5. Rules of inference. Concepts of proof, validity, rule of inference, specific rules of inference for propositional logic including modus ponens (the law of detachment), modus tollens, hypothetical syllogism, disjunctive syllogism, conjunction, resolution, etc.
8. Friday, Feb 2
   § 1.3. Exercises due: 1-3, 6, 10, 15-16, 35-36, 52-53. Answers
   More on § 1.5. Rules of inference for predicate logic: universal instantiation and generalization, existential instantiation and generalization.
   Begin § 1.6. Introduction to proofs in mathematics. Theorems, lemmas, and corollaries.
9. Monday, Feb 5
   § 1.4. Exercises due: 4-6, 12-13, 19-20, 23, 27-28, 31-32, 45-46. Answers
   Continue § 1.6. Direct proofs, contrapositives, proofs of universal theorems, vacuous proofs, proof by contradiction, proofs of equivalence, counterexamples.
10. Wednesday, Feb 7
    § 1.5. Exercises due: 1-4, 7-8, 9abc, 10abc, 15, 23. Answers
    Discuss § 1.7. Proof methods and strategy. Proof by cases. Existence proofs and nonconstructive existence proofs. Uniqueness proofs. Forward and backward reasoning. The discovery process. Conjectures.
11. Friday, Feb 9
    § 1.6. Exercises due: 3, 6, 10-11, 39. Answers
    Quiz on sections 1.4 and 1.5. Answers
    Begin Chapter 2. Discuss § 2.1 on sets. Connection to logic. Examples.
12. Monday, Feb 12
    § 1.7. Exercises due: 3, 12, 21-22. Answers
    Continue § 1.1. Venn diagrams, cardinality, infinite sets, power sets, Cartesian products of sets
    Discuss § 2.2. Operations on sets. Union, intersection, etc., and identities relating to them
    Notes on sets
13. Wednesday, Feb 14
    § 2.1. Exercises due: 1-2, 17, 26, 27, 29. Answers
    Discuss § 2.3 on functions. One-to-one function (injection), onto function (surjection), one-to-one correspondence (bijection).
14. Friday, Feb 16
    § 2.2. Exercises due: 1-4, 6-7, 16, 23, 27. 30, 32, 35-36, 38b, 40. Answers
    From § 2.3. Composition and inverse functions. Graphs of functions.
    Discuss § 2.4. Sequences, strings, summation notation, geometric series, product notation.
15. Monday, Feb 19
    § 2.3. Exercises due: 1-5, 8-11, 19, 28-29, 32, 36, 38, 61a. Answers
    Class cancelled
16. Wednesday, Feb 21
    Review for the first midterm
17. Friday, Feb 23
    First midterm on chapter 1 and chapter 2 through § 2.3. You may bring a calculator and a sheet of notes.
    Two versions: First, answers; Second, answers
18. Monday, Feb 26
    § 3.1 Algorithms. Searching algorithms, sorting algorithms, the halting problem
19. Wednesday, Feb 28
    § 3.2 The Growth of Functions. Big-O, big omega, big theta notations.
    Growth of functions.
    § 3.3 Complexity of Algorithms. Time complexity, worst case, average case
20. Friday, March 2
    § 3.1. Exercises due: 2, 11, 12, 16, 19. Answers
    § 3.4 The Integers and Division. Divisibility, modular arithmetic, congruence.
    
    Spring break, March 5 through March 9.
    
    
21. Monday, March 12
    § 3.2. Exercises due: 1-2, 8-9, 19-20, and § 3.3: 5, 7-9. Answers for 3.2, Answers for 3.3
    § 3.5 Primes and Greatest Common Divisors. Fundamental theorem of arithmetic, Euclid's proof of the infinity of primes, Mersenne primes and perfect numbers, the prime number theorem, greatest common divisor (GCD) and least common multiple (LCM), relatively prime numbers
22. Wednesday, March 14
    § 3.4. Exercises due: 1-2, 6-7, 9a-d, 11, 16, 33, and § 3.5: 3-5, 14, 20, 22. Answers for 3.4, Answers for 3.5
    § 3.6 Integers and Algorithms: Base conversion, Efficient algorithm for computing powers, the Euclidean algorithm, the extended Euclidean algorithm, solving single linear congruences.
    Cryptography and the number theory behind it
23. Friday, March 16
    § 3.6. Exercises due: 1-5, 8, 23-24. Answers
    § 4.1: Mathematical induction. Base case, inductive step, inductive hypothesis
24. Monday, March 19.
    § 3.7. Exercises optional: 1abc, 2abc, 6-7, 18-19, 46. Answers
    More on mathematical induction.
25. Wednesday, March 21
    § 4.1. Exercises due: 9, 10, 14, 16, 21. Answers
    § 4.2: strong induction and well-ordering
26. Friday, March 23
    Quiz on §§ 3.2 and 3.5. Answers
    Notes on Combinatorics
    § 5.1. Basic principles of combinatorics. Multiplicative and additive priciples of counting, principle of inclusion and exclusion, tree diagrams. Permutations
27. Monday, March 26
    § 5.2. The Pigeonhole Principle, generalized pigeonhole principle
    § 5.3. Permutations and Combinations. r-permutations, combinations
28. Wednesday, March 28
    § 5.4. Binomial Coefficients. Pascal's triangle
    Introduction to discrete probability.
29. Friday, March 30
    § 5.1. Exercises due: 7-8, 10-12, 16, 23-24, 31, 39, 42. Answers.
    § 5.2. Exercises due: 1-2, 6, 20-21, 30. Answers.
    § 6.1. Basic principles of probability. Uniform finite probability.
30. Monday, April 2
    § 5.3. Exercises due: 1-2, 6, 8, 10, 15, 20ab, 27-28. Answers.
    § 5.4. Exercises due: 2, 4, 12, 31. Answers.
    § 6.2. Probability theory. Conditional probability, independence.
31. Wednesday, April 4
    More on § 6.2. Bernoulli trials, binomial distribution, random variables.
    § 6.3. Bayes' theorem.
32. Friday, April 6
    Review for second midterm on chapters 3 through 5
33. Monday, April 9
    Second midterm on chapters 3 through 5. You may bring a calculator and a sheet of notes. Answers
34. Wednesday, April 11
    § 6.1. Exercises due: 3, 5, 6, 10-12, 25, 30. Answers.
    § 6.4. Expected value.
35. Friday, April 13
    § 6.2. Exercises due: 7, 8, 12, 17, 25, 26, 28. Answers.
    Properties of expected value.
36. Monday, April 16
    § 6.4. Exercises due: 1-6, 12, 16. Answers.
    § 8.1. Relations. Binary relation on a set S as a subset of S², functions as relations. Properties of relations: reflexive, symmetric, transitive, antisymmetric. Operations on relations: union, intersection, difference, composition.
    § 8.3. Representing a relation as a matrix and as a directed graph (digraph).
37. Wednesday, Apr 18
    § 8.5. Equivalence relations, equivalence classes, partitions.
38. Friday, Apr 20
    § 8.1. Exercises due: 4, 10, 17, 24. Answers.
    § 8.3. Exercises due: 1-2, 5-6, 11-12, 18-19, 31-32. Answers.
    § 5.6. Partial orderings (posets), lexicographic order, Hasse diagrams.
39. Monday, Apr 23
    § 9.1 Graphs and Graph Models. Vertices and edges, loops, labels. Simple graphs vs. multigraphs. Directed graphs (digraphs) vs. undirected graphs. Graph models, i.e., applications.
40. Wednesday, Apr 25
    § 8.5. Exercises due: 1-3, 21-23, 26-28. Answers.
    § 8.6. Exercises due: 7, 9-11, 15, 22. Answers.
    § 9.2. Graph terminology and special types of graphs. Adjacency, degree of a vertex, handshaking theorem
41. Friday, Apr 27. Exercises on graph theory.
42. Monday, Apr 30. Review.
43. Thursday, May 3. Alternate final exam, 1:30-3:30
    You may bring a sheet of notes and a calculator to the final.
44. Monday, May 7. Scheduled final exam, 1:30-3:30 BP 316