Spring 2016
### Discrete Mathematics

**Course Description**

**Textbooks**

This course covered the mathematical topics most directly related to computer science. Topics included: logic, relations, functions, basic set theory, countability and counting arguments, proof techniques, mathematical induction, graph theory, combinatorics and recursion. Emphasis will be placed on providing a context for the application of the mathematics within computer science. The analysis of algorithms requires the ability to count the number of operations in an algorithm. Recursive algorithms in particular depend on the solution to a recurrence equation, and a proof of correctness by mathematical induction. The design of a digital circuit requires the knowledge of Boolean algebra. Software engineering uses sets, graphs, trees and other data structures. Logic is used in AI research in theorem proving and in database query systems. Proofs by induction and the more general notions of mathematical proof are ubiquitous in theory of computation, compiler design and formal grammars.

**Instructors:** Ali Reza Khanteymoor , Soudeh Behrouzinia

**Office Hours: **Mondays 13:30-14:30 by apointment

**Kenneth Rosen. Discrete Mathematics and Its Applications,****7th Edition**, McGraw Hill Publishing Co., 2012

**Ivan Niven, Mathematics of Choice: Or, How to Count Without Counting, 1975**

**Grading Policy**

- Homework and Quizzes (30%)
- Midterm Exam (30%)
- Final Exam (40%)
- Extra Point: Optional Assignments (Up to 20%)

**Syllabus**

Lecture & Topics | Readings & Useful Links | Handouts | Assignments |
---|---|---|---|

Introduction |
Slides | ||

Propositional Logic |
Rosen: 1.1 , 1.2 Truth Tables interactive demo: click the "Chapter 1 Truth Tables" Java applet |
Slides | HW |

Propositional Equivalence |
Rosen: 1.3 | Slides | |

Predicates and Quantifiers |
Rosen: 1.4 , 1.5 | Slides | HW |

Rules of Inference |
Rosen: 1.6 | Slides | HW: Deadline 2016-04-16 |

Introduction to Proofs |
Rosen: 1.7 , 1.8 | Slides | HW: Deadline 2016-04-23 |

Sets |
Rosen: 2.1 | Slides | |

Set Operations |
Rosen: 2.2 | Slides | |

Functions |
Rosen: 2.3 | Slides | |

Induction and Strong Induction |
Rosen: 5.1, 5.2 | Slides | |

The Basics of Counting |
Rosen: 6.1 | ||

Permutations and Combinations |
Rosen: 6.3 | HW: Deadline 2016-04-12 | |

Binomial Coeeficients |
Rosen: 6.4 | ||

Generalized Permutation and Combinations |
Rosen: 6.5 | HW: Deadline 2016-04-26 | |

Inclusion-Exclusion |
Rosen: 8.5, 8.6 | HW: Deadline 2016-04-26 | |

The Pigeonhole Principle |
Rosen: 6.2 | ||

Recursive Definitions |
Rosen: 5.3 | ||

Applications of Recurrence Relations |
Rosen: 8.1 | ||

Graphs and Graph Models |
Rosen: 10.1, 10.2 | ||

Connectivity In Graphs |
Rosen: 10.4 | ||

Euler and Hamiltonian Paths |
Rosen: 10.5 | ||

Shortest Path Problem |
Rosen: 10.6 | ||

Introduction to Trees |
Rosen: 11.1 | ||

Spanning Trees |
Rosen: 11.4, 11.5 |