This course page is obsolete.  I'll prepare a new page next time I teach the course.

Course information

• 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 CSCI120.

• 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

• Syllabus. See the page syllabus.html

• Textbook. Discrete Mathematics and its Applications, sixth edition, by Kenneth H. Rosen. See the webpage at http://www.mhhe.com/math/advmath/rosen/ for more information about the text.

• Course Hours. MWF 10:00-10:50 in room BP 326 (next to the department office).

• Office hours. Semester schedule

• 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 will be during the weeks of Feb. 11 and Mar. 24.

• 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.

• Workload. The expected workload for this course is about six to eight hours per week outside of class, but this will, of course, vary from student to student and from week to week. About two or three hours per class for reading, studying, and homework.

• Classes. Bring your textbook to every class.

  Attendance is required and will be taken at the beginning of the hour on those few days when there is no homework due and no test is given.

• 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 whether or not I'm having office hours. Check my schedule. I'm usually in every day until at least 2:00.

Class notes, quizzes, tests, homework assignments

1. Monday, Jan. 14.
   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. Wednesday, Jan. 16.
   Continue discussion of symbolic logic. Concepts of conditional statement (implication), converse, contrapositive, inverse, precedence conventions of logical operators.
3. Friday, Jan. 18.
   § 1.1. Exercises due: 1-4, 7, 10, 15, 16, 19, 21, 23, 31a-d, 32ace, 54, 62.
   Discuss § 1.2. Propositional equivalences. Concepts of tautology, contradiction, contingency, logical equivalence, laws such as De Morgan's and distributive.
4. Monday, Jan. 21. No class. Martin Luther King Day.
5. Wednesday. Jan. 23.
   Discuss § 1.3. Predicates and quantifiers. Concepts of predicate (propositional function), universal and existential quantifier.
6. Friday, Jan. 25.
   § 1.2. Exercises due: 1, 2, 5-7, 12, 14, 17, 20, 27, 35, 46, 48, 50.
   Continue § 1.3., Concepts of counterexample, negation and duality for quantified expressions.
7. Monday, Jan. 28.
   Discuss § 1.4. Nested quantifiers. Concepts of scope of a quantifier, double universal quantifiers, double existential quantifiers, mixed quantifiers, negation of nested quantifiers.
8. Wednesday, Jan. 30.
   § 1.3. Exercises due: 1-3, 6, 10, 15-16, 35-36, 52-53.
   Discuss § 1.5. Rules of inference. Concepts of proof, rule of inference, specific rules of inference such as disjunctive syllogism, conjunction, resolution, etc.
9. Friday, Feb. 1.
   § 1.4. Exercises due: 4-6, 12-13, 19-20, 23, 27-28, 31-32, 45-46.
   Discuss § 1.6. Introduction to proofs in mathematics.
10. Monday, Feb.4.
    § 1.5. Exercises due: 1-4, 7-8, 9abc, 10abc, 15, 23.
    Discuss § 1.7. Proof methods and strategy.
11. Wednesday, Feb 6. Notes.
    Discuss §§ 2.1 and 2.2. Sets and their operations.
    § 1.6. Exercises due: 3, 6, 10-11, 39.
12. Friday, Feb. 8.
    § 1.7. Exercises due: 3, 12, 21-22.
13. Monday, Feb. 11. No class.
14. Wednesday, Feb. 13. Review of chapter 1.
15. Friday, Feb. 15.
    Discuss constructions on sets: products of sets and power sets; functions.
    § 2.1. Exercises due: 1-2, 17, 26, 27, 29.
16. Monday, Feb. 18. Sequences, strings, summation notation, geometric series, product notation.
    § 2.2. Exercises due: 1-4, 6-7, 16, 23, 27. 30, 32, 35-36, 38b, 40.
    First test, on chapter 1. Evening 6:30-9:00. Answers. (Postponed from last week.) You may bring a calculator and a sheet of notes.
