CSC236 Assignment 3

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) : L is a list of integers. : 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 ∈ Q and a closed interval I = [a, b], a, b ∈ Q, we say that I covers x if a ≤ x ≤ b. Given a set of points S = {x1, . . . , xn} and a set of closed intervals Y = {I1, . . . , Ik} 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: August 3 rd, 2018 Algorithm 2 Cover(S, Y ) : S is a finite collection of points in Q. Y is finite set of closed intervals which covers S. : Return a subset Z of Y such that Z is the smallest subset of Y which covers S. 1: L = {x1, . . . , xn} ← 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 L over the alphabet Σ = {0, 1} construct a regular expression R and a DFA M such that L(R) = L(M) = L. Prove the correctness of your DFA. 2 CSC236: Introduction to the Theory of Computation Due: August 3 rd, 2018 Part (1) [8 marks] Let L1 = {x ∈ {0, 1} ∗ : the first and last charactes of x are the same}. Note: ϵ /∈ L since ϵ does 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 = {x ∈ {0, 1} ∗ : x only contains blocks of length at least three}. 3