Peter Selinger: CSCI/MATH 2112, Fall 2005, Section 2

CSCI/MATH 2112, Discrete Structures I, Section 2
Fall 2005
Peter Selinger

Updates are shown in red.

Course Description: This course is 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
Phone: 494-3311 (I prefer email when possible)
Email: selinger@mathstat.dal.ca (please put "2112" in the subject line)
Office Hours: currently MW 1-2, or by appointment.
Teaching Assistants: Xiaofen Zheng and Zhen Zhen will be teaching assistants for this course.
Website: Updated information, assignments, any handouts, etc., will be available from http://www.mathstat.dal.ca/~m2112/02/
Lectures: TTh 11:35-12:55, Dunn 101
Tutorials: Tutorial 1: M 14:35-15:25 McCain 2116
Tutorial 2: M 14:35-15:25 McCain 2116
Tutorial 3: T 15:05-15:55 McCain 2102
Each student should attend one 1-hour tutorial per week, either on Mondays or on Tuesdays. In the Tutorial, you will be given problems to solve, individually and in groups. You will also have an opportunity to ask questions about the homework.
Topics: This class, together with CSCI/MATH 2113, offers a survey of the following areas: set theory, mathematical induction, number theory, relations, functions, algebraic structures and introductory graph theory. The topics to be discussed are fundamental to most areas of Mathematics and have wide applicability to Computer Science.
Prerequisites: Nova Scotia Mathematics 441 or equivalent
Textbook: S. S. Epp. Discrete Mathematics with Applications. Third Edition, Brooks/Cole, 2004. ISBN: 0-534-35945-0. If you are looking for this textbook at the Dalhousie Bookstore in the Student Union Building, look under MATH 2112, not CSCI 2112.
Course Work: There will be a midterm exam and a final exam. The midterm exam will be on Wednesday, October 26, 7-8:30pm in Dunn 117. There will also be weekly homework, to be handed in at the beginning of class on Thursdays. Late homework will not be accepted except with my prior permission. Each week, you will also be assigned some reading from the textbook. At irregular times, we will have a 5-minute quiz in class related to the reading assignment.
Missed test policy: A missed midterm exam cannot be written at another time. If you miss the midterm exam 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 test, or (2) if you have an officially valid excuse such as a medical doctor's note. In these cases, the weight of the missed test will be shifted to the final exam (i.e., the final exam will then count 80% instead of 55%).
Marks: Marks will be based on the exams, homework, and quizes. Class participation may be taken into account. The midterm exam counts 25%, the final exam counts 55%, the homework counts 15%, and the quizes count 5%. 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 1.1, 1.2, 1.3. Introduction to propositional logic; proofs, valid and invalid arguments.
Sections 2.1, 2.2, 2.3, 2.4. Predicates and quantified statements; arguments with quantified statements.
Sections 3.1, 3.6, 3.2, 3.3, 3.7, 3.4, 3.5 Direct proofs; counterexamples; quotient-remainder theorem; floor and ceiling functions; irrationality of some square roots; infinitude of primes.
Sections 4.1, 4.2, 4.3 Mathematical Induction.
Sections 5.1, 5.2, 5.3 Set Theory; set properties; partitions; power sets.
Sections 3.8, 4.5 Algorithms; correctness of algorithms.
Sections 4.4, 8.1, 8.2 Strong induction; recursively defined sequences; solving recurrences by iteration.
Sections 9.1, 9.2, 9.3, 9.4 Big Oh notation; efficiency of algorithms; exponential and logarithmic functions.
Sections 10.1, 10.2, 10.3 Relations; equivalence relations.
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 disabilities@dal.ca, or drop in at the Killam, G28.
Plagiarism policy: Plagiarism is considered 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://www.registrar.dal.ca/calendar/ug/UREG.htm#12

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 Phone: 494-3311 (I prefer email when possible) Email: selinger@mathstat.dal.ca (please put "2112" in the subject line)
Office Hours:	currently MW 1-2, or by appointment.
Teaching Assistants:	Xiaofen Zheng and Zhen Zhen will be teaching assistants for this course.
Website:	Updated information, assignments, any handouts, etc., will be available from http://www.mathstat.dal.ca/~m2112/02/
Lectures:	TTh 11:35-12:55, Dunn 101
Tutorials:	Tutorial 1: M 14:35-15:25 McCain 2116 Tutorial 2: M 14:35-15:25 McCain 2116 Tutorial 3: T 15:05-15:55 McCain 2102 Each student should attend one 1-hour tutorial per week, either on Mondays or on Tuesdays. In the Tutorial, you will be given problems to solve, individually and in groups. You will also have an opportunity to ask questions about the homework.
Topics:	This class, together with CSCI/MATH 2113, offers a survey of the following areas: set theory, mathematical induction, number theory, relations, functions, algebraic structures and introductory graph theory. The topics to be discussed are fundamental to most areas of Mathematics and have wide applicability to Computer Science.
Prerequisites:	Nova Scotia Mathematics 441 or equivalent
Textbook:	S. S. Epp. Discrete Mathematics with Applications. Third Edition, Brooks/Cole, 2004. ISBN: 0-534-35945-0. If you are looking for this textbook at the Dalhousie Bookstore in the Student Union Building, look under MATH 2112, not CSCI 2112.
Course Work:	There will be a midterm exam and a final exam. The midterm exam will be on Wednesday, October 26, 7-8:30pm in Dunn 117. There will also be weekly homework, to be handed in at the beginning of class on Thursdays. Late homework will not be accepted except with my prior permission. Each week, you will also be assigned some reading from the textbook. At irregular times, we will have a 5-minute quiz in class related to the reading assignment.
Missed test policy:	A missed midterm exam cannot be written at another time. If you miss the midterm exam 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 test, or (2) if you have an officially valid excuse such as a medical doctor's note. In these cases, the weight of the missed test will be shifted to the final exam (i.e., the final exam will then count 80% instead of 55%).
Marks:	Marks will be based on the exams, homework, and quizes. Class participation may be taken into account. The midterm exam counts 25%, the final exam counts 55%, the homework counts 15%, and the quizes count 5%. 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 1.1, 1.2, 1.3. Introduction to propositional logic; proofs, valid and invalid arguments. Sections 2.1, 2.2, 2.3, 2.4. Predicates and quantified statements; arguments with quantified statements. Sections 3.1, 3.6, 3.2, 3.3, 3.7, 3.4, 3.5 Direct proofs; counterexamples; quotient-remainder theorem; floor and ceiling functions; irrationality of some square roots; infinitude of primes. Sections 4.1, 4.2, 4.3 Mathematical Induction. Sections 5.1, 5.2, 5.3 Set Theory; set properties; partitions; power sets. Sections 3.8, 4.5 Algorithms; correctness of algorithms. Sections 4.4, 8.1, 8.2 Strong induction; recursively defined sequences; solving recurrences by iteration. Sections 9.1, 9.2, 9.3, 9.4 Big Oh notation; efficiency of algorithms; exponential and logarithmic functions. Sections 10.1, 10.2, 10.3 Relations; equivalence relations.
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 disabilities@dal.ca, or drop in at the Killam, G28.
Plagiarism policy:	Plagiarism is considered 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://www.registrar.dal.ca/calendar/ug/UREG.htm#12