• March 10th, 2011, 09:49 PM
Honours
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:
Code pseudo:

```boolean 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)} }```
Study carefully John's algorithm and
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.
• March 10th, 2011, 09:54 PM
copeg
And what exactly is the problem and/or question? I hope you aren't relying on us to answer the bottom 5 points for you, as this is your job. If you have a specific question about the work, by all means ask and we can try to help
• March 10th, 2011, 10:39 PM
Honours
No, i am not. I am new to java and this algorithm thing. I just need someone to answer the first and second questions for me with some details why the algorithm is flawed. i need to understand what is wrong with it. Rightnow i don't understand it.
• March 11th, 2011, 12:46 PM
KevinWorkman
You've pretty much just described your homework assignment. That's not how this works. What do you think is the answer? What have you done to try to figure it out? Have you tried running the code and trying it yourself?

Also, posts with titles like yours tend to be ignored. Everybody here needs help. Yelling "please" won't help you- in fact, it will hurt your chances of getting help.
• March 11th, 2011, 02:51 PM
Honours
Thanks. I got it done already.
• March 13th, 2011, 08:03 PM
Spotlight