-
Notifications
You must be signed in to change notification settings - Fork 168
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Pseudocode for Bursting Balloons #14
Comments
i would like to work on this project |
Sure, go ahead. Make sure to share your approach first. |
My first approach using Dynamic Programming and more specifically divide and conquer techique
} |
Looks good. You can start working on the pseudocode now. |
This is my attempt for the pseudocode % Set the Page Layout
\documentclass[12pt]{article}
\usepackage[inner = 2.0cm, outer = 2.0cm, top = 2.0cm, bottom = 2.0cm]{geometry}
% Package to write pseudo-codes
\usepackage{algorithm}
% Remove the 'end' at the end of the algorithm
\usepackage[noend]{algpseudocode}
% Define Left Justified Comments
\algnewcommand{\LeftComment}[1]{\Statex \(\triangleright\) #1}
% Remove the Numbering of the Algorithm
\usepackage{caption}
\DeclareCaptionLabelFormat{algnonumber}{Algorithm}
\captionsetup[algorithm]{labelformat = algnonumber}
\newcommand{\To}{\textbf{ to }}
\begin{document}
\begin{algorithm}
\caption{Find the maximum coins you can collect by bursting the balloons wisely.}
\begin{algorithmic}[1]
\Require An array of Balloons as input
\Statex
\Function{$Max\_Coins$}{$BArray$}
\Statex
\State $BalloonArraylength \gets BArraylength+2$
\State $BalloonArray[0] \gets 1$
\Comment{Initialise the top and bottom of the BalloonArray to 1}
\State $BalloonArray[BalloonArraylength-1] \gets 1$
\For{$i=1 \To BalloonArraylength-2$}
\Comment{Initialise the rest of BalloonArray by indexing it to Barray}
\State $BalloonArray[i] \gets Barr[i]$
\EndFor
\State $MCarray[i][j] \gets 0 \hfill \forall i \hfill \forall j$
\Comment{Initialise the MaxCoin array}
\Statex
\Comment{Divide and Conquer technique , defining subproblems by the last balloon to burst}
\For{$k = 3\To ArrayBalloonlength$}
\Comment{Complexity O($n^3$)}
\For{$left =1 \To ArrayBalloonlength-k$}
\State $right \gets left+k$
\For{$i=left+2\To right$}
\Comment{i Balloon is the last balloon we burst}
\State $MCarray[left][right] \gets MAX(MCarray[left][right], BalloonArray[left] * BalloonArray[i] * BalloonArray[right] + MCarray[left][i] + MCarray[i][right])$
\EndFor
\EndFor
\EndFor
\State \Return{$ MCarray[0][ArrayBalloonlength-1]$}
\EndFunction
\end{algorithmic}
\end{algorithm}
\end{document} |
I'm out of town at the moment (without my laptop). I won't be back before 10th. Can you please wait for the review till then? Thanks! A general tip, avoid using cameCase and use underscores instead. Moreover, any comment should not span more than one line. Keep the comments short (and include an explanation at the end if need be). Right now, the code looks clustered, you can provide blank lines using /Statex. I'll let you know the other ones on 10th. Till then you can look around for other issues (or create one) |
i edited the pseudocode and i think is more clear know. I'll wait for your review next week % Set the Page Layout
\documentclass[12pt]{article}
\usepackage[inner = 1.0cm, outer = 1.0cm, top = 2.0cm, bottom = 2.0cm]{geometry}
% Package to write pseudo-codes
\usepackage{algorithm}
% Remove the 'end' at the end of the algorithm
\usepackage[noend]{algpseudocode}
% Define Left Justified Comments
\algnewcommand{\LeftComment}[1]{\Statex \(\triangleright\) #1}
% Remove the Numbering of the Algorithm
\usepackage{caption}
\DeclareCaptionLabelFormat{algnonumber}{Algorithm}
\captionsetup[algorithm]{labelformat = algnonumber}
\newcommand{\To}{\textbf{ to }}
\begin{document}
\begin{algorithm}
\caption{Find the maximum coins you can collect by bursting the balloons wisely.}
\begin{algorithmic}[1]
\Require An array of Balloons as input
\Statex
\Function{$Max\_Coins$}{$BArray$}
\Statex
\State $BalloonArraylength \gets BArraylength+2$
\State $BalloonArray[0] \gets 1$
\Comment{Initialise the top and bottom of the BalloonArray to 1}
\State $BalloonArray[BalloonArraylength-1] \gets 1$
\Statex
\For{$i=1 \To BalloonArraylength-2$}
\Comment{Indexing BalloonArray to Barray}
\State $BalloonArray[i] \gets Barr[i]$
\EndFor
\Statex
\State $MCarray[i][j] \gets 0$ $\forall i $ $ \forall j$
\Comment{Initialise the MaxCoin array}
\For{$k = 3\To ArrayBalloonlength$}
\Comment{Complexity O($n^3$)}
\Statex
\For{$left =1 \To ArrayBalloonlength-k$}
\State $right \gets left+k$
\Statex
\For{$i=left+2\To right$}
\Comment{i Balloon is the last balloon we burst}
\Statex
\State $MCarray[left][right] \gets MAX(MCarray[left][right],BalloonArray[left]*BalloonArray[i] * BalloonArray[right] + MCarray[left][i] + MCarray[i][right]$
\EndFor
\EndFor
\EndFor
\Statex
\State \Return{$ MCarray[0][ArrayBalloonlength-1]$}
\EndFunction
\end{algorithmic}
\end{algorithm}
Divide and Conquer technique , defining subproblems by the last balloon to burst
\end{document} |
Thanks. I'll look into it. Here is a quick tip regarding code sharing in markdown. This retains the formatting and color coding. (The language is |
I think that the iterative DP solution doesn't capture the essence of the problem (as the real details are hidden by the implementation specifics). Based on your iterative solution, I've written a recursive one which is quite expressive. I would appreciate it if you could write the pseudocode for the recursive one (We can include the iterative one at a later stage). If you are busy, I can take this up, No issues. Here is my solution. Let me know if you have any issues. Tips
|
After you're done, make a pull request so that I can review the code line by line (instead of posting in this thread) |
Problem Link
The text was updated successfully, but these errors were encountered: