Peter Selinger: Math/CSCI 2113, Winter 2010

Math/CSCI 2113, Discrete Structures II
Winter 2010
Peter Selinger

Updates are shown in red.

Course Description: This course is the continuation of Math/CSCI 2112, a basic course in logic and discrete mathematics. Discrete structures are fundamental to computer science, in the same way that calculus and geometry are fundamental to physics. They form the foundations of many areas of computer science, such as data structures, database theory, algorithms, automata theory, compiler design, and cryptography. The most important goal of the course is to learn to think abstractly, to reason correctly, and to work with symbolic representations.

Instructor: Prof. Peter Selinger
Department of Mathematics and Statistics
Chase Building, Room 303
Email: selinger@mathstat.dal.ca (please mention "2113" in the subject line)
Lectures: MWF 11:35-12:25, LSC C244
Website: Updated information, assignments, any handouts, etc., will be available from http://www.mathstat.dal.ca/~selinger/2113/
Office Hours: Wednesdays 2:30-3:30 in Chase 303.
Topics: The topics to be covered will include: Counting and probability, solution of recurrence relations, generating functions, Chinese remainder theorem, trees and graphs, finite state machines, boolean algebra.
Prerequisites: Math/CSCI 2112.
Textbook: Susanna S. Epp. Discrete Mathematics with Applications. Third Edition, Brooks/Cole, 2004. If you are looking for this textbook at the Dalhousie Bookstore in the Student Union Building, look under MATH 2113, not CSCI 2113.
Course Work: There will be an in-class midterm and a final exam. The midterm is scheduled for Friday, February 19 in class. There will also be weekly homework, to be handed in at the beginning of class on Fridays. From each homework set, I will choose some number of problems that will be graded. Late homework will not be accepted except with my prior permission. Each week, you will also be assigned some reading from the textbook.
Missed test policy: A missed midterm cannot be written at another time. If you miss the midterm without my prior permission, then it will count as a 0. Exceptions are made in two cases: (1) if you obtain my prior permission to miss a midterm, or (2) if you have an officially valid excuse such as a medical doctor's note (see also the Sick Notes Policy below). In these cases, the weight of the missed midterm will be shifted to the final exam (i.e., the final exam will then count 75% instead of 50%). There is no make-up option for the final exam.
Marks: Marks will be based on the homework, midterm, and final exam. Class participation may be taken into account. The homework counts 25%, the midterm counts 25%, and the final exam counts 50%. You need to pass the final exam in order to pass the course. Numerical grades are converted to letter grades via the standard Faculty of Science scheme: 90-100 = A+, 85-89.9 = A, 80-84.9 = A-, 75-79.9 = B+, 70-74.9 = B, 65-69.9 = B-, 62-64.9 = C+, 58-61.9 = C, 55-57.9 = C-, 50-54.9 = D, 0-49.9 = F.
Syllabus: We will cover the following sections of the textbook, in approximately the given order.
Sections 6.1-9. Counting and probability.
Section 8.3. Solving recurrence relations; generating functions.
Sections 11.1-6. Graphs and trees.
Sections 12.1-3. Finite state machines.
Section 10.4. The Chinese remainder theorem.
Section 5.6. Boolean algebras.
Students with disabilities: Students with disabilities should register as quickly as possible at Student Accessibility Services if they want to receive academic accommodations. To do so please phone 494-2836, e-mail access@dal.ca, visit http://studentaccessibility.dal.ca/, or drop in just outside the Killam Library at 6227 University Avenue.
Plagiarism policy: Plagiarism is a serious academic offence which may lead to loss of credit, suspension or expulsion from the University, or even the revocation of a degree. Please read the Policy on Intellectual Honesty contained in the Calendar or on the Dalhousie web site at: http://ug.cal.dal.ca/UREG.htm#12.
Pandemic advisory: From: Alan Shaver, Vice President Academic and Provost
September, 2009
In the event of an escalation of the pandemic H1N1 influenza virus the University may need to authorize Academic Units to change elements of class schedules and/or evaluation plans as outlined in course syllabi. Any change is intended to support the primary goal of reducing the risk of spreading a pandemic influenza among students, faculty and staff.
Although it is difficult to predict the severity of the pandemic, the University is committed to minimizing the impact on students' academic progress. Therefore every effort will be made to provide students with options for continued learning and for continued fair evaluations.

Adjustments to course assignments;
Changes to the dates of exams;
Arrangements for alternative evaluations for students affected by H1N1 influenza virus;
Adjustments to work terms;
Modification of marks awarded for participation;
Adjustments to attendance policies.
Any alternative plans made in individual courses may be superseded by University-wide or Government measures to reduce the spread of the pandemic H1N1 influenza virus.
We will continue to keep the University Community informed as we proceed into the 2009/10 academic term.
Sick notes policy: This is the modification for Academic Regulation 16.8 regarding requirement for medical certificates and H1N1 Influenza Virus:
For the 2009 fall academic term, section 16.8 of the University's Academic Regulations, which require a medical certificate due to illness, is suspended for those individuals experiencing influenza-like symptoms.
In all cases, students are required to immediately advise their instructors of an absence due to influenza-like symptoms as this will assist in monitoring the extent of illness across the University.
Students are encouraged to follow the decision chart guidelines to assist in making care decisions in the event of flu-like symptoms.
A Senate determination will be made by December, 2009 on whether to extend this modified regulation into the 2009/2010 winter term.

