CSE191, Fall 2013

Discrete Structures

Instructor:

Dr. Kenneth W. Regan

326 Davis

645-4738

Office hours: Mondays, 1--3pm, Thursdays, 1--2:30pm

email

TAs: 1.

Tianle Ma

302 Davis

no phone

Ofc. hrs.: Tue. 2--4pm

email

2.

Michael Wehar

302 Davis

no phone

Ofc, hrs.: Wed. 10--11am, 1 more TBA

email

3.

Tao Wei

302 Davis

no phone

Ofc, hrs.: Wed. 1--2:45pm

email

Printed Syllabus; see also notes below.

Assignment 1, due Friday 9/13 in class. Answer Key.

Assignment 2, due Friday 9/20 in class. Answer Key.

Assignment 3, due Friday 9/27 in class; the longer assignment 4 is due the following Friday 10/4. Answer Key.

Assignment 4 by itself, no change from above, again due Friday 10/4. Answer Key.

Assignment 5, due Friday 10/25. Answer Key (plaintext).

Assignment 6, due Friday 11/1. Answer Key.

Assignment 7, due Friday 11/8. Answer Key (plaintext).

Assignment 8, due Friday 11/15. Answer Key ( plaintext).

Assignment 9 (the last), due Friday 12/6. Answer Key ( plaintext).

Course Description This course teaches fundamental mathematics for understanding computation. As calculus is vital to understanding and engineering analog systems, discrete mathematics is the stuff of digital systems. The course begins with the elements of symbolic logic and set theory, and continues with parts of number theory used for instance in cryptography. Then it covers clever methods of counting---permutations and combinations---and basic discrete structures, such as graphs and trees. The two most important skills that should result from this course, using the ABET accreditation wording, are:

  • Ability to apply knowledge of mathematics, probability and statistics, computer science, and electrical engineering as applied to the fields of computer software and hardware.
  • Ability to communicate technical information in speech, presentation, and writing.

These outcomes will be measured by grades on exams and written homeworks, and participation in recitations and lectures.


Course Resources

Bill Rapaport's CSE191 Page. My syllabus, order of lectures, grading policy, and course organization will be ``similar but a little different.'' For instance, I will have 2 prelim exams in place of one midterm, and the coverage of Chapter 1 (Logic) will be somewhat quicker.

Bill Rapaport's Lecture Calendar---it has online notes in rough parallel with my lectures.

UB Accessibility Resources Office, as discussed in class and in private.


Week I Reading Assignment: Text, up through section 1.6. This will be tied to a quiz in lecture on Friday, Sept. 6. The quiz will be closed-book, closed-notes, 15 minutes.

There is a lot of "FYI" material in the early sections, and I won't "officially cover" them all, though they are useful to read. For example, I've already alluded to the fact that notation like Quarterback(x) is used in "logic programming" and other AI applications---if this helps motivate pages 51-52 then fine as FYI, but coverage of Prolog itself (where it would be "quarterback(X)") is left to CSE305. Particular topics where it's useful to know what they are before my lectures do (more) things with them:

  • Propositional logic has truth values, variables, and operators; binary or multi-ary operators especially are also called connectives.
  • Predicate logic adds the idea of a domain of discourse, elements of that domain, predicates, and quantifiers.
  • When a predicate's variables are (either quantified or) filled in by particular elements, it becomes a sentence.
  • Logical (semantic) equivalence, and its relation to the <--> operator of syntactic equivalence (Wed. 9/4 lecture).
  • De Morgan's Laws and other laws of logical equivalence.
  • Boolean formulas F(x_1,...x_n) can be regarded like predicates whose variables x_i range over the truth values themselves.
  • A Boolean formula is a tautology if every assignment makes it evaluate to true.
  • F is satisfiable if some assignment makes it true, which happens iff NOT(F) is not a tautology.
  • Quantifiers and domains---note that I felt it important to introduce the idea of domains like "people" and "objects" ahead of time.
  • Logical equivalences with quantifiers---OK these are tricky so not on the quiz.
  • Modus ponens and the idea of a "fallacy"--these are the only parts of sections 1.5--1.6 that might be on the quiz.