Discrete Structures in Computing (II)

CIS*2910 (Fall 2012)

Instructor: Fei Song (Reynolds 215, ext. 58067)

Email: fsong@uoguelph.ca

Office Hours: Monday, Wednesday, and Friday: 4:00 – 5:00 pm in Instructor’s office

Lab Location: MacKinnon 236

Teaching Assistants: Tao Xu and A.N.K. Zaman

Overview

This course is a further introduction to discrete structures and formal methodologies used in computer science, including sequences, summations, recursion, combinatorics, discrete probability, and graph theory. It is a subsequent course to CIS*1910 and is often taken together with CIS*2520. The three together help lay a solid mathematical foundation so that you can understand the related concepts and theories in other computer science courses in depths.

Preequisite(s): CIS*1500 and CIS*1910 or ENGG*1500

Evaluation

Six assignments (6 x 6% = 36%)

Two midterms (2 x 12% = 24%)

One final exam (40%)

Textbook and Course Website

Kenneth H. Rosen. Discrete Mathematics and its Applications. Seventh Edition.

McGraw-Hill, 2012.

Course website: http://moodle.socs.uoguelph.ca/

Topics to be Covered

· SEQUENCES:

- sequences, monotonic/arithmetic/geometric sequences;

- summation notation, properties, double summation

· RECURSION:

- explicitly/recursively defined sequences/sets;

- from recursive to explicit and vice versa;

- Fibonacci sequences

· COUNTING:

- product/sum rules, inclusion‐exclusion principle, pigeonhole principle;

- permutations, lexicographic order relation;

- combinations;

- binomial coefficients/theorem, Vandermonde’s/Pascal’s/etc. identities;

- combinatorial proofs

· DISCRETE PROBABILITY:

- probability mass function, probability measure;

- conditional probability, independent/mutually exclusive events, Bayes’ theorem;

- integer random variables, expectation, law of large numbers

· GRAPHS AND TREES:

- undirected/directed graphs;

- representations;

- paths/cycles, Euler/Hamilton paths, Eulerian/Hamiltonian graphs;

- connected/complete/planar/bipartite graphs, chromatic number, four colour theorem;

- trees (defined as particular graphs) and forests;

- subgraphs, spanning trees/forests

Policies

· Lab tutorials are synced with the six assignments and will provide additional examples and question-answering. You are required to attend the labs as much as possible since they will also serve as office hours for the TA(s).

· Late assignments are not accepted for grading and will be given a mark of zero. You will be further ahead to submit a partially finished assignment on time than to spend effort asking for an extended submission date. Unless otherwise specified, assignments are due on or before the midnight of the due date.

· Any requests for the remarking of assignments and midterms should be submitted to the TA(s) by emails within 5 business days so that an appointment can be made between you and the TA(s). Any later requests will not be considered.

· Academic misconducts such as cheating on exams, plagiarism, and submitting the same material in two different courses without a written permission are not tolerated at the University of Guelph. You are expected to be familiar with the rules specified on Academic Misconduct in the Undergraduate Calendar at the University of Guelph.

· If you are unable to meet any course requirement due to illness or other compassionate reasons, please advice the instructor in writing ahead of time, followed by appropriate documentation, so that an alternative may be arranged.