Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
CSC236H5
1. Correctness [12 marks] Use the given python program to solve the questions below. def mystery(L): ''' Precondition: L is a list of 0s and 1s''' i = 0 j = -1 while i < len(L): if L[i] == 0: j += 1 L[i], L[j] = L[j], L[i] i += 1 return j >= 0 A. [2 marks] What will the list L look like after the function mystery is called? What does the function mystery return? B. [6 marks] Prove the following loop invariant Inv for the while-loop: Inv(i, j) = −1 ≤ j < i ≤ len(L) L[0:j+1] are all 0 L[j+1:i] are all 1 Note: The slicing operation L[x:y] is considered as the python slicing operation, thus it ranges from L[x] to L[y-1]. Page 2 of 4 CSC236H5 - Fall 2022 University of Toronto Mississauga Problem Set 3 Due: December 1st, 2022 C. [2 marks] State the postcondition for the function mystery. Then, use the invariant Inv to prove that this postcondition holds if the loop terminates. D. [2 marks] Prove that the loop terminates. Remember that this involves finding a variant and proving two things: (i) that the loop body is guaranteed to decrease the variant; and (ii) that the loop-condition and invariant together imply that the variant is a natural number greater than or equal to zero (i.e., ≥ 0). 2. Divide-and-Conquer [8 marks] Consider the following three problems: Subset Given a set S of n integers, and a target value k, does S have a subset that sums to k. Pair Given a set S of n integers, and a target value k, does set S have a pair of elements that sum to k? Tuple Given sets X and Y of integers, and a target value k, is there an x ∈ X and a y ∈ Y such that x+ y = k? You are tasked with the below questions. When computing the complexity, each binary operation costs one unit of time. Additionally, you must always justify your answer. A. [1 mark] Describe a brute force algorithm that solves the Subset problem. What is the worst-case time complexity of this algorithm? B. [1 mark] Describe a brute force algorithm that solves the Pair problem. What is the worst-case time complexity of this algorithm? C. [1 mark] Consider the following algorithm for the Pair problem: • Step 1: sort S in ascending order, and let S = s1, s2, ...sn • Step 2: calculate s1 + sn • Step 3: – if s1 + sn > k then the sum is too large, so shift sn down to sn−1 and go back to Step 2 – if s1 + sn < k then the sum is too small, so shift s1 up to s2 and go back to Step 2 – if s1 + sn = k return true What is the worst-case time complexity of the algorithm given above? Note: assume sorting takes Θ(nlog(n)) time. D. [2 marks] Design an algorithm using the same method as the Pair algorithm above to solve the Tuple problem. What is the worst-case time complexity of your algorithm? Note: assume sorting takes Θ(nlog(n)) time. E. [3 marks] Use a divide-and-conquer technique, in combination with your algorithm in step 4, to create an algorithm that solves the Subset problem. What is the worst-case time complexity of your algorithm?
CSC236H5 University of Toronto Mississauga Problem Set 3 3. Regular Expression [8 marks] Consider a typical vending machine that dispenses a person’s choice of candy after it has received a total of 25 cents in nickels (5 cents), dimes (10 cents), and quarters (25 cents). Consider a deterministic finite automaton (DFA) where the state represents the amount of money the machine has received, and the actions are the money being deposited into the vending machine. A. [2 marks] Assume the vending machine consumes any over payment (i.e., you will not receive any change back if you pay more than 25 cents). Explicitly model the system by defining Q (set of states), Σ (alphabet), q0 (initial state), and F (final states). You can use variables n, d, and q to represent nickels, dimes, and quarters. B. [2 marks] Draw the corresponding DFA for your model (as described in A.). C. [2 marks] Now, assume the machine is able to produce change. Once the machine receives 25 cents (or more), you can no longer add coins to it. Now, the final state is represented as “25 with x cents returned”. Explicitly model this new system by defining Q (set of states), Σ (alphabet), q0 (initial state), and F (final states).