17. Wednesday, Feb. 20. Introduction to algorithms.
18. Friday, Feb. 22. More on algorithms.
19. Monday, Feb. 25. Growth of functions.
    § 2.3. Exercises due: 1-5, 8-11, 19, 28-29, 32, 36, 38, 61a.
20. Wednesday, Feb. 27. Complexity of algorithms.
    § 2.4. Exercises due: 1-4, 5a-e, 7-8, 13-14, 23-24, 27-28, 31, 40.
21. Friday, Feb. 29.
    § 3.1. Exercises due: 2, 11, 12, 16, 19.
    § 3.2. Exercises 1-2, 8-9, 19-20.
22. March 3-7, midterm break.
23. Monday, Mar. 10. Integers and division. Primes and greatest common divisors.
24. Wednesday, Mar. 12. Primes and greatest common divisors.
    Quiz on § 3.2.
    § 3.3. Exercises due: 5, 7-9.
25. Friday, Mar. 14. Integers and algorithms.
    § 3.4. Exercises due: 1-2, 6-7, 9a-d, 11, 16, 33.
    § 3.5. Exercises due: 3-5, 14, 20, 22.
26. Monday, Mar. 17. Efficient algorithm for computing powers, the Euclidean algorithm, the extended Euclidean algorithm, solving single linear congruences.
27. Wednesday, Mar. 19. Chinese remainder theorem, Fermat's little theorem, pseudoprimes.
    § 3.6. Exercises due: 1-5, 8, 23-24, 32, 38.
28. Friday, Mar. 21. Public key crypotgraphy and the RSA cryptosystem.
    Notes on cryptography.
29. Monday, Mar. 24.
    § 3.7. Exercises due: 1abc, 2abc, 6-7, 18-19, 46.
30. Wednesday, Mar. 26. Mathematical induction.
31. Friday, Mar. 28. Review
    § 4.1. Exercises due: 9, 10, 14, 16, 21.
32. Monday, Mar. 31.
    Second test, on chapters 2 and 3. Answers. -->
33. Wednesday, Apr. 2.; Recursive defined functions, sets, and structures.
34. Friday, Apr. 4.; Recursive algorithms.
    § 4.3. Exercises due: 1-3, 5, 7-9, 12, 34-35.
35. Monday, Apr. 7. Basic principles of combinatorics.
36. Wednesday, Apr. 9. Pigeonhole principle, full permutations.
    § 4.4. Exercises due: 5, 15, 44-46.
37. Friday, Apr. 11. Partial permutation, combinations, binomial coefficients. Notes on Combinatorics
    § 5.1. Exercises due: 7-8, 10-12, 16, 23-24, 31, 39, 42.
38. Monday, Apr. 14. More on binomial coefficients and Pascal's triangle.
    § 5.2. Exercises due: 1-2, 6, 20-21, 30.
39. Wednesday, Apr. 16. Introduction to discrete probability.
    § 5.3. Exercises due: 1-2, 6, 8, 10, 15, 20ab, 27-28.
40. Friday, Apr. 18. Basic principles of probability.
    § 5.4. Exercises due: 2, 4, 12, 31.
41. Monday, Apr. 21.
    § 6.1. Exercises due: 3, 5, 6, 10-12, 25, 30.
    § 6.2. Exercises due: 7, 8, 12, 17, 25, 26, 28.
42. Wednesday, Apr. 23. Expectation and variance.
43. Friday, Apr. 25.
    § 6.4. Exercises due: 1-6, 12, 16.
44. Monday, Apr. 28. Last meeting.
45. Final Exam

Interesting pages on the web

• Math Achives http://archives.math.utk.edu/ links to pages on discrete mathematics http://archives.math.utk.edu/topics/discreteMath.html, logic and set theory http://archives.math.utk.edu/topics/logic.html, and combinatorics http://archives.math.utk.edu/topics/combinatorics.html
• Math Forum's Internet resources for discrete mathematics http://mathforum.org/discrete/discrete.html
• Robin Whitty's Theorem of the Day http://www.theoremoftheday.org/

This page is located on the web at

http://aleph0.clarku.edu/~djoyce/ma114/

David E. Joyce