CTP107 - Discrete Mathematics
2012 - 2013 Fall

Department of Computer Technology and Programming
(Last updated: 18/09/2007)   (CWPS ver: 2.0.2)
Instructor:
E-mail: okyay@ctp.bilkent.edu.tr
Lecture: MON 08:40-10:30, TUE 08:40-10:30, WED 08:40-10:30, FRI 10:40-12:30 GZ-52
Grading:     Grades
    Final: 40 %
    Midterm 1: 25%
    Midterm 2: 25%
    Quiz 1: 10%

The aim of this course is to develop logical reasoning ability of students. Elements of logic, set theory and operations on sets; DeMorgan's rules, finite and infinite. Relations and functions. Logic circuits. Induction and recursion, pigeonhole principle. Permutations, combinations and probability of discrete events. Graphs and their representation in computing.
Credit: 3 credits.
Lecture Hours: 4 hours in a week.

OBJECTIVES
1. To understand the operations on sets and their properties.
2. To apply the operations and principles on sets in solving problems.
3. To understand relations, their properties, equivalence & order relation
4. To understand basic notions of function, special types of function & their properties
5. To use relation, function & their properties in solving problems.
6. To understand the fundamental concepts of logic.
7. To understand the principle of mathematical induction, recursion, & pigeonhole principle.
8. To solve problems by using permutations andcombination.
9.To find the probability of discrete events.
10.To understand graphs and their representations.
11. To understand theory of trees, routed trees, tree traversals, and some applications.
Textbooks and Other Materials:
  • Required: "Discrete and Combinatorial Mathematics", R. P. Grimaldi
  • Required: "Discrete Mathematics for Computer Science", J.L.Mott,A. Kandel & T.P. Baker
  • Required: "Discrete Mathematics", Richard Johnsonbaugh
  • Recommended: "Discrete Mathematics", Melvin Hausner, Saunder
  • Recommended: "Discrete Mathematical Structures for Computer Science", Bernard Kolman, Robert C. Busby
  • Recommended: "A First Course in Discrete Mathematics", J.Molluzzo, F.Buckley
    Detailed Weekly Course Outline:
    Week Date COURSE OUTLINE
    1 13/09/2012
    17/09/2012
    Introduction: Objectives of the course.Logic and Proof – Propositional Logic
    2 20/09/2012
    24/09/2012
    Logic and Proof (cont.) Conditional Propositions and Logical Equivalance, QuantifiersValid arguments, Proof, Resolution Proofs
    3 27/09/2012
    01/10/2012
    Basic proof techniques: Nature of Proof, direct, indirect proofs, proof by contradiction
    4 04/10/2012
    08/10/2012
    Mathematical Induction
    QUIZ I
    5 11/10/2012
    15/10/2012
    Recurrence Relations: Solving recurrence relations
    6 18/10/2012
    22/10/2012
    Language of Mathematics: Sets, set theoretic proofs
    sequences and strings.
    7 25/10/2012
    29/10/2012
    Set Exercises
    8 01/11/2012
    05/11/2012
    MIDTERM WEEK
    9 08/11/2012
    12/11/2012
    Relations, properties of relatrions, equivalance relations, matrices of relations.
    10 15/11/2012
    19/11/2012
    Relations.
    Language of Mathematics:( Cont.) Functions: Domain, range, properties, types of functions, special functions
    11 22/11/2012
    26/11/2012
    Functions (exercises)
    Basics of Counting: Counting arguments (addition and multiplication principle), Permütations and combinations
    12 29/11/2012
    03/12/2012
    Basics of Counting: Introduction to Discrete probability theory.
    13 06/12/2012
    10/12/2012
    Probability
    14 13/12/2012
    17/12/2012
    Graphs and Trees : Graphs and digraph, classes of graphs, matrices associated with graphs, Binary trees, tree traversal.
    15 20/12/2012
    24/12/2012
    Application of graphs, Minimum weight Spanning Trees.

    End of CTP107 main page.