Discrete Structures

The course provides a solid theoretical foundation of discrete structures as they apply to Computer Science problems and structures. The students will learn how to use mathematical notation and solve problems using mathematical tools

Course Contents:

Logic: Propositional Equivalences, Predicates and Quantifiers, Nested Quantifiers, Methods of Proof.
Sets & Functions
Algorithms: the Growth of Functions, Complexity of Algorithms, the Integers and Division, Matrices
Number Theory and Cryptography
Mathematical Reasoning: Proof Strategy, Sequences and Summations,
Mathematical Induction, Recursive Definitions and Structural Induction,
Recursive Algorithms, Program Correctness
The Basics of Counting: The Pigeonhole Principle,
Permutations and Combinations, Binomial Coefficients,
Generalized Permutations and Combinations,
Generating Permutations and Combinations
Advanced Counting Techniques: Recurrence Relations,
Solving Recurrence Relations, Divide-and-Conquer Algorithms and Recurrence Relations,
Generating Functions, Inclusion-Exclusion & its Application
Relations and Their Properties, n-ary Relations and Their Applications,
Representing Relations, Closures of Relations, Equivalence Relations, Partial Orderings
Graph: Representing Graphs and Graph Isomorphism,
Connectivity, Euler and Hamilton Paths, Shortest-Path Problems, Planar Graphs, Graph Coloring
Trees: Applications of Trees, Tree Traversal, Spanning Trees, Minimum Spanning Trees