#
Dalhousie University

MATH 2112 / CSCI 2112

Discrete Structures

Course Information, Fall 2006

###
Note: The final exam time is on Saturday, December 16 at 12 pm at __Dunn 101__.

Note 2: The corrected proof of the Merge Sort complexity is here.

Note 3: Office hours updated for exam week (see below). Old homeworks are available for pickup at my office.

__General Information:__

Instructor: Dr. O-Yeat Chan

E-mail address: math@oyeat.com

Course website: http://www.oyeat.com/courses/math2112/

Office: Chase 251

Office hours: Wed 1330-1530, Thu/Fri 1400-1600, or by appointment

Office phone: 494-3896

Class hours: MWF 1135-1225

Class meets at: LSC-Psychology P4258

Text: Susanna S. Epp, *Discrete Mathematics with Applications, 3rd ed.* Thomson Learning.

Important information about the course, as well as any updates, will be posted to the website.
__Tutorials and TAs:__

The TA for the course is: Jane Tougas (email)

The tutorial meets Mondays 1435-1525 at McCain 2116

Jane will be responsible for running the tutorial and grading homework. If you have any questions about the material, do not hesitate to ask Jane or myself.
__Course Description:__

MATH/CSCI 2112 is the first half of the Discrete Structures sequence. The focus of this half of the sequence is on logical reasoning and mathematical thinking, as well as to familiarize you with the precision of mathematical language. You will learn how to write mathematical proofs and several common proof techniques. We will also cover some topics considered ``discrete mathematics'', for example set theory and recursion. Further topics, such as enumeration, graph theory, and probability will be treated in the second half of the sequence, MATH/CSCI 2113.
__Syllabus:__

We will cover the following topics in this course
- Propositional and predicate logic, validity of arguments, truth tables. (Ch. 1 and 2)
- Introduction to mathematical proof and proof techniques (Ch. 3)
- Basic number theory, divisibility, mod notation (Ch. 3 and 10.4)
- Recursion and induction (Ch. 4 and 8)
- Complexity-analysis of algorithms, Big-O, Big-Omega, and Big-Theta notation (Ch. 9)
- Basic set theory, relations, functions (Ch. 5, various parts of Ch. 7 and 10)

__Grading Policy:__

The course grade will be determined as follows:

Homework | 20% |

Midterm | 30% |

Final exam | 50% |

**Total ** | 100% |

Your final grade will be determined using the following grading scale (slightly modified from the default Faculty of Science conversion scheme):

**Score** | 90-100 | 85-89.9 | 80-84.9 | 76-79.9 | 72-75.9 | 68-71.9 | 65-67.9 | 62-64.9 | 58-61.9 | 50-57.9 | below 50 |

**Grade** | A+ | A | A- | B+ | B | B- | C+ | C | C- | D | F |

__Homework:__

There will be homework problems assigned each week, to be collected on Wednesdays. From each problem set I will choose some number of problems that are to be graded. Each problem set will have the same weight.

Homework 1 is due on Wednesday, Sept 20, at the beginning of lecture. Solutions

Homework 2 is due on Wednesday, Sept 27, at the beginning of lecture. Solutions

Homework 3 is due on Wednesday, Oct 4, at the beginning of lecture. Solutions

Homework 4 is due on Wednesday, Oct 11, at the beginning of lecture. Solutions

Homework 5 is due on Wednesday, Oct 25, at the beginning of lecture. Solutions

Homework 6 is due on Wednesday, Nov 1, at the beginning of lecture. Solutions

Homework 7 is due on Wednesday, Nov 8, at the beginning of lecture. Solutions

Homework 8 is due on Wednesday, Nov 15, at the beginning of lecture. Solutions

Homework 9 is due on Wednesday, Nov 22, at the beginning of lecture. Solutions

Homework 10 is due on Wednesday, Nov 29, at the beginning of lecture. Solutions

The solution to the bonus problem can be found here.

__Midterm:__

The midterm is worth 30% of the course grade, and will be given in class on Wednesday October 18. Solutions are located here.
__The Final Exam:__

The final examination will be on Saturday, December 16 at 12 pm. The exam will be held at Dunn 101. The official schedule is posted at http://www.registrar.dal.ca/exam/. Only in very exceptional situations can we give make-up exams. Please work your holiday schedules around this.
__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.