CENG 223 - Discrete Computational Structures

 

Fall 2013

 

Instructor: Faruk Polat

Catalog Data: Discrete Computational Structures (3-0) 3 

See the Catalog for more descriptive information. 

Prerequisites: None.  

Textbook(s):  K.H.Rosen, Discrete Mathematics and Its Applications, McGraw-Hill, 7th Edition, 2003.


Goals: To teach the basics of discrete mathematical structures..

Course Outline:

      • Propositional Logic: Logic,  Equivalences
      • Predicate Logic: Predicates and Quantifiers, Nested Quantifiers, Methods of Proof, Natural Deduction (additional material)
      • Sets and Functions: Sets,  Set Operations,  Functions,  Growth of Functions, Complexity of Algorithms
      • Integers: Integers and Division, Integers and Algorithms, Applications of Number Theory (Reading Assignment)
      • Induction and Recursion: Sequences and Summations, Mathematical Induction, Recursive Definitions and Structural Induction,  Recursive Algorithms
      • Counting: Permutations and Combinations,  Recurrence Relations,  Solving Recurrence Relations, Generating Functions, Inclusion and Exclusion
      • Relations: Relations and Their Properties, Representing Relations, Closure of Relations, Equivance Relations, Partial Orderings
      • Graphs: Int to Graphs, Graph Terminology, Representing Graphs, Connectivity, Euler and Hamiltonian Paths, Shortest Path Problem, Graph Coloring
      • Trees: Int to Trees, Applications of Trees, Spanning Trees, Min Spanning Trees

 

Evaluation:

  • Homeworks (15%)           

    Use an editor to prepare solutions (you may draw figures by hand) 
    Deliver your printed solutions in due dates.      

  • Pop-Quizzes (5%)
  • Midterm Exam 1 (22%)
  • Midterm Exam 2 (23%)
  • Final Exam 35 (45%):


Communication:

  •     All announcements including homework assignments will be made in the courses' newsgroup metu.ceng.course.223