CSE1019, Fall 2011

Math/CSE1019: Discrete Math for Computer Science
Fall 2011

News

0. The final exam marks are on ePost. Unofficial grades have also been posted. Official grades will not be available until after the department has approved the grades, likely at the end of this week.
1. An old final is here. Use this for practice. Your final will be similar but not necessarily identical in the weightage given to various chapters. Solutions are here. The solutions have been updated to fix a typo and add two missing solutions.
2. There will be a bonus test on Dec 5. This is purely voluntary and taking it (or otherwise) will not reduce your final grade in any circumstance. The syllabus is Algorithms and Recursion.

General Information

Instructor: Suprakash Datta
Office: CSEB, room 3043
Telephone: (416) 736-2100 ext. 77875
Facsimile: (416) 736-5872
Lectures: Monday, 7-10 pm in Stedman Lecture Hall (SLH) F
Office Hours: Wednesday: 3 - 5 pm or by appointment, in CSEB 3043.
Email: [lastname]@cs.yorku.ca (While you are free to send me email from any account, please realize that email from domains other than yorku.ca have a higher chance of entering my spam folder. I do check my spam folder irregularly , but to be safe, consider using your cs account when sending me email.)

Grades

Grades can be checked online by clicking here

Three in-class tests (15% each): October 17, October 31, Nov 21.
1. Syllabus for test 1: Ch 1.1-1.6 (inclusive). A sample test is here. Please note that the sample test will only give a reasonable idea of the difficulty, length and format of the test. The questions on the test will be different from these.
  Solutions for test 1 are version 1 and version 2. Please review these solutions before discussing your marks with me.
2. Syllabus for test 2: Ch 1.7,1.8,2.1,2.2,2.3,2.4.
  A sample test is here. Please note that the sample test will only give a reasonable idea of the difficulty, length and format of the test. The questions on the test will be different from these.
  Questions for practice:
  Pg 91: Q26, 33
  Pg 108: Q3,25,29,34
  Pg 113: Q 38
  Pg 126: Q 24,34,39
  Pg 136: Q 19, 30
  Pg 152: Q 14,44
  Pg 168: Q 34,44,46.
  Solutions for test 2 are version 1 and version 2. Please review these solutions before discussing your marks with me.
3. Syllabus for test 3: Sec 2.5, 5.1, 5.2. Note that 3.1 is not on this test.
  Questions for practice:
  Pg 188: Q32, Q34 (difficult). Pg 329: Q6, 8, 10, 16, 20 , 44
  Pg 341: Q7, 8, 30.
  Solutions for test 3 are version 1 and version 2.
4. Syllabus for the bonus test: Everything covered in Algorithms and recursion (counting is not part of either).
  Questions for practice:
  Pg 357: 8,24,26
  Pg 370: 24,32,44
  Pg 377: 7,12
  Pg 379: 4,12,14.
Solutions for the bonus test are version 1 and version 2.
Homework (15%)
Final (40%): Sat Dec 17, 7-10 pm, at ACW 206. Syllabus - everything covered.

Lectures

Lecture 1 (Sep 12): Intro to Propositional logic and Predicate logic. Practice problems (do not submit): Sec 1.1 -- Q 9, 12, 21, 25, 33 (pg 13-16). My slides are here.
Lecture 2 (Sep 26): Predicate logic continued. Introduction to proofs. My slides are here.
Lecture 3 (Oct 3): Introduction to sets and functions. My slides are in ppt and pdf.
Lecture 4 (Oct 17): 7 - 8 pm test 1. Functions, sequences and series. Same slides as in Lecture 3. (There was one correction on slide 41).
Lecture 5 (Oct 24): Cardinality of Sets. Same slides as in Lecture 3.
Lecture 6 (Oct 31): 7 - 8 pm test 2. Review uncountability of the reals. Introduction to Algorithms. My slides are here (pdf)
Lecture 7 (Nov 7) Induction. My slides are here (pdf) . More on algorithms. My slides are here (pdf) .
Lecture 8 (Nov 14) More on Algorithms. My slides are here (pdf) .
Lecture 9 (Nov 21) Finish algorithm analysis and asymptotic notation (same slides as before). Start Recursion and recursive programs. My slides are here (ppt) .
Lecture 10 (Nov 28) Counting techniques. My slides are here (ppt) .
Lecture 11 (Dec 5) Counting techniques - permutations, combinations and problems. No new slides were used. The bonus test took place in this class.

Assignments

Assignment 1 is here. To submit this assignment online, log in to a CSE linux machine and type the following (without the quotes) "submit 1019 a1 filename.pdf" where filename.pdf is your assignment. Please do not submit MS Word or any other word processor files. You can get (free) pdf converters online for any platform that you use (e.g., I have used primopdf without any problems on Windows platforms).
The solutions are here. The solutions have been updated to correct Q1a,b.
Assignment 2 is here. To submit this assignment online, log in to a CSE linux machine and type the following (without the quotes ) "submit 1019 a2 filename.pdf" where filename.pdf is your assignment. Please do not submit MS Word or any other word processor files. Please do NOT email your solutions to me.
The solutions are here.
Assignment 3 is here. To submit this assignment online, log in to a CSE linux machine and type the following (without the quotes ) "submit 1019 a3 filename.pdf" where filename.pdf is your assignment. Please do not submit MS Word or any other word processor files. Please do NOT email your solutions to me.
The solutions are here.
Assignment 4 is here. To submit this assignment online, log in to a CSE linux machine and type the following (without the quotes ) "submit 1019 a4 filename.pdf" where filename.pdf is your assignment. Please do not submit MS Word or any other word processor files. Please do NOT email your solutions to me.
The solutions are here.

List of Topics

A list of expected learning outcomes is here.

Ch 1: Logic and Proofs. (Omit the subsection on page 51 called "Logic programming".
Ch 2: Sets, functions, sequences, sums. (Omit 2.6)
Ch 3: Algorithms.
Ch 5: Induction and recursion.
Ch 6: Counting Techniques (we will not cover 6.5, 6.6).
Ch 8 Advanced counting techniques (8.1 - 8.3) - we did not have time to cover this and it is not on the exam syllabus.

Resources

Textbook

Discrete Mathematics and Its Applications, Seventh Edition

Textbook web site

Other References

Norman L. Biggs. Discrete Mathematics. Oxford University Press, 2002.
Alan Doerr and Kenneth Lavasseur. Applied Discrete Structures for Computer Science. Science Research Associates, 1985.
Gary Haggard, John Schlipf and Sue Whitesides. Discrete Mathematics for Computer Science. Thomson, 2006.
Rod Haggarty. Discrete Mathematics for computing. Addison-Wesley, 2002.
Bernard Kolman, Robert C. Busby and Sharon Cutler Ross. Discrete Mathematical Structures. Pearson, 2004.
Edward Scheinerman. Mathematics: A Discrete Introduction. Thomson, 2006.
Daniel Solow. How to Read and Do Proofs: An Introduction to Mathematical Thought Processes. Wiley, 2002.
Andrew Wohlgemuth. Introduction to Proof in Abstract Mathematics. Saunders College Publishing, 1990.

Academic Honesty

It is important that you look at the departmental guidelines on academic honesty.

Although you may discuss the general approach to solving a problem with other people, you should not discuss the solution in detail. You must not take any written notes away from such a discussion. 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.

Math/CSE1019: Discrete Math for Computer Science Fall 2011