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 5th 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, 4th 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