Pseudocode for Bursting Balloons

[ghost]

Problem Link

[theodtasia]

i would like to work on this project

[ghost]

Sure, go ahead. Make sure to share your approach first.

[theodtasia]

My first approach using Dynamic Programming and more specifically divide and conquer techique It is java code and passes LeetCode test. public class Solution {//using divide and conquer technique,dividing the problem by the last balloon to burst public int maxCoins(int[] nums) { // Initialize the ArrayB stands for Array of Balloons and extend the list with top=bottom=1
int Arrayb[] = new int[nums.length + 2]; Arrayb[0] = 1; Arrayb[Arrayb.length-1] = 1; for (int i = 0; i < nums.length; i++) { Arrayb[i+1] = nums[i]; }

    // MCstep stands for max coins at every step
    int MCstep[][] = new int[Arrayb.length][Arrayb.length]; 
    for (int i =0; i < Arrayb.length; i++) //Intialiazing MCstep to zero
    {
        for (int j = 0; j < Arrayb.length; j++)
        {
            MCstep[i][j] = 0;
        }
    }

    for (int k=2; k< Arrayb.length;++k) //from  this 3 loops we assume that complexity is o(n^3)
    {
        for (int left=0; left<Arrayb.length-k;++left) 
        {

           int right = left + k;
           for (int i = left + 1; i < right; ++i)// the balloon i is the last balloon to burst
           {
            MCstep[left][right] = Math.max(MCstep[left][right], 
            Arrayb[left] * Arrayb[i] * Arrayb[right] + MCstep[left][i] + MCstep[i][right]);
            }
        }
    }

    return MCstep[0][Arrayb.length-1];
}

}

[ghost]

Looks good. You can start working on the pseudocode now.

[theodtasia]

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}

[ghost]

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)

[theodtasia]

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}

[ghost]

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 tex)

[ghost]

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

• It's okay to use the name of the array as arr instead of BArray.
• Mention explicitly that you are adding 2 extra elements in the initial array (Maybe using push_back/push_front
• Try to accommodate a single statement in a single line. If it gets big, break it into parts
• Define the DP definitions clearly. (dp[low][high] denotes the profit that can be collected by bursting **all** the balloons in the range (low,high) (Excluding bothlowandhigh`).
• Avoid camelCase and use under_scores

[ghost]

After you're done, make a pull request so that I can review the code line by line (instead of posting in this thread)