About

CENG 115

Discrete Structures

Sets, and Functions, The Fundamentals: Algorithms, the Integers, and Matrices, Methods of Proof, Mathematical Induction, Recursive Definitions, Recursive Algorithms, Program Correctness, Basics of Counting, The Pigeonhole Principle, Permutations and Combinations, Recurrence Relations, Divide-and-Conquer Relations, Inclusion-Exclusion, Relations and Their Properties, n-ary Relations, Representing Relations, Closures of Relations, Equivalence Relations, Partial Orderings, Graph Terminology, Representing Graphs and Graph Isomorphism, Connectivity, Euler and Hamiltonian Paths, Shortest Path Problems, Planar Graphs and Graph Coloring, Tree Traversal, Trees and Sorting, Spanning Trees, Minimum Spanning Trees, Boolean Functions and Their Representations, Minimization, Elements of Computability, Complexity Classes, P – NP – NP Completeness, Space Complexity, Number Conversion, Calculational Logic, Maximum and Minimum, Coding and Constructions.

Topics
Propositional Logic
Predicate Logic
Proof Techniques
Sets and Functions
Sequences and Summations
Algorithms and complexity analysis
Integers, divisibility, and matrices
Mid-term Exam
Induction and recursion
Counting, pigeonhole principle, permutation, and combination
Discrete probability
Recurrences
Relations
Graphs

Instructor(s)

Associate Professor
Other First Year Courses