COMP1805ABC (Winter 2024) -“Discrete Structures I” Assignment 4 of 5 - Due Thursday March 21, 23:59 Carleton University • Your assignment should be typed and submitted online as a single .pdf file, created using Google Docs, Microsoft Office, or LaTeX. Handwritten submissions (including those that have been scanned or photographed) are not acceptable and will receive a mark of zero. Compressed files (e.g., "zip", "rar”, “tar", etc.) or documents in another format (e.g., "doc”, “docx”, “rtf”, “txt", "jpg", etc.) will be penalized and may receive a mark of zero. • When you submit your assignment to Gradescope, you MUST assign questions to pages. For every question that is not assigned to a page or is assigned to the wrong page, you will receive a penalty of 50% of the question mark. For example, if Q2, worth 10 points, was misassigned, then your max grade for Q2 will be 5 points. • Late assignments will be accepted for up to 12 hours after the deadline without penalty. No late assignments will be accepted after that. • Write down your name and student number on every page. You can use header settings for that. • Start each question on a new page. The questions should be answered in order. • Each response should begin with a principal answer (for example, the final formula, True/False, Yes/No, etc.) followed by your explanation/solution starting from a new line. • You need to show your work, but also keep your solution precise, concise and clear. A correct solution will receive partial mark if it is not accompanied by the work required to reach it. • If you do not know how to produce some formula or indentation, please ask the teaching team. We will help you. Poor formatting will be penalized. Examples are: no indentation; no spaces between parts/questions; no question numbers; specifying negation (¬) by "not", "-", etc; writing compliment sign (A) as anything but the proper sign, or letting it hover a line (or more) above (A). • Marks for every question are specified at the beginning of every question. The grading scheme for each question is “full marks" for correct answer, “half marks” for an answer that is not completely correct and 0 otherwise. 1. (12pts) What are the terms a10 and a11 of the sequence {an}, where an equals (a) 5n (b) 8+2n (c) 9 (d) [n/2]+[n/2] (e) 2n + (-2)n (f) (-1)+nn 2. (12pts) Below you can see lists of integers. For each of these lists, provide an explicit formula {an} (but not a recurrence relation) that generates the terms of an integer sequence that begins with the given list. Don't forget to specify the possible values of n. (a) −5, 5, −5, 5, —5, 5, —5, 5, —5, . . . (b) 6,11,16,21, 26, 31, 36, 41, 46, . . . (c) 3, 6, 12, 24, 48, 96, 192, 384, 768, ... (d) 3, 6, 11, 18, 27, 38, 51, 66, 83, 102, ... COMP1805ABC (Winter 2024) -“Discrete Structures I” Assignment 4 of 5 - Due Thursday March 21, 23:59 Carleton University 3. (6pts) Express in sigma notation the sum of the first 100 terms of the following series: (a) 3+3 +3 +3 + ... (b) 6+9+12+ 15 + 18+ ... 4. (12pts) Compute the exact values of the following sums. You need to show each step in your derivation and simplify the final answer. See sample solution in part (d). 90 (2) Σ55 8 (b) Σ-1 (2 - 1) (c) Σ1Σ-30 (6 – 3) (d) 1 (6k2-8k) Solution: n n 6k2 8k = n k=1 IM ³ n n -8k n 8 k n k=1 = = = = 6 n(n+1)(2n + 1) n 6 (n+1)(2n + 1) — 4n - 2n23n+1-4n - 4 2n2-n-3 8 n(n + 1) n 4 2 - 5. (5pts) Let's play a game. We start with a list of numbers 1, 2, 3, ..., 2024. We take turns by picking two numbers from the list, say a and b, and removing them. Then, we insert exactly one of the numbers |a – b❘ or a+b into the list. Note that the length of the list decreases by one after each change. The game stops when only one number is left on the list. Prove that the final remaining number is even. 6. (4pts) Suppose that you have three different algorithms, A,B, and C, that solve the same problem. To solve a problem of size n, the first algorithm uses exactly a basic operations, the second algorithm uses exactly b basic operations, and the third algorithm uses exactly c basic operations. As n grows, which algorithm uses fewer operations for the following values of a, b and c? In other words, which algorithm is faster for big values of n. n5/2 (a) a = n³, b = n² logn, c = n³ (b) a = n² 2n, b = n^, c = n! 7. (10pts) Provide an algorithm for each of the following parts. You may present it in pseudocode or as a step-by- step procedure in plain English. Additionally, indicate the algorithm's runtime using big-O notation. .... (a) Describe an algorithm that takes as input a sequence of distinct integers a1, a2, an (for n ≥2) and determines if the integers are sorted in increasing order. (b) You are given an array of integers, where each element represents the stock price on a particular day. Write an algorithm that calculates the maximum profit that can be obtained by buying and selling a single share of the stock. Note that you cannot sell a stock before you buy one. For example, given the array 7, 1, 5, 3, 6, 4, the maximum profit of 5 can be obtained by buying on day 2 (price = 1) and selling on day 5 (price = 6). COMP1805ABC (Winter 2024) -“Discrete Structures I" Assignment 4 of 5 - Due Thursday March 21, 23:59 Carleton University 8. (12pts) Suppose that f(n) is (n) and g(n) is O(n²). Prove or disprove the following statements. Note that to disprove a statement, you need to provide a counter-example. (a) f(n) is O(n). (b) f(n) is (1). (c) f(n) is O(n²). (d) g(n) is (n). (e) g(n) is (n³). (f) g(n) is O(n³). 9. (6pts) Suppose that Algorithm A has runtime complexity O(n²) and Algorithm B has runtime complexity O(nlogn), where both algorithms solve the same problem. (a) Assume you started both algorithms simultaneously, and assume that n = 50. Is it possible for Algorithm A to terminate before Algorithm B? (b) Is it possible, that actual running time of A and B is the function n? (c) Suppose we also know that Algorithm A has runtime complexity (n²), and Algorithm B has runtime complexity (nlogn). In other words, runtimes of A and B are O(n²) and O(n log n), respectively. How do the algorithms compare when n is very large? 10. (21pts) Determine whether or not the following are true. If true, then provide a derivation showing why. If false, then provide a derivation showing why. For your proofs use definitions of asymptotic notations. Notice, in your solutions you are not allowed to use limits. 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) 32 is (1). (b) (2.2) is O(2n). (c) 2.2 is O(2n). (d) 3n2n5 is O(n²). (e) (n/5)³ – 2n² — n log n is O(n²).