Discrete Structure syllabus

Discrete Structure

• 1 Logic and Proofs (8 Hrs.)

  • Propositional logic, equivalences and applications
  • Predicates and nested quantifiers
  • Inference rules
  • Proof methods, strategies and mistakes
• 2 Number Theory (7 Hrs.)

  • Divisibility, modular arithmetic and integer representations
  • Primes, GCD and LCM
  • Euclidean and extended Euclidean algorithms
  • Congruences and Chinese Remainder Theorem
  • Large-integer arithmetic and pseudorandom numbers
• 3 Induction and Recursion (5 Hrs.)

  • Mathematical and strong induction; well ordering
  • Recursive definitions and structural induction
  • Recursive functions, sets and algorithms
  • Program correctness; recursion versus iteration
• 4 Counting and Advanced Counting (12 Hrs.)

  • Sum, product, subtraction and division rules
  • Pigeonhole principles
  • Permutations, combinations, binomial theorem and Pascal's identity
  • Repetition and generation of permutations/combinations
  • Recurrence relations and linear recurrences
  • Inclusion-exclusion principle
• 5 Graphs (10 Hrs.)

  • Graph models, terminology and isomorphism
  • Connectivity, paths and circuits
  • Euler and Hamilton paths/circuits
  • Dijkstra's algorithm and travelling-salesman problem
  • Planarity and graph coloring
• 6 Trees (6 Hrs.)

  • Rooted trees, models and properties
  • Binary search, decision, prefix-code and game trees
  • Tree traversals; depth-first and breadth-first search
  • Spanning trees and Prim's/Kruskal's algorithms
• 7 Laboratory Works

  • Implement course concepts and algorithms in a suitable programming language