CSC236H5 - Fall 2022
University of Toronto Mississauga
Problem Set 3
Due: December 1st, 2022
CSC236: Problem Set 3
Due on Thursday December 1st, 2022 by 5pm ET
Andrea Mitchell, Ahmed Ashraf, and Michael Liut
Posted on Thursday, November 17th, 2022 || Version: 1.0
Problem Set Instructions
Please read the following instructions carefully before starting the assignment. They contain important infor-
mation about expectations, requirements, exercise submission instructions, and reminders of both course and
university policies.
Grading
• Your problem set is worth 13% of your final grade in this course, with the following distribution:
➔ 12% (of the overall 13%) is graded using the following breakdown:
80% is allocated to correctness (these marks are noted in this document)
20% is allocated to writing/communication (these marks follow the writing rubric)
By writing/communication, we expect clear and formally written proofs. Solutions which are techni-
cally correct but poorly written will not receive full marks. Please read over your solutions carefully
before submitting them.
➔ 1% (of the overall 13%) is graded based on your submission using our VoiceEx (Voice and Text
Explanations) platform. More details will follow once the system is online and operational – there
will be a second handout with additional instructions (and a separate/different due date) once the plat-
form is online and operational.
Requirements
Problem Sets, like everything else in this course, are to be completed individually. This means that you are
forbidden from communicating, working with, and discussing these problem sets with anyone (except for the
CSC236 Teaching Team). Please be aware of UofT’s Academic Integrity Policies. Please refer to the course
syllabus for additional details on this and the “Minimum Standards for Submitted Work”
Submission
All submission are required to be written in LATEX. We would strongly suggest using Overleaf as a means of
compiling and editing LATEX documents. However, you may use other programs that help compile LATEX, but you
are not permitted to use another word processor (e.g., Microsoft Word, Apple Pages, Google Docs, etc.).
All files are to be submitted using the MarkUs platform (https://markus108.utm.utoronto.ca/markus22f/courses).
You may submit as many times as you like, in fact you are encouraged to do so! If you have not used MarkUs be-
fore, give yourself plenty of time to figure it out, and ask for help if you need it! Please ensure your answers are typed
and submissions is clearly legible/understandable. Your submissions should be written in English and communi-
cated clearly, free from spelling and grammatical errors.
The requiorange files for this problem set are ps3.pdf and ps3.tex.
Page 1 of 4
CSC236H5 - Fall 2022
University of Toronto Mississauga
Problem Set 3
Due: December 1st, 2022
Policies
Late Submissions
Late Problem Sets will be deducted 15% per day of lateness. After three (3) calendar days, the Problem Set
will no longer be accepted. If you do not submit within the 3-day period (i.e., you have no submission) you get a
ZERO (0%) for the entire Problem Set (i.e., you forfeit 13% of your grade).
Mismatching or Missing Files
You are requiorange to submit the LATEX file that matches the corresponding PDF. If mismatched files or not both
files are submitted, you will receive a ZERO (0%) for the entire Problem Set (i.e., you forfeit 13% of your grade).
Furthermore, an administrative deductions will be applied if the teaching staff need to compile or recompile your
submission. If you did not upload your file correctly (i.e., it is not readable) you will receive a ZERO.
Academic Integrity
Academic integrity is essential to the pursuit of learning and scholarship in a university, and ensuring that a degree
from the University of Toronto Mississauga is a strong signal of each student’s individual academic achievement.
As a result, UTM treats cases of cheating and plagiarism very seriously. The University of Toronto’s Code of
Behaviour on Academic Matters outlines behaviours that constitute academic dishonesty and the process for
addressing academic offences. See the course syllabus and UofT polcies for further details.
Please note that this course will extensively verify that the work you submit is your own, this includes utilizing
software, programs, and other resources at our disposal for plagiarism and collusion detection.
Problem Set Exercises
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?
Page 3 of 4
CSC236H5 - Fall 2022
University of Toronto Mississauga
Problem Set 3
Due: December 1st, 2022
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).
D. [2 marks] Draw the corresponding DFA for your model (as described in C.).
Note: for both of your DFA drawings (B. and D.) you may use colours (with a legend) to label the tran-
sitional arrows, otherwise, you must annotate each label; as this will be used to identify “how” you tran-
sition from one state to another. Additionally, we will permit you to hand draw the diagram and include
it in your LATEX file, however, if you would like to draw it in LATEX, you can use the following tool:
https://madebyevan.com/fsm/. We encourage you to try this tool!
Page 4 of 4