Assignment 3 Solution

Question 1.    [16 marks]

Given a list L, a contiguous sublist M of L is a sublist of L whose elements occur in immediate succession in L. For instance, [4; 7; 2] is a contiguous sublist of [0; 4; 7; 2; 4] but [4; 7; 2] is not a contiguous sublist of [0; 4; 7; 1; 2; 4].

We consider the problem of computing, for a list of integers L, a contiguous sublist M of L with maximum possible sum.

Algorithm 1 M axSublist(L)


<precondition>: L is a list of integers.

<postcondition>: Return a contiguous sublist of L with maximum possible sum.



Part (1)    [5 marks]

Using a divide-and-conquer approach, devise a recursive algorithm which meets the requirements of M axSublist.

Part (2)    [8 marks]

Give a complete proof of correctness for your algorithm. If you use an iterative subprocess, prove the correctness of this also.

Part (3)    [3 marks]

Analyze the running time of your algorithm.



Question 2.    [18 marks]

For a point x 2 Q and a closed interval I = [a; b], a; b 2 Q, we say that I covers x if a x b. Given a set of points S = fx1; : : : ; xng and a set of closed intervals Y = fI1; : : : ; Ikg we say that Y covers S if every point xi in S is covered by some interval Ij in Y .

In the “Interval Point Cover” problem, we are given a set of points S and a set of closed intervals Y . The goal is to produce a minimum-size subset Y ′ Y such that Y ′ covers S.
Consider the following greedy strategy for the problem.















1
CSC236: Introduction to the Theory of Computation    Due:  




Algorithm 2 Cover(S; Y )


<precondition>:

S is a finite collection of points in Q. Y is finite set of closed intervals which covers S.

<postcondition>:
Return a subset Z of Y such that Z is the smallest subset of Y which covers S.

    1: L = fx1; : : : ; xng   S sorted in nondecreasing order

    2: Z   ∅
    3: i   0
    4: while i < n do

    5: if xi+1 is not covered by some interval in Z then
    6: I   interval [a; b] in Y which maximizes b subject to [a; b] containing xi+1
    7: Z:append(I)

    8: i   i + 1
    9: return Z



Give a complete proof of correctness for Cover subject to its precondition and postcondition.



Question 3.    [10 marks]

The first three parts of this question deals with properties of regular expressions (this is question 4 from section 7.7 of Vassos’ textbook). Two regular expressions R and S are equivalent, written R S if their underlying language is the same i.e. L(R) = L(S). Let R; S, and T be arbitrary regular expression. For each assertion, state whether it is true or false and justify your answer.

Part (1)    [2 marks]

If RS    SR then R    S.

Part (2)    [2 marks]

If RS    RT and R ̸    ∅then S    T .

Part (3)    [2 marks]

(RS+R) R    R(SR+R) :

Part (4)    [4 marks]

Prove or disprove the following statement: for every regular expression R, there exists a FA M such that L(R) = L(M ). Note: even if you find the proof of this somewhere else, please try to write up the proof in your own words. Just citing the proof is NOT enough.


Question 4.    [16 marks]

In the following, for each language R and a DFA M such that L(R) =

L over the alphabet = f0; 1g construct a regular expression L(M ) = L. Prove the correctness of your DFA.

2

CSC236: Introduction to the Theory of Computation

Due:  
Part (1)

[8 marks]



Let L1 =
f
x
2 f
0; 1
g

:  the first and last charactes of x are the same
g
. Note: ϵ = L since ϵ does









2
not have a first or last character.


Part (2)

[8 marks]




Let a block be a maximal sequence of identical characters in a finite string. For example, the string 0010101111 can be broken up into blocks: 00, 1, 0, 1, 0, 1111. Let L2 = fx 2 f0; 1g : x only contains blocks of length at least threeg.





















































3