tutorial section COMP1805-BCM Discrete Structures I Grade / 40 Assignment 3 Due Date: March 10, 2016 Time Due: Before 3:00pm in the drop box in HP 3115 Student Number Student Name Write down your name and student number on every page. You must have a cover page that clearly states your name, student number, course number and tutorial section. If you do not have a cover page with this information, your assignment will not be marked. The questions should be answered in order and your assignment sheets must be stapled, otherwise the assignment will not be marked. Every part of every question is worth 2 marks. The grading scheme for each question is 2 for correct answer, 1 for an answer that is not completely correct and 0 otherwise. 1. Draw the graph of the function f (x) = 3x + 5 where the domain is {x | x is an integer and 3 x 4} 2. Let f and g both be functions from reals to reals. Let f (x) = 3x 5 and g(x) = x2 4. Dene what is: (a) f g (b) g f (c) (f g) f 3. Compute the closed form for the following (e.g. the closed form for (a) (b) (c) (d) (e) (f) (g) (h) n i=25 5, where n is a positive n i=1 6(i + 3) n 2 i=1 (3i + 2i 4) 57 j=33 31 n 2 j=1 (2j n + 3) n i i=1 j=1 (i + j) n n n i=1 j=1 k=1 (3i 1) n n j=i 2j i=1 n i=1 i is n(n + 1)/2.): integer whose value is at least 25. 4. Determine whether or not the following are true and provide a derivation explaining your answer. The domain of the functions of n below is the positive real numbers. For convenience, you may assume that the logs are in the base of your choice, but you should specify what base you are using in your derivation. (a) (2n 6)2 is (n2 ) (b) 9n2 7n + 8 is O(n2 ). (c) n3 /27 5n2 log2 n is (n2 ). (d) 5n4 3n3 log3 n 3n2 + 6n log n is (n4 ) (e) 7n2 10n 14 is O(n3 ). (f) 3n2 n is (1). (g) 9n5/2 2n2 is O(n3 log n). (h) 5n/6 7 is (n)