Table of Contents

Course Information:

• Office hours during the exam period will only be by appointment. To set up an appointment, please e-mail me at alpremat@math.yorku.ca
• Note that the course outline has changed. In particular, the sections (or part of) from the textbook on Graphs and Trees covered in class are: 8.1 (just the definition of simple graph), 8.2 (Basic terminology, Special simple graphs, New graphs from old), 8.3 (Isomorphism of graphs), 8.4 (Paths, Connectedness in undirected graphs, Paths and isomorphisms) and some of 9.1.

Exam Information:

The Final Exam will be on Saturday, April 22nd 2006 at 19:00 (7 PM) in SLH E, SLH F. It will be 3 hours long.

IMPORTANT: There will not be any material on the final exam from section 2.1 (Algorithms) and you will not be asked to calculate the complexity of specific algorithms. However, you should understand what it means to say, for example, that an algorithm has polynomial complexity.

This term we covered the following sections from the textbook. We did not cover each of these sections entirety. Please refer to your notes and the suggested homework below.

Functions: one-to-one, onto (section 1.8).

Algorithms and their complexity (Sections 2.1, 2.3)

Growth of functions, big-O (Section 2.2)

Integers and division, division algorithm, Euclidean algorithm, etc.. (Sections 2.4, 2.5 and 2.6)

Sequences, Cardinality and Mathematical Induction. (Sections 3.2 and 3.3)

Recurrence relations (3.4, 6.1 and 6.2).

Counting principles. Pigeonhole principle, permutations and combinations (Sections 4.1, 4.2, 4.3, 4.4 and 4.5).

Graphs and trees. Sections 8.1, 8.2, 8.3, 8.4 and 9.1. Main topics: Handshake Theorem, isomorphism of graphs, definition of trees.

Homework:

• Section 1.8 - 5, 7, 12, 13, 17, 19, 21, 24, 25, 27, 35, 39, 49, 55, 59, 65 .
• Section 2.1 - 1-16 (odd numbered questions).
• Section 2.2 - 1-5 (odd numbered questions), 9-21 (odd numbered questions), 33.
• Section 2.3 - 7, 9, 13, 15, 23, 27.
• Section 2.4 - 7-19 (odd numbered questions), 29, 31, 37, 39, 41, 43, 44, 45 and 46.
• Section 2.5 - 21.
• Section 2.6 - 1 and 13.
• Section 3.2 - 3, 13, 15, 19, 21, 31-35.
• Section 3.3 - 3, 5, 7, 8, 13-25 (odd numbered), 29, 33, 51 and 53.
• Section 3.4 - 1-9 (odd numbered) and 13.
• Section 6.1 - 1-13 (odd numbered), 17, 19, 23-29 (odd numbered), 41 and 43.
• Section 6.2 - 1-7 (odd numbered), 13, 15 19 and 21.
• Section 4.1 - 1-33 (odd numbered), and 37-41 (odd numbered).
• Section 4.2 - 1-9 (odd numbered), 13-19 (odd-numbered), 25 and 29.
• Section 4.3 - 1-41 (odd numbered).
• Section 4.5 - 1-31 (odd numbered), 37-41 (odd-numbered) and 45.
• Section 4.4 - 1-15 (odd numbered), 19, 21 and 33.
• Section 8.1 - 11.
• Section 8.2 - 1-5, 25 (a), (b), (c) and (e), 26-29, 31-45 (odd-numbered).
• Section 8.3 - 35, 37, 39, 40, 41, 42, 43 and 55.
• Section 8.4 - 1, 3, 5 and 15.
• Section 9.1 - 1-9 (odd numbered), 17, 19, 31, 45 adn 47.

Exams Solutions:

Last modified: April 3rd, 2006