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).