CSE/MATH 1019: Discrete Math for Computer Science
Summer 2009
 
Instructor: Niloufar Shafiei
Lectures: Mondays, Wednesdays, 6-9 in room CLH  J of Curtis Lecture Halls
Email: niloo@cs.yorku.ca
 
The best way to contact me is by email. Please use a York account when sending me email, and start your subject line with "[1019]". Send messages in plain text, without attachments.
 
Office hours: Mondays, Wednesdays,  4-5 / CSE 2013
Tutorial: Mondays, Wednesdays,  5-6 / CLH J (starts June 15.)
 
Academic Honesty
It is important that you look at the computer science department's guidelines on academic honesty.
Solutions you hand in for homework assignments must be your own work. Although you may discuss the general approach to solving a problem with other people, you should never discuss the solution in detail.
Also, you must list on the cover page of your solutions any people with whom you have discussed the problems. The solutions you hand in should be your own work. While writing them, you may look at the course textbook and your own lecture notes but no other outside sources.
 
 
News
(June 8)    First class starts.
(June 8)    Assignment 1 is posted.
(June 15)    Assignment 2 is posted.
(June 17)    10% Quiz                                                                                                                    
(June 29)    Midterm
(July 1)    No class
(July 2)    Midterm grades are posted online.
(July 10 - 17)    Course evaluation is available online.                                                                             (http://courseevaluations.yorku.ca)      
(July 14)    Solutions to even numbered recommended exercises are posted here.    
(July 14)    Eric Ruppert’s notes for Section 7.1, 7.2 and 7.3.
(July 18)     Final exam at CLHB at 19:00.
(July 23)     Final exam grades are posted online.            
(July 24)     Unofficial grades are posted online.  (Unofficial grades may change.)  
                                                                           
Marking Scheme
 
Assignments:    15%                            
Quiz:                 10%
Midterm:           25%  
Final exam:       50%
 
 
Important days
June 8                    First class
June 17                   Quiz
June 29                  Midterm
July 4                     Drop deadline
July 15                   Last class  
    
 
Textbook
Kenneth H. Rosen. Discrete Mathematics and Its Applications, Sixth Edition. McGraw-Hill, 2007. Textbook web site. There is a list of errata on that site.
 
 
Course outline
Outline
 
 
Reading
June 8                        Introduction to the course
June 8                        Propositional Logic (Section 1.1)
June 8                        propositional Equivalences (Section 1.2)
June 8                        Proof Techniques
June 10                      Predicates and quantifiers (Section 1.3)
June 10                      Nested quantifiers (Section 1.4)
June 15                      Rules of inferences (Section 1.5)
June 15                      Introduction to proofs (Section 1.6)
June 22                      Proof methods and strategy (Section 1.7)
June 22                      Sets (Section 2.1)
June 24                      Set operations (Section 2.2)
June 24                      Functions (Section 2.3)
June 29                      Sequences and summations (Section 2.4)
July 6                         The growth of functions (Section 3.2)
July 8                         Mathematical induction (Section 4.1)
July 8                         Strong induction and well-ordering (Section 4.2)
July 13                       Recursive definitions and structural induction (Section 4.3)
July 13                       The basics of counting (Section 5.1)
July 13                       Recurrence relations (Section 7.1)
July 15                       Linear recurrence relations (Section 7.2)
July 15                       Divide-and-conquer algorithms and recurrences (Section 7.3)
July 15                       The pigeonhole principle (Section 5.2)
 
Assignments
Assignment 1          Solution
Assignment 2          Solution
Assignment 3          Solution
Assignment 4          Solution
Assignment 5          Solution
Assignment 6          Solution
 
Useful Links
Sessional deadlines
Must read info for students is found at this link.