CS 205: Intro to Discrete Math and Logic

The purpose of this course is to formalize many topics and ways of thinking in computer science that are frequently discussed in rather casual terms. Taking a mathematical approach to these ideas facilitates not only communication, but also understanding (ideally). On an abstract level, this course is about how to think logically, and how to identify and analyze the important parts of a problem to yield confident, correct results. On a more technical level, this course covers a number of mathematical structures and ideas of interest that occur frequently in computer science.

Discrete mathematics has a very different feel and flavor than that of other fields such as calculus, focusing instead on conceptualizing and manipulating discrete objects. These include logical propositions, finite sets, combinations and permutations, and, at a higher level, graphs. These objects are important for modeling and analyzing real-world objects that are of interest programmatically (e.g., computation as functions, relationships as graphs, etc).

Textbook

The usual text for this course is Discrete Mathematics and Its Applications by Kenneth Rosen, the custom edition for Rutgers University. Additional notes may be made available as necessary.

Topics

Logic, Propositional Logic, Predicates and Quantifiers, Applications
Inferences, Proofs
Sets, Set Operations, Applications, Proofs Involving Sets
Induction (Strong/Weak), Proofs Involving
Functions, Boolean Functions, Sequences, Summations
Recursion
Cardinality
Algorithms, Growth and Complexity, Recursive Algorithms
Integers, Representation, Divisibility, Modular Arithmetic
Integer Algorithms
Primes, Greatest Common Divisor
Solving Congruences
State Machines, Turing Machines, Automata

Notes (Coming Soon)

Math as Art
Logic Primer
Set Primer
Induction Notes + Examples
Halting Problem Notes
Diagonal Slash Notes
Algorithm Notes
Diophantine Equations
Things Worth Knowing, Cheat Sheet