To Peter Selinger's Homepage:

Peter Selinger / Department of Mathematics and Statistics / Dalhousie University
selinger@mathstat.dal.ca / PGP key

Instructor:	Prof. Peter Selinger Department of Mathematics and Statistics Chase Building, Room 303 Email: selinger@mathstat.dal.ca (please mention "2113" in the subject line)
Lectures:	MWF 11:35-12:25, LSC C244
Website:	Updated information, assignments, any handouts, etc., will be available from http://www.mathstat.dal.ca/~selinger/2113/
Office Hours:	Wednesdays 2:30-3:30 in Chase 303.
Topics:	The topics to be covered will include: Counting and probability, solution of recurrence relations, generating functions, Chinese remainder theorem, trees and graphs, finite state machines, boolean algebra.
Prerequisites:	Math/CSCI 2112.
Textbook:	Susanna S. Epp. Discrete Mathematics with Applications. Third Edition, Brooks/Cole, 2004. If you are looking for this textbook at the Dalhousie Bookstore in the Student Union Building, look under MATH 2113, not CSCI 2113.
Course Work:	There will be an in-class midterm and a final exam. The midterm is scheduled for Friday, February 19 in class. There will also be weekly homework, to be handed in at the beginning of class on Fridays. From each homework set, I will choose some number of problems that will be graded. Late homework will not be accepted except with my prior permission. Each week, you will also be assigned some reading from the textbook.
Missed test policy:	A missed midterm cannot be written at another time. If you miss the midterm without my prior permission, then it will count as a 0. Exceptions are made in two cases: (1) if you obtain my prior permission to miss a midterm, or (2) if you have an officially valid excuse such as a medical doctor's note (see also the Sick Notes Policy below). In these cases, the weight of the missed midterm will be shifted to the final exam (i.e., the final exam will then count 75% instead of 50%). There is no make-up option for the final exam.
Marks:	Marks will be based on the homework, midterm, and final exam. Class participation may be taken into account. The homework counts 25%, the midterm counts 25%, and the final exam counts 50%. You need to pass the final exam in order to pass the course. Numerical grades are converted to letter grades via the standard Faculty of Science scheme: 90-100 = A+, 85-89.9 = A, 80-84.9 = A-, 75-79.9 = B+, 70-74.9 = B, 65-69.9 = B-, 62-64.9 = C+, 58-61.9 = C, 55-57.9 = C-, 50-54.9 = D, 0-49.9 = F.
Syllabus:	We will cover the following sections of the textbook, in approximately the given order. Sections 6.1-9. Counting and probability. Section 8.3. Solving recurrence relations; generating functions. Sections 11.1-6. Graphs and trees. Sections 12.1-3. Finite state machines. Section 10.4. The Chinese remainder theorem. Section 5.6. Boolean algebras.
Students with disabilities:	Students with disabilities should register as quickly as possible at Student Accessibility Services if they want to receive academic accommodations. To do so please phone 494-2836, e-mail access@dal.ca, visit http://studentaccessibility.dal.ca/, or drop in just outside the Killam Library at 6227 University Avenue.
Plagiarism policy:	Plagiarism is a serious academic offence which may lead to loss of credit, suspension or expulsion from the University, or even the revocation of a degree. Please read the Policy on Intellectual Honesty contained in the Calendar or on the Dalhousie web site at: http://ug.cal.dal.ca/UREG.htm#12.
Pandemic advisory:	From: Alan Shaver, Vice President Academic and Provost September, 2009 In the event of an escalation of the pandemic H1N1 influenza virus the University may need to authorize Academic Units to change elements of class schedules and/or evaluation plans as outlined in course syllabi. Any change is intended to support the primary goal of reducing the risk of spreading a pandemic influenza among students, faculty and staff. Although it is difficult to predict the severity of the pandemic, the University is committed to minimizing the impact on students' academic progress. Therefore every effort will be made to provide students with options for continued learning and for continued fair evaluations. Adjustments to course assignments; Changes to the dates of exams; Arrangements for alternative evaluations for students affected by H1N1 influenza virus; Adjustments to work terms; Modification of marks awarded for participation; Adjustments to attendance policies. Any alternative plans made in individual courses may be superseded by University-wide or Government measures to reduce the spread of the pandemic H1N1 influenza virus. We will continue to keep the University Community informed as we proceed into the 2009/10 academic term.
Sick notes policy:	This is the modification for Academic Regulation 16.8 regarding requirement for medical certificates and H1N1 Influenza Virus: For the 2009 fall academic term, section 16.8 of the University's Academic Regulations, which require a medical certificate due to illness, is suspended for those individuals experiencing influenza-like symptoms. In all cases, students are required to immediately advise their instructors of an absence due to influenza-like symptoms as this will assist in monitoring the extent of illness across the University. Students are encouraged to follow the decision chart guidelines to assist in making care decisions in the event of flu-like symptoms. A Senate determination will be made by December, 2009 on whether to extend this modified regulation into the 2009/2010 winter term.