Ali Reza Khanteymoori

Spring 2016

Discrete Mathematics

Course Description

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



Grading Policy


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    
Past Exams: Midterm 1, Midterm 2, Final 1, Final 2, Final 3 (All in Persian)