Discrete Mathematical Structures

Course Outline, Fall 2002

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

Prerequisites:

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

Textbook:

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:

Quiz 1a Solutions-

Quiz1b Solutions

Quiz2a Solutions

Quiz2b Solutions

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