CSC110Y1F Term Test 1 PDF

University of Toronto Faculty of Arts and Science CSC110Y1F Term Test 1 Date: October 2, 2023 Duration: 100 minutes Instructor(s): T. Fairgrieve, S. Sharmin Aids Allowed: No aids allowed other t...

University of Toronto Faculty of Arts and Science CSC110Y1F Term Test 1 Date: October 2, 2023 Duration: 100 minutes Instructor(s): T. Fairgrieve, S. Sharmin Aids Allowed: No aids allowed other than instructor provided reference sheet Given Name(s): Family Name(s): Student Number (9 or 10 digits): UTORid (e.g., pitfra12): Please write your name and student number in the area above. This test has 5 questions. There are a total of 11 pages, DOUBLE-SIDED. This test covers Chapter 1–4 of the Course Notes. You may not use concepts (including programming language features) from outside these chapters. In particular, you may not use data classes or for loops in any solutions on this test. If you notice a potential error/typo, please report to an instructor, and we will confirm whether there is indeed an error and make a class-wide announcement if necessary. If you need more space for one of your solutions, use the provided blank page at the end of the test paper and indicate clearly the part of your work that should be marked. Question Q1 Q2 Q3 Q4 Q5 Total Mark Out of 11 7 5 5 4 32  CSC110Y1F , Fall 2023 Term Test 1 1. [11 marks] Short answer (a) [4 marks] Python data types and expressions. Assume each of the following Python statements and expressions is entered into the Python console in the given order. In the space following each expression, write the value that would be displayed. If evaluating an expression would cause an error, write ERROR and briefly explain why the error would occur. >>> L = ['c', 'a', 't'] >>> 'cat' in L >>> len(L) == len('cat') >>> d = {x: x * 3 for x in [1, 2, 3]} >>> d == {2: 6, 3: 9, 1: 3} >>> d >>> numbers_list = [x for x in range(5, 50)] >>> min(numbers_list) >>> max(numbers_list) >>> gl = "good luck, we're rooting for you!" >>> str.upper(gl) >>> 'good' in gl Please do not write below this line. There is extra space at the back of the test paper. Page 2/11 CSC110Y1F , Fall 2023 Term Test 1 (b) [3 marks] Function basics. Assume each of the following Python statements and expressions is entered into the Python console in the given order. In the space following each expression, write the value that would be displayed. If evaluating an expression would cause an error, write ERROR and briefly explain why the error would occur. >>> def f1(x: int) -> int:... """Docstring details omitted to save space."""... return x * 2... >>> f1(4) >>> f1(2) + f1(1) >>> x = 4 >>> f1(x + 1) >>> x >>> def f2(a: int, b: int) -> bool:... """Docstring details omitted to save space."""... r = f1(a) % b... return r == 0... >>> f2(3, 2) >>> r Please do not write below this line. There is extra space at the back of the test paper. Page 3/11 CSC110Y1F , Fall 2023 Term Test 1 (c) [4 marks] Logic. i. Let A be the set of all animals. We define the following predicates: IsFluffy(a) : “a is fluffy”, where a ∈ A IsCute(a) : “a is cute”, where a ∈ A Translate each of the following statements from English into symbolic logic. (i) All cute animals are fluffy. (ii) At least one cute animal is fluffy. ii. Translate each expression below from propositional logic into Python by using Python bool operators and the variable p. Assume that the Python variable p corresponds to the value of the propositional variable p (we have completed the first translation for you as an example). Do NOT simplify the given expressions. You may only use bool operators. No if- statements. Propositional logic Python p ∨ ¬p p or not p (¬(¬p)) ⇔ p ((p ∨ q) ∧ ¬p) ⇒ q Please do not write below this line. There is extra space at the back of the test paper. Page 4/11  CSC110Y1F , Fall 2023 Term Test 1 2. [7 marks] Programming - short answer. (a) [3 marks] Filtering collections / string methods Complete the following function body using a comprehension, filtering, a call to a string method and a call to a top-level built-in function. def get_uppercase(lst: list[str]) -> list[str]: """Return a sorted list containing all strings in the given lst that are uppercase. Hint: Use an appropriate string method to determine if a string is uppercase. >>> get_uppercase(['Good', 'CODE', 'is its own', 'BEST', 'documentation.']) ['BEST', 'CODE'] >>> get_uppercase(['An algorithm', 'must be seen', 'to be believed.']) [] """ Please do not write below this line. There is extra space at the back of the test paper. Page 5/11 CSC110Y1F , Fall 2023 Term Test 1 (b) [4 marks] If statements. Fill in the blanks to complete the following function according to the docstring provided. Rules: (1) Do NOT add in any extra lines. Fill in only the blanks provided – one line of code per blank. (2) Use the top-level built-in function(s) any() and/or all() within some parts of your code. def check_scores(scores: list[int]) -> str: """Return a message determined by values in scores. Given a list of scores, when all values in the list are greater than or equal to 100, return the string 'Great work'. Otherwise, if at least one of the values in the list is greater than or equal to 100, return the string 'Good work'. Otherwise, return 'Better luck next time'. Preconditions: - len(scores) > 0 >>> check_scores([115, 160, 130]) 'Great work' >>> check_scores([95, 115]) 'Good work' >>> check_scores([5, 10, 15, 20]) 'Better luck next time' """ check_all = check_at_least_one = if : return : return : return 'Better luck next time' Please do not write below this line. There is extra space at the back of the test paper. Page 6/11  CSC110Y1F , Fall 2023 Term Test 1 3. [5 marks] Function design recipe. Complete function get common numbers below by following the Function Design Recipe. Step 1 of the Function Design Recipe, example creation, has been completed for you. Based on the given examples, complete steps 2, 3, and 4 of the Function Design Recipe, as described next: Step 2: Fill in the function header (including the parameter and return data types). Assume all items in each collection have the same type. Specify the contained type as well, based on the examples below. Step 3: Write a good description of what the function does in the appropriate space, and Step 4: Write the body of the function in the appropriate space. (Hint: You may find it helpful to use built-in functions/methods.) (Note: You may only use Python statements covered in Chapters 1 – 4.) def get_common_numbers(L1: , L2: ) -> : """ >>> L1 = [10, 20, 30, 40, 50] >>> L2 = [60, 70, 80, 30, 10] >>> numbers = get_common_numbers(L1, L2) >>> numbers == {10, 30} True >>> L1 = [10, 20, 30, 40, 50] >>> L2 = [60, 70, 80] >>> get_common_numbers(L1, L2) set() """ Please do not write below this line. There is extra space at the back of the test paper. Page 7/11  CSC110Y1F , Fall 2023 Term Test 1 4. [5 marks] Debugging and testing. Consider the following function definition. def is_fibonacci(s: list[int]) -> bool: """Return whether list s contains the Fibonacci sequence of length len(s). The Fibonacci sequence of length n is the sequence of n numbers 0, 1, 1, 2, 3, 5, 8, 13,... Every number after the second is the sum of the previous two numbers. The first number must be 0 and the second number must be 1. Precondition: - len(s) > 2 >>> is_fibonacci([0, 1, 1, 2, 3, 5, 8, 13, 21]) True >>> is_fibonacci([0, 1, 4, 9, 16, 25, 36, 49, 64, 81]) False """ return all([s[i + 2] == s[i] + s[i + 1] for i in range(0, len(s) - 2)]) This implementation of is fibonacci passes the doctest examples, but actually has a subtle error, and so is not correct on all possible inputs to the function that meet the precondition. (a) [2 marks] Complete the unit test below to show an example valid input to is fibonacci that will fail because this implementation returns an incorrect value. def test_is_fibonacci_error() -> None: """A test case for is_fibonacci that reveals an error in the given implementation. If we ran this test with pytest and the current implementation, we would expect this test to *fail* because of the error in the function body. """ actual = is_fibonacci( ) # FILL THIS IN expected = # FILL THIS IN assert actual == expected Please do not write below this line. There is extra space at the back of the test paper. Page 8/11 CSC110Y1F , Fall 2023 Term Test 1 (b) [1 mark] Explain what is the error in the given implementation. Do not say how to fix the error in your response. (c) [2 marks] Write a correct function implementation for is fibonacci. You may make use of the code written at the start of this question, but will need to correct the error. def is_fibonacci(s: list[int]) -> bool: """Return whether list s contains the Fibonacci sequence of length len(s). The Fibonacci sequence of length n is the sequence of n numbers 0, 1, 1, 2, 3, 5, 8, 13,... Every number after the second is the sum of the previous two numbers. The first number must be 0 and the second number must be 1. Preconditions: - len(s) > 2 >>> is_fibonacci([0, 1, 1, 2, 3, 5, 8, 13, 21]) True >>> is_fibonacci([0, 1, 4, 9, 16, 25, 36, 49, 64, 81]) False """ Please do not write below this line. There is extra space at the back of the test paper. Page 9/11  CSC110Y1F , Fall 2023 Term Test 1 5. [4 marks] Proofs Let n, d ∈ Z. Recall the definition of the divisibility predicate: d | n : “∃k ∈ Z, n = dk ′′ , where n, d ∈ Z. Consider the following statement: ∀n ∈ Z, n | n2 + n (1) (a) [1 mark] Rewrite statement (1) by expanding the definition of the divisibility predicate |. (b) [3 marks] Prove statement (1). You can and should use the definition of divisibility given above. Please do not write below this line. There is extra space at the back of the test paper.Page 10/11 CSC110Y1F , Fall 2023 Term Test 1 Use this page for rough work. If you want work on this page to be marked, please indicate this clearly at the location of the original question. Total Pages = 11. Total Marks = 32. Page 11/11