Discrete Structures

The objective of this course is to familiarize students with concepts, structures, and techniques that are widely used in computer science and engineering. Foundational skills including creative problem-solving, constructing and understanding rigorous mathematical proofs, familiarity with elementary results in combinatorics, number theory, graph theory, as well as providing the mathematical prerequisites needed for many other courses offered in various fields of computer science and engineering, are among the goals of this course. The prerequisites for this course are high school mathematics, specifically familiarity with the basics of logic, quantifiers, functions, and set theory.

• Logic (2 sessions)
  • Inference rules
  • Proof methods
• Induction (1.5 sessions)
  • Mathematical induction, strong induction
  • Structural induction
• Number Theory (2.5 sessions)
  • Divisibility, GCD, LCM, prime numbers
  • Congruence, Euler's theorem, applications in cryptography
• Counting (4 sessions)
  • Basic counting principles, permutations and combinations, binomial coefficients
  • Permutations and combinations with repetition, inclusion-exclusion principle
  • Distributing objects into boxes, pigeonhole principle
  • Recurrence relations and solving homogeneous recurrence relations
• Discrete Probability (3 sessions)
  • Probability theory, probability distribution function, independent events, conditional probability
  • Random variables, expected value and variance
  • Markov, Chebyshev, and Chernoff inequalities
• Graphs (5 sessions)
  • Basic definitions, special graphs, bipartite graphs, graph representations
  • Paths and connectivity, Eulerian paths, Hamiltonian paths
  • Planar graphs, Euler's formula
  • Graph coloring
  • Trees and forests, rooted trees

• Assignments: 6 points
• Final exams: 14 points