Thread: Algorithm

Suppose that you're given a 3 by 3 table of pos. integers. For any step, you are either able to double each of the #s in any 1 row (horizontal), or you are able to subtract 1 from each of the #s in any 1 column (vertical). Come up with an algorithm that transforms the orig. table into a table of all 0's.

Note: need this explained in words how it works (not any pseudocode or programming), and showing an example of how this works.

Start with first column

Keep subtracting 1 from each entry in the column until one of the entries is 1 then

i) Double the entries in the row the 1 is in
ii) Subtract one from each entry in the first column

Do this until you have two entries in the column that are 1 then

i) Double the entries in the rows the 1s are in
ii) Subtract one from each entry in the first column

Do this until all entries in the first column are 1 then

i) Subtract one from each entry in the first column

The frst column's entries are now all zeroes.

You can now repeat this procedure for the second and third columns as doubling zeroes will not change the number

Can improve the efficiency of the algorithm by targeting the column with the highest entry at each stage