It is a writing question. It is not a programming question.

4. A string w of parenthesis '(' and ')' is balanced if it satisfies one of the following conditions: w is the empty string: w = (-2) for some balanced string r; w=ty for some balanced strings r and y. For example, the string w = (00)000))) is balanced, because x = ((0)0) and y = (000))) are balanced. (a) Describe (English description + pseudocode) and analyze correctness + runtime) an algorithm to determine whether a given string of parenthesis is balanced. (b) Describe (English description + pseudocode) and analyze (correctness + runtime) a greedy algorithm to compute the length of a longest balanced subsequence of a given string of paren- thesis. The input to each of the above problems is an array W[1..n] such that for each i we have W[i] ='( or W[i] =')'. Both of the algorithms should run in O(n) time