Discrete Mathematics/Discrete Structures/CombinatoricsThis is typically a compulsory course in many undergrad CS programs. While most traditional engineering branches are based on ideas of continuous domain mathematics and involve calculus; much of Computer Science is based on Discrete Mathematics. A course in Discrete Mathematics typically covers sets, relations, recurrence relations, number theory, groups, fields, permutations and combinations, complexity etc. Here's a quick look at some of the topics often covered in a Discrete Mathematics course. Propositional logic: Syntax and semantics, valid, satisfiable and unsatisfiable formulas, the validity of some logical arguments.Proof Techniques: Forward proof, proof by contradiction, contrapositive proofs, proof of necessity and sufficiency.Sets, relations and functions: Operations on sets, relations and functions, binary relations, partial ordering relations, equivalence relations, principles of mathematical induction. Size of a set: Finite and infinite sets, countable and uncountable sets, Cantor's diagonal argument and the power set theorem, Schröder-Bernstein theorem. Combinatorics: Basic counting techniques: inclusion and exclusion, pigeon-hole principle, permutation, combination, summations. Introduction to recurrence relations and generating functions. Algebraic structures and morphisms : Algebraic structures with one binary operation - semigroups, monoids and groups, congruence relation and quotient structures. Free and cyclic monoids and groups, permutation groups, substructures, normal subgroups. Algebraic structures with two binary operations - rings, integral domains and fields. Boolean algebra and Boolean ring. Graphs and trees: degree, path, cycle, subgraphs, isomorphism, Eulerian and Hamiltonian walks, graph coloring, planar graphs, trees.Here are some recommended books for studying Discrete Mathematics, in case you'd like to take a look at them on Amazon. Discrete Mathematics |
Computer Science >