Office: 534 Atkinson

Office Hours: Mon 10-11,Tu/Thr 4-5 or by appointment

E-mail: scull@yorku.ca

Course Description:

The course covers the algebraic and
combinatorial structures that are needed in computer science. We begin with a
review of functions, then discuss growth of functions, algorithms and
complexity. Other topics include elementary number theory, combinatorics,
recursive definitions and recurrence relations, and tree structures. **Preliminary
outline of sections: 1.6-1.8, 2.1-2.5, 3.2-3.4, 4.1-4.3,4.6, 5.1-5.4, 8.1,8.4**

AS/MA1090 3.0 or AS/Ma 1190 or any second
year math course without a middle digit 5.

**Lecture: **Tuesday, Thursday, 2;30-

, CLH A

Final Exam Saturday, Dec 7, 7-10 PM

Stuent Field House, Tait McKenzie

Exam is closed book, no
calculators.

Bring photo ID

Grades will be posted on web site
and 5^{th} floor of Atkinson early in the new year.

Topics to be covered:

Functions
, 1-1, onto, 1-1 correspondences1.6

Cardinality
, countable and uncountable sets 1.7

Big
-O 1.8

Divisibility
2.3

Euclidean
algorithm and applications 2.4

Congruences,
inverses, and CR Thm 2.5

Math
induction 3.2

Counting
problems 4.1-4.3, 4.6

Recurrence
relations and applications 3.3, 5.1

Solving
recurrence relations 5.2

Generating
functions 5.4

Midterm Solutions

**Tutorial**: __For week of Dec 2: Tue 12:30-13:30,
Thur 12:30-15:30. N 508 Ross. Also you can contact tutor at the Math lab (S525 Ross) on Dec 3
13:30-15:30____ __

Discrete Mathematics and its Applications by
Kenneth Rosen, 4^{th} edition, McGraw-Hill ,Inc

The final will be calculated as follows.

Quizes 20% (2)

Term Test 30%

Final 50%

Solutiones in PDF format below:

__ __

**Important information about exams:**. There are **NO** make up exams. Missed tests will count zero, except in extreme cases
such as illness. In such event, the final exam mark will be used for the
missing grade.

**The last date to withdraw w/o academic
penalty is Nov 8. Be sure to realistically evaluate your chances of success in
the course before then.**

**Dates for tests: Note change of dates **Quizzes:
October 1, November 12. Term Test: October 22. The final exam will be held
sometime in the final exam period from December 5-20. It will be a common exam
with section A.

**Homework is assigned but not collected.
Below are some suggested problems.**

** **Functions,
sequences, big-O notation (sec 1.6-1.7) **1.6 **5, 13, 19, 21, 26, 27, 31, 57; **1.7 **3,13, 17, 19, 21, 27, 31, 35, 37, 39, 41 **1.8 **1, 7, 9, 13, 17,21, 32

** **Algorithms and
complexity (sec 2.1-2.2) **2.1** 7, 9, 11, 25, **2.2 ****3, **5,
9a,b, 11a,19

** **Division and
Congruences (sec 2.3-2.4) **2.3 **5,
6, 9, 11, 12, 19, 21, 26, 29, 30, 31, 32, 34, 35, 36,** **37 **2.4 **1,
2, 3, 4, 5, 7, 9, 11, 12** **

Applications of number theory (sec 2.5) **2.5
**1, 3 ,5 ,6, 10, 11, 12, 21, 22, 23

** **Induction and
recursion sec (3.2-3.3) **3.2 **1, 2,
5, 13, 18, 21, 22, 25, 41, 47 **3.3**
1, 3, 26, 27, 31, 32

** **Recurrence relations and counting problems ( **5.1,4.1,4.2) 5.1 **1, 3, 9, 13, 17, 21, 23 **4.1 **1, 3, 11, 21**, **33, 37, 39 **4.2 **5, 7, 9,
13, 15, 29

** **Permutations and
Combinations (**4.3,4.6) 4.3 **9,11,13,
15, 19, 25, 27 **4.6 **3, 5, 9, 11, 15,
17, 21, 25, 27, 41

** **Solving recurrences
(**5.2) 5.2 **1, 3a-d, 7, 13, 23

** Binomial theorem and **Generating
functions (**4.3,5.4) 4.3 **35, 36, 39
**5.4** 1, 3a)b), 9a)b), 11a)b), 13,
15 ,19, 23, 33,

Trees TBA