Carleton University School of Computer Science
COMP 1805C
Discrete Structures I
2013 Winter
Preliminary course outline subject to change; last updated on Wed Jan 16 15:30:54 EST 2013

Class Schedule
Classroom: Loeb C164
Class Times: Tue., Thu. 10:00-11:30
Course Website: t.b.a.
Instructor Information
Instructor Office Telephone Email Office Hours
Dr Doron Nussbaum 5378 HP 1-(613)-520-2600 x1390 nussbaumatsignscs.carleton.ca By appointment
Teaching Assistants
T.A. Email Office Hours Room Number
Spencer Whyte SpencerWhyteatsigncmail.carleton.ca Mon 13:00 - 15:00 HP 1170
Elizabeth Stobert estobertatsignscs.carleton.ca Tue 10:00 -12:00 HP 1170
Gregory Bint gregorybintatsigncmail.carleton.ca Tue 13: - 15:00 HP 1170
Po Lai polaiatsigncmail.carleton.ca Wed 12:00 - 14:00 HP 1170
Andrew Belu AndrewBeluatsigncmail.carleton.ca Thu 9:30-11:30 HP 1170
Eduardo Mesa Barrameda eamesabaatsignconnect.carleton.ca Thu 13:00 - 15:00 HP 1170
Vinh Nguyen VinhNguyenatsigncmail.carleton.ca Fri 10:00 - 12:00 HP 1170
Matthew Eastman mattheweastmanatsigncmail.carleton.ca Tutorial TA by Appointment TBA
Joshua Brach JoshuaBrachatsigncmail.carleton.ca Thursday 14:30 - 16:30 HP 1170
Amin Gheibi AminGheibiatsigncmail.carleton.ca Tutorial TA by Appointment TBA
Course Description
Introduction to discrete mathematics and discrete structures. Topics include: propositional logic, predicate calculus, set theory, complexity of algorithms, mathematical reasoning and proof techniques, recurrences, induction, finite automata and graph theory. Material is illustrated through examples from computing.
Topics Covered
Tentative Course Topics will include not necessary in this order (Note, other topics may be introduced): 1. Logic and Proofs - Propositional calculus, predicates and quantifiers. Methods of proof 2. Induction and Recurrences 3. Graph Theory - basic definitions, planar graphs, connectivity, and computer representations of graphs 4. Trees - Paths, cycles, directed trees, search trees, spanning trees 5. Sets and Functions 6. Sums 7. Counting - Basic definitions, pigeonhole principle, permutations and combinations 8. Relations - basic definitions, representation of relations, closures, equivalence relations, partial orderings. 9. Algorithms and their complexity 10. Boolean functions and their representation
Course Objectives
This course is designed to give students a basic understanding of Discrete Mathematics and its role in Computer Science. Computers handle discrete rather than continuous data. The course presents an overview of some of the major theoretical concepts needed to analyze this type of data. Topics include: propositional logic, set theory, Boolean algebra, introduction to complexity of algorithms, mathematical reasoning, counting, recurrences, functions and relations, introduction to graphs.
Textbook (s)
Eric Lehman, Thomson Leighton, Albert R. Meyer, Mathematics for Computer Science. Available freely on the course website.
Evaluation
Students will be evaluated in this course according to the following measures.

Component Weight Due Date
Five assignments 20% TBA
Three class tests (with an optional fourth) 30% TBA
Final exam 50% TBA
Important Dates
Tests are held in the tutorials on (January 22, subject to change: Week 3 - Jan. 23, Week 6 - Feb. 13, Week 9 - March 13, Week 12 - Apr 3(optional). Reading week February 18-22. Last Day for PMC accommodation: March 8. Last Day of classes: Wednesday, April 10.
Collaboration Policy
Collaborating on assignments is strictly disallowed. You must complete the work by yourself. If you need help, please see a TA or your instructor. Posting assignment solutions on discussion boards before the due date and time is also prohibited.
Undergraduate Academic Advisor
The Undergraduate Advisor for the School of Computer Science is available in Room 5302C HP, by telephone at 520-2600, ext. 4364 or by email at undergraduate_advisor@scs.carleton.ca. The undergraduate advisor can assist with information about prerequisites and preclusions, course substitutions/equivalencies, understanding your academic audit and the remaining requirements for graduation. The undergraduate advisor will also refer students to appropriate resources such as the Science Student Success Centre, Learning Support Services and the Writing Tutorial Services.
University Policies
Student Academic Integrity Policy
Every student should be familiar with the Carleton University student academic integrity policy. A student found in violation of academic integrity standards may be awarded penalties which range from a reprimand to receiving a grade of F in the course or even being expelled from the program or University. Some examples of offences are: plagiarism and unauthorized co-operation or collaboration. Information on this policy may be found in the Undergraduate Calendar.
Plagiarism
As defined by Senate, "plagiarism is presenting, whether intentional or not, the ideas, expression of ideas or work of others as one's own". Such reported offences will be reviewed by the office of the Dean of Science.
Unauthorized Co-operation or Collaboration
Senate policy states that "to ensure fairness and equity in assessment of term work, students shall not co-operate or collaborate in the completion of an academic assignment, in whole or in part, when the instructor has indicated that the assignment is to be completed on an individual basis". Please refer to the course outline statement or the instructor concerning this issue.
Academic Accommodations for Students with Disabilities
The Paul Menton Centre for Students with Disabilities (PMC) provides services to students with Learning Disabilities (LD), psychiatric/mental health disabilities, Attention Deficit Hyperactivity Disorder (ADHD), Autism Spectrum Disorders (ASD), chronic medical conditions, and impairments in mobility, hearing, and vision. If you have a disability requiring academic accommodations in this course, please contact PMC at 613-520-6608 or pmc@carleton.ca for a formal evaluation. If you are already registered with the PMC, contact your PMC coordinator to send me your Letter of Accommodation at the beginning of the term, and no later than two weeks before the first in-class scheduled test or exam requiring accommodation (if applicable). After requesting accommodation from PMC, meet with me to ensure accommodation arrangements are made. Please consult the PMC website for the deadline to request accommodations for the formally-scheduled exam (if applicable) at http://www2.carleton.ca/pmc/new-and-current-students/dates-and-deadlines/
Religious Obligation
Write to me with any requests for academic accommodation during the first two weeks of class, or as soon as possible after the need for accommodation is known to exist. For more details visit the Equity Services website: http://www2.carleton.ca/equity/
Pregnancy Obligation
Write to me with any requests for academic accommodation during the first two weeks of class, or as soon as possible after the need for accommodation is known to exist. For more details visit the Equity Services website: http://www2.carleton.ca/equity/
Medical Certificate
The following is a link to the official medical certificate accepted by Carleton University for the deferral of final examinations or assignments in undergraduate courses. To access the form, please go to http://www.carleton.ca/registrar/forms