Math/EECS1019: Discrete Math for Computer Science
Fall 2014
News
- All marks are online. Final grades are online - these are unofficial until approved by the department.
- Hw3, Hw4 marks are on ePost.
- A list of parts to skip are here. No chapters
other than those listed in the linked document were covered.
- Solutions to the last assignment are published. Solutions to the sample final had an error in Q 13, it is fixed now. Thanks to Lipai Xu for finding the error.
- Test 3 grades and solutions to the sample final are published.
- Office hours and tutorial as usual on Dec 10.
- Solutions to test 3 are published.
- Solutions to assignment 3 are published.
- If needed, please refer to the sections on logarithms in Sec A.2 in the Appendix of our test and Pseudocode in Sec A.3.
- A sample test 3 is available with solutions -- scroll down.
- The deadline for Assignment 3 is postponed to 9:30 pm Nov 19.
- Solutions to the test are here: v1 and v2. Please bear in mind the solutions were written on a plane after many hours of travel, so they may not be proofread well and are missing the Venn Diagrams.
- Test 2 scores are on ePost. Test 2 will be available for pickup Nov 6, 10 am - 12 noon on the second floor of Lassonde, on the north side (facing the stadium). Look for the TA, Bryan Gao. The place is near room 2001 of Lassonde.
- Test 3 is postponed by 1 week to Nov 24.
- Assignment 1 marks are on ePost.
- Sivanesan has a forum for this course here. Also there is a study session in Bethune (Thursday October 23
2 : 30 - 5 : 30 PM, BC (Bethune College) 105. I will try to drop in between my meetings.
- Test 1 marks are on ePost now. The highest was 29/30, the average was 20.1/30. If you have any concerns about your marks, please wait until you get your scripts back, compare your solutions to the published solutions and then contact me.
- Solutions to assignment 2 are published, see below.
- Tutorial at the normal time this week, see below.
- The web and terminal submit commands should be working now -- I apologize for setting the wrong permissions on the folder concerned. Please email ne if you have any problems.
- Assignment 2 deadline is extended to 5 pm, Oct 15.
- Solutions to test 1 are published, see below.
- HW 2 is published -- see below.
- Solutions to the sample test are published -- see below.
- Solutions to assignment 1 are published -- see below.
- Test 1 syllabus reduced -- see below.
- Please avail of the assistance provided by Bethune College to students. Your class representative is Sivanesan Vettivel and his contact details are below.
e-mail : nesan13[at]yorku.ca (replace [at] with @)
phone # : 647 dash 524 dash 1318
google calender (includes dates for study group sessions, etc.)
facebook group
- Some hints to HW 1 are here.
- Tutorial 1 time/place added.
- HW1 is posted. The slides from lec 1 have been updated (I had mistakenly put an older version there than the one I used in class). Test dates are posted.
- Welcome to Math/EECS 1019!
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 Curtis Lecture Hall (CLH) A
Office Hours: Wednesday: 4 - 6 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). [Note that the test in
which a student gets her/his minimum mark will be weighted down to 5%]
- Test 1 [Sept 29] Syllabus : Ch 1.1 - 1.6 (both inclusive) in the 7th edition. Omit the parts on System Specification, Boolean search and Logic Circuits in Sec 1.2. Also omit the subsection on page 51 called "Logic programming".
A sample test is here.
Solutions to the sample test are 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 to test 1 are version 1 and
version 2.
- Test 2 [Oct 27]: Syllabus: Ch 1.7, 1.8, 5.1, 5.2, ,2.1 and 2.2
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.
- Test 3 [Nov 24]: Syllabus - Ch 2.3,2.4,2.5 and proof techniques, including induction.
A sample test 3 is here. This is just a sample, your test may look quite different.
Solutions are here.
Solutions to test 3 are version 1 and
version 2.
- Homework (25%):
- Final (40%): Sun, 21 Dec 2014, 14:00-17:00, TM TMWEST (set by the registrar's office).
Syllabus - everything covered.
A sample final is here. Note that we had covered much of Ch 6 that term. We omitted Ch 6 and did parts of Ch 8 this term.
Solutions to the sample final are here.
Lectures
- Lecture 1 (Sep 8): 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 (pdf)
We covered upto slide 48 in this set. That corresponds to sections 1.1-1.5, and part of 1.6 (upto page 75 only). Read 1.2 but you will not be tested on the logic circuits and the system specification parts.
- Lecture 2 (Sep 15): Finish negation of quantifiers; cover inference in predicate logic. Work out a few examples. Sections 1.7 and 1.8: Proofs.
Same slides as before.
We covered upto slide 64 in class.
- Lecture 3 (Sep 22):
Finish the earlier set of slides.
Also a few additional slides are here (pdf)
- Lecture 4 (Sep 29): Test 1 for the first half of the class.
In the second half, lecture on Induction. My slides are here (pdf)
This is Ch 5.1. We skipped ahead because this is a very useful proof technique and fits well with the other proof techniques in Ch 1.
- Lecture 5 (Oct 6): Finish Strong Induction (Ch 5.2). Same slides as before.
Start Sets (Ch 2). My slides are here (pdf)
- Lecture 6 (Oct 20): Finish Sets and Functions. Solve problems in both. Start sequences and series. Same slides as before.
- Test 2 and Lecture 7 (Oct 27): Sequences and Series. Same slides as before.
- Lecture 8 (Nov 3): Cardinality and Infinite Sets. My slides are here (pdf)
- Lecture 9 (Nov 10): Prof Eric Ruppert will teach this class. Introduction to algorithm analysis (Ch 3).
- Lecture 10 (Nov 17): Algorithm analysis (Ch 3). My slides are here (pdf)
- Lecture 11 (Nov 24): Test 3 for the first half of the class. Introduction to recursion. My slides are here (pdf)
- Lecture 12 (Dec 1): Recursion continued (8.1, 8.2, 8.3). My slides are here (pdf)
Tutorials
- Tutorial 1 (Sep 17, 7-8:30 pm, LSB 105): We will work out more problems and answer questions. Attendance is not mandatory.
- Tutorial 2 (Sep 24, 7-8:30 pm, TEL 0014): We will work out more problems and answer questions. Attendance is not mandatory.
- Tutorial 3 (Oct 1, 7-8:30 pm, Ross S 203): Cancelled because I am indisposed.
- Tutorial 4 (Oct 8, 7-8:30 pm, Ross S 203):
- Tutorial 5 (Oct 15, 7-8:30 pm, SLH C):
- Tutorial 6 (Oct 22, 7-8:30 pm, Ross S 133):
- Tutorial 7 (Nov 19, 7-8:30 pm, CB 115):
- Tutorial 8 (Nov 26, 7-8:30 pm, VH 1152A):
- Tutorial 9 (Dec 3, 7-8:30 pm, ACW 104):
- Tutorial 10 (Dec 10, 7-8:30 pm, VH 3006):
- Tutorial 11 (Dec 17, 7-8:30 pm, VH 3006):
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). Alternatively you can use the dropbox
marked EECS 1019 next to the EECS main office.
Some hints are here.
Solutions to Assignment 1 are here.
- Assignment 2 is here.
To submit this assignment online, follow the instructions on this URL. You can also 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). Alternatively you can use the dropbox
marked EECS 1019 next to the EECS main office.
Solutions to Assignment 2 are here.
- Assignment 3 is here.
To submit this assignment online, follow the instructions on this URL. You can also 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. 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). Alternatively you can use the dropbox
marked EECS 1019 next to the EECS main office.
If you are submitting online, do not have spaces in the file name. You can use underscores or alternating upper and lower case alphabetical charaters.
Solutions to Assignment 3 are here.
- Assignment 4 is here.
To submit this assignment online, follow the instructions on this URL. You can also 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. 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). Alternatively you can use the dropbox
marked EECS 1019 next to the EECS main office.
If you are submitting online, do not have spaces in the file name. You can use underscores or alternating upper and lower case alphabetical charaters.
Solutions to Assignment 4 are here.
List of Topics
A list of expected learning outcomes will be here.
- Ch 1: Logic and Proofs. (Omit the subsection on page 51 called "Logic
programming").
- Ch 2: Sets, functions, sequences, sums. (Omit 2.6: Matrices)
- Ch 3: Algorithms.
- Ch 5: Induction and recursion.
- Ch 8 Advanced counting techniques (8.1 - 8.3)
- Ch 10: Graphs (10.1-10.5). - if time permits
Resources
Textbook
Kenneth H. Rosen. Discrete Mathematics and Its Applications, Seventh
Edition. McGraw Hill, 2012.
Available from the University bookstore. 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.
Important Dates
- Sep 8: First day of class
- Oct 13: Thanksgiving
- Oct 29-Nov 2: Co-curricular days (no classes or tests)
- Nov 7: Last day to drop courses without receiving a grade
- Dec 7: Classes end
- Dec 2, 8: Study days
- Dec 9-22: Exam period