
Upon satisfactory completion of this course, you should be able to:
 Understand, within the framework of the propositional calculus, truth tables, logical equivalence and implication, tautologies and contradictions, rules of inference, how to do logical proofs including direct proofs, indirect proofs, and proofs of implications.
 Know and understand logical predicates and the universal and existential quantifiers, and how to use them to represent English statements of quantity. Students will be able to carry out proofs containing quantified axioms.
 Know basic set definitions, be able to prove elementary properties of sets using formal, set theoretic notions, and be acquainted with infinite sets and their properties. Students will understand “diagonalization arguments” as illustrated by the proof of the noncountability of the real numbers and by the “halting problem.”
 Have basic knowledge of functions, 11 functions, onto functions, and 11 correspondences. Students will be acquainted with sequences and how they are different from sets.
 Understand the concept of BigO, BigOmega and Big Theta (order) complexity, and how to solve runtime problems based on these concepts. Students will understand how to analyze simple algorithms with regard to their runtime complexity.
 Have a solid working knowledge of proof by mathematical induction, and will be comfortable with inductive proofs.
 Understand modular computations, algorithms for computing efficiently with huge numbers, and the theorems that underlie modern cryptography such as Fermat’s Little Theorem. Students will understand how RSA encryption works.
 Understand recursive definitions of sets, strings and sequences, and be able to find closedform solutions to simple recurrence relations, and prove the correctness of such solutions by means of mathematical induction. Students will acquire skill in finding recurrence relations that model a problem and finding recurrence relations based on the closed form of a sequence.
 Understand basic combinatorics, including the rules of product and sum, permutations and combinations with and without “replacement.”
 To be conversant both with ordinary numerical matrices and Boolean matrices, and the various operations that apply to them.
 Comprehend the notion of a binary relations, and the accompanying definitions, expressed in logical formalism, of Reflexive, Irreflexive, Symmetric, Antisymmetric, Asymmetric and Transitive. They will also understand significant kinds of binary relations such as Partial Orders and Hasse Diagrams, and Equivalence Relations and Equivalence Classes. Students will know how to represent relations in matrices, thus allowing them to be computationally processed.
 Have knowledge of elementary graph theory, including formal definitions of graphs using logic, types of graphs including simple graphs, directed graphs, multigraphs and pseudographs; isomorphisms of graphs, adjacency matrix representations of graphs, and incidence matrix representations of graphs. Students will further understand the notions of Euler circuits, Euler paths, Hamiltonian circuits, Hamiltonian paths, and how to compute whether such circuits and paths exist within a graph.
 Understand trees as special types of directed graphs and how to prove properties of trees by means of inductive proofs on the heights of trees.


Required:
Discrete Mathematics and its Applications, 7th Edition. Kenneth Rosen, McGrawHill, 2011.
Hardcover: ISBN10: 0073383090 ISBN: 9780073383095
Paperback: ISBN10: 0071317104 ISBN13: 9780071317108
Optional:
Student Solutions Guide, 7th Edition. Kenneth Rosen, McGrawHill, 2011.
ISBN10: 0077353501
ISBN13: 9780077353506
