Mathematical Structures for Computer Science

Catalog description

This course covers the following topics: Proof techniques: proof by example, counterexample, contradiction, and induction. Mathematical logic: propositional logic, predicate logic, Boolean algebra, and applications in the design of combinational circuits. Set theory: operations, cardinality, relations, and functions. Discrete probability: sample space, outcomes and events, probability of an event, conditional probability and independent events, probability function, random variables, and expected values. Graph theory: basic and weighted graphs, paths, trees, planar graphs, and graph colorings. Combinatorics: fundamental principle of counting, permutations, combinations, and the pigeonhole principle.