Consider the problem description below:

John proposed an algorithm balancedBracketsByCounting(String s), as follows, that takes a string

as an input and checks whether the brackets \[" and \]" in the string are matched correctly. He

claimed that his algorithm is correct. For example, balancedBracketsByCounting("[x][[xy]]")

would return true but balancedBracketsByCounting("[[x[y]]") would return false.

This is John's algorithm:

Study carefully John's algorithm andboolean balancedBracesByCounting(String s) { numOfLeftBracketRound = 0; numOfRightBracketRound = 0 numOfLeftBracketSquare = 0; numOfRightBracketSquare = 0 balanced = true while (not at the end of the s) { if (the next character is an open bracket '(' { numOfLeftBracketRound++ } else if (the next character is an open bracket '[') { numOfLeftBracketSquare++ else if (the next character is a close bracket ')' { numOfRightBracketRound- - } else if (the next character is a close bracket ']') { numOfRightBracketSquare- - } } return {(noOfLeftBracketRound==noOfRightBracketRound) and (noOfLeftBracketSquare==noOfRightBracketSquare)} }

1. Explain why the algorithm balancedBracketsByCounting(String s) is

awed.

2. Demonstrate one

awed case in which, with the aid of an example of input, the algorithm may

return a true for a wrong match.

3. Identify as many errors or weaknesses as possible in John's algorithm, and correct or improve

them. Summarise your results in a table

4. Derive an alternative algorithm that would return correct answers. Show all your work.

5. Implement your algorithm, referring to the submission requirements.