CSE 240: Logic and Discrete Mathematics for Computer Science, Spring 2006
Lopata 101, Mondays and Wednesdays, 1-2:30pm
This class introduces basics of deductive logic, set theory, proof by
induction, program verification, combinatorics, and finite graphs for
Computer Science applications. The main high-level goals of the class
are
- to enable you to write (and read) rigorous informal proofs. This
is important for the more theoretical aspects of later CS classes. It
will also help improve your ability to reason about the correctness of
code you write.
- to help improve your ability to translate (in your head) back and
forth from formally to informally expressed constructions. We will
focus on moving between formal and informal formulas and proofs. The
skills are more broadly relevant for CS: code, design documents, etc.,
are often expressed both formally and informally, and it is important
to be comfortable moving from one mode to another.
- to teach the basics of set theory, combinatorics, and finite
graphs. Graphs are critically important in CS (the Internet is a
finite graph, for example). Set theory is the language most often
used to express ideas formally, both in CS and mathematics.
Combinatorics are useful for reasoning about, e.g., complexity of algorithms.
- to introduce some other cool stuff from Computational Logic, an area
of theoretical Computer Science.
Graded work
There are 10 homeworks, a midterm, and a final for the class. The
homeworks are worth 70% of your grade (so 7% each), the midterm is
worth 15% and the final is worth 15%. Your lowest homework score that
is at least a 50% will be replaced by your highest homework score.
Textbooks
The required books for the class are Naive Set Theory, by Paul
Halmos; and Introductory Discrete Mathematics, by
V. K. Balakrishnan. These are available in the campus bookstore. In
addition, I am making available lecture notes
on deductive logic, for the first part of the course.
Collaboration policy
You may not collaborate with others on homework. You are free to consult
with the TA or the instructor on assignments.