a$.2\mathrm{.}5+2\mathrm{.}5$ Please write the following two functions for it$.$ Also describe their time complexity. A is

globally$/$objectively accessible to the two functions

def setValue$(x,y$ : # sets a value at row $x$ and column y in $A$

def subRectangleSum$($x$1,$ y$1,$ x$2,$ y$2)$: # calculates the sum value of rectangle encased #within the

two given point $(x1,y1)$ and $($x$2,$ y$2).$ Eg:

$ifA=\left[\begin{array}{c}1212\\ 2121\\ 1212\\ 2121\end{array}\right]$

Then subRectangleSum $(1,1,2,3)$ returns $9,$ subRectangleSum $(0,0,2,1)$ returns $9.$

Write pseudocode. Explanation of your algorithm and clearly stating and explaining the complexity

are mandatory. b$.[5]$ Now very carefully consider this condition. The queries made upon A are in an indefinite stream,

such that you have to execute the two functions repeatedly. If$,$ for example, SubRectangleSum$()$

runs in $O(n^3)$ time, that time would be repeated for as long as you have your stream of query

executing. Your goal is to bring the time complexity of the function to $O(1).$ You can use an extra

matrix $($also globally available$)$ of the same size. You can also write helper functions to aid you in

the program. Write the new algorithm for helper function and SubRectangleSum$().$ The conditions

of writing pseudocode and explanation stand as always.Let

$\backslash$Sigma

$=$

$\{$

$$

$,$

$$

$,$

$$

$,$

$...$

$,$

$$

$\}$

$\backslash$Sigma $=\{$a$,$b$,$c$,...,$z$\}$ denote the alphabet, and let

$$

$$

$\backslash$Sigma

$$

S$\backslash$Sigma

$$

be the set of all words in the English language. In the ScriptoContinua problem, you are given a string

$$

in

$\backslash$Sigma

$$

s in $\backslash$Sigma

n

$($that does not have any spaces or punctuation marks$)$ and you must output True if there exists a sequence of words

$$

$1$

$,$

$...$

$,$

$$

$$

in

$$

w

$1$

$$

$,...,$w

m

$$

in S such that

$$

$=$

$$

$1$

$$

$2$

$$

$$

$$

s$=$w

$1$

$$

w

$2$

$$

$$w

m

$$

is the concatenation of the words

$$

$1$

$,$

$...$

$,$

$$

$$

w

$1$

$$

$,...,$w

m

$$

$,$ and False otherwise.

For example, for the input

$$

$=$

thisstringisasequenceofwordswrittenwithoutanyspaces

s$=$thisstringisasequenceofwordswrittenwithoutanyspaces

the valid solution is True since we can partition

$$

s into the sequence of $11$ words:

$$

$=$

this$$string$$is$$a$$sequence$$of$$words$$written$$without$$any$$spaces

s$=$this$$string$$is$$a$$sequence$$of$$words$$written$$without$$any$$spaces

with

$$

$1$

$,$

$$

$2$

$,$

$...$

$,$

$$

$11$

in

$$

w

$1$

$$

$,$w

$2$

$$

$,...,$w

$11$

$$

in S$.$

Design a dynamic programming algorithm for solving the ScriptoContinua problem. In your solution, you can assume that you have access to an algorithm IsWord that, on any input

$$

in

$\backslash$Sigma

$$

w in $\backslash$Sigma

$$

$,$ outputs True if

$$

in

$$

w in S and False otherwise, and has time complexity

$\backslash$Theta

$($

$1$

$)$

$\backslash$Theta $(1).$ You can create a list of words of approximately $500$ words to look through $($for this you can use a Python dictionary$).$ You should aim for an algorithm with runtime

$$

$($

$$

$2$

$)$

O$($n

$2$

$),$ aside from the word look$-$up$.$ You do not need to worry about the grammar of the resulting sentence.

Modify the algorithm in part $($a$)$ so that when the answer is True, the algorithm also outputs

$$

$1$

$,$

$...$

$,$

$$

$$

in

$$

w

$1$

$$

$,...,$w

m

$$

in S for which

$$

$=$

$$

$1$

$$

$2$

$$

$$

$$

s$=$w

$1$

$$

w

$2$

$$

$$w

m

$$