CSC236 Fall 2021 PS3

General Instructions

Please read the following instructions carefully before starting the exercise.  They contain important information about general exercise expectations, exercise submis- sion instructions, and reminders of course policies.

● Your problem set is graded on both correctness and clarity of communication. 80% of your grade will be for correctness, and 20% will be for a clear, formally written proof.   This 20% grade will be based on only one of the questions, chosen at random.   Solutions to that question which are technically correct but poorly written will not receive full marks. Please read over your solutions carefully before submitting them.

● Each problem set may be completed in groups of up to three.   If you are working in a group for this problem set, please consult https://github.com/ MarkUsProject/Markus/wiki/Student-Guide for a brief explanation of how to create a group on MarkUs. Make sure to accept the invitation of your group mates before the deadline.  If you fail to do so, you will get a ZERO grade in this assignment.

● Solutions must be typeset electronically, using LATEX and submitted as a PDF with the correct filename. Other forms of submission will receive a grade of ZERO.

The required files for this problem set are ps3.pdf, ps3.tex, and socks.py.

● Problem sets must be submitted online through MarkUs. If you haven’t used MarkUs before, give yourself plenty of time to figure it out, and ask for help if you need it!

● Submissions made after the due date and time on MarkUs will have a number of grace tokens deducted in accordance with the syllabus. If you do not have enough grace tokens remaining, or you attempt to submit 72 hours or later after the due date, your submission will not be accepted.

Problem 1.

(6 Marks)

Consider the following sorting algorithm that I shamelessly stole from the internet (I even left the comments in there for you):

def  selection_sort(L):

"""

Pre:  L  is  a  list  of numbers

Post:  L  is  sorted  in non-decreasing  order

"""

#  i  indicates how many  items were  sorted

for  i  in  range(len(L)):

#  To  find  the minimum  value  of  the unsorted  segment      # We  first  assume  that  the  first  element  is  the  lowest min_index  =  i

# We  then use  j  to  loop  through  the  remaining  elements for  j  in  range(i+1,  len(L)):

# Update  the min_index  if  the  element  at  j  is  lower  than  it if  L[j]  <  L[min_index]:

min_index  =  j

#  After  finding  the  lowest  item  of  the unsorted  regions, #  swap with  the  first unsorted  item

L[i],  L[min_index]  =  L[min_index],  L[i]

The loop invariant for the outer loop is rather simple: 0 < i < len(L) and L[0 : i] is sorted. Clearly, once the loop finishes and i = len(L), this implies the postcondi- tion, and L is sorted.

State and prove the loop invariant for the inner loop that can be used to prove the loop invariant for the outer loop.  However, you do not need to prove how it is connected to the outer loop (though this is good practice).

Hint:  You should start by fixing a value for i, and assuming the outer loop in- variant holds for that i.  You should use this assumption in your proof for the inner loop invariant.

Problem 2.

(20 Marks)

Recall our friend Taylor and the messy room from Problem Set 2. Having found a shirt and pants, Taylor now needs to find a pair of matching socks.  Fortunately, Taylor was smart enough to ensure that there were only two types of socks to choose from, which are either blue or red.

Each sock is represented on the 2D Cartesian plane as a point (x,y).

1. Design an iterative algorithm that finds the two nearest matching colored  socks.   Zero  marks  will  be  given  for  a  recursive  solution. Your solution must have complexity O(m2 + n2 ) or better, where m is the number of blue socks and n is the number of red socks.  Submit your solution as a file named socks.py.

2. Determine the complexity of your algorithm.  Show your work.

3. Prove partial correctness of your algorithm using loop invariants for any loops in your code.

4. Prove that your algorithm will terminate.

def  socks(T):

"""

Pre:

T  is  a  list  of  all  socks  in  the  room.

A  sock  is  of  the  form  (C,x,y), where

C  is  a  string  representing  the  sock’s  color

(x,y)  are  the  coordinates  of  the  sock.

T has  at  least  two  socks  that match

Post:  Returns  a  tuple  (s1,s2)

containing  the  two matching  socks nearest  to  each  other """

Problem 3.

(13 Marks)

Consider this language:

L = {w e {0, 1}*  : w is a binary string with a value greater than 5}

1.  Give  a  5-state  DFA that  accepts this  language  L.  Draw the  state transition diagram with circles and arrows.  Clearly indicate the ini- tial  state and accepting  states,  and  label each transition with the proper symbol.

2.  Give a proper state invariant for each state of your DFA. Just write the invariants, no need to prove them.

3.   Using the proof technique from lecture, prove that your DFA has the minimal number of states for accepting L.

Note: You may use Google Draw or any other tool to draw DFAs and download the image as a png file. When you submit your ps3.tex, there is no need to submit the image separately. We will evaluate your diagram using ps3.pdf.

Problem 4.

(7 Marks)

Using the State Elimination algorithm, convert the following DFA to a regular expression. Visualize all steps of the algorithm by indicating the elim- inated state and the resulting partial regex. Make sure to write the complete regex at the end of your solution.

Note: Make sure to use the conventions of CSC236 when writing your regex. Any solutions that uses regex symbols from other courses or sources will automatically receive a grade of 0.

Problem 5.

(10 Marks) Use the subset construction algorithm from lecture to produce an equivalent DFA from the following NFA. Please show your work so that we know how each state is generated. Name your DFA states so that the link to the NFA states is clear; i.e.  you should have DFA states that look like {q0 , q1 }. You will need to show both the table and the diagram in your solution.  For full marks, you will need to show all intermediate steps of the algorithm (in tabular form is fine; the DFA diagram is required only for the final DFA).

The start state of this NFA is q0 ; the accepting (final) states are q0 , q1 , and q5 .