[Assignment]Write a function called saddle that finds saddle points in the input matrix M.

Write a function called saddle that finds saddle points in the input matrix M. For the purposes of this problem, a saddle point is defined as an element whose value is greater than or equal to every element in its row, and less than or equal to every element in its column. Note that there may be more than one saddle point in M. Return a matrix called indices that has exactly two columns. Each row of indices corresponds to one saddle point with the first element of the row containing the row index of the saddle point and the second element containing the column index. If there is no saddle point in M, then indices is the empty array.

I am working on this assignment...but i got error feedback all the time,i'm still a noob,so can anyone help me to figure out what is wrong in my program? how to improve it?

Here is my program

function indices = saddle(M)
[a,~] = size(M);
j = 1;i = 1;
[max_M,~] = max(M,[],2);
count = 0;
for ii = 1:a
[c,d] = find(M==max_M(ii));
[e,f] = size(c);
mi = min(M(:,d));
         if(max_M(ii) == mi)
             while i<=f
             while i<=e
            output(j,1) = c(i);
            output(j,2) = d(i);
            j = j+1;
            i = i+1;
            count = count+1;
             end
             end
         end
            if count>0
            indices = output;
            else 
            indices = [];
            end
end
end

[Rik]

That interface doesn't provide you any debugging options. Paste this into Matlab and set a breakpoint at the first line. On which line does something unexpected happen?

Also, you're not taking advantage of the matrix capabilities of Matlab. You can specify on which dimension the min and max functions should work.

[Yihan Liu]

Thanks for telling me that. My program could work on my Matlab, since it could find the right number in some simple Matrixes. However I have no idea what kind of matrix they give to this program... I will try to use max or min to find out the answer. Thanks

[Rik]

You should also attempt to create your own test suite. They should at least return without error.

M_test=cell(1,2);%clear and set shape to row vector of cells
M_test{1}=randi(30,400,400);
M_test{2}=randi(30,400,10);
M_test{3}=randi(30,10,400);
M_test{4}=randi(30,400,1);
M_test{5}=randi(30,1,400);

[Yihan Liu]

Indeed, when it comes to this code something goes wrong, and i cannot get the result because the Matlab shows 'busy'. But how can i improve my code? If i give it a small martix like'm = [11; 22; 44; 14; 55; 1246; 72; 1128; 4532; 120;];' It could give me the correct result. I assume that my code efficiency isn't enough.

 M=randi(30,1,400);

[Rik]

If you use min and max you should be able to avoid loops, which probably currently causes your code to run too slow. What code are you using?

[Walter Roberson]

Consider column 7. Suppose you find the minimum value of the column using min. Now find the row indices where the column values are equal to the minimum. There is no point in checking any rows other than those ones, because the other rows cannot possibly have values less than the minimum. Now you can go through just that list of rows and test each one to see whether the row test is satisfied; if it is, then emit that row and column pair.

[Yihan Liu]

I rewrite my program by using max&min and this time it works. Thank you so much and I appreciate you guys’ help.

Answer 1

[Arafat Roney]

function in=saddle(M)
[m,n]=size(M);    %%SIZE CALCULATED
in=[];            %%'in' IS INITIALIZED AS AN EMPTY MATRIX
for ii=1:m
    for jj=1:n
        if (M(ii,jj)==max(M(ii,:))&& M(ii,jj)==min(M(:,jj)))
            in=[in; ii,jj];     %%INDICES CALCULATION AND STORING TO 'in'
        end
    end
end
            
indices=in;       %%FINAL INDICES AS OUTPUT ARGUMENT
end

[Aritra Das]

Thanks a lot, it really works.

[Arafat Roney]

welcome

[Image Analyst]

Yes but it could be made more efficient if the min and max are computed before the loops, and a map of saddle points is preallocated in advance, like in my Answer.

[Arafat Roney]

Yep thanks, I've checked your answer. Actually I'm a beginner here. Not used to preallocating, just simply finished solving. Next time I will try to preallocate and solve in more efficient way. Thank you again.

Answer 2

[Ductho Le]

If you have no idea to solve this problem, you can use my code as a reference. Good luck!

function id = saddle(M)
[a,b]=size(M);
id = zeros(a+b,2);
count = 0;
for i = 1:a
    mah = max(M(i,:));
    [c1,c2] = find(M(i,:) == mah);
    for k = 1:length(c1)
        c1k = c1(k); c2k = c2(k);
        mic = min(M(:,c2k));
        if M(i,c2k)==mic
            count = count+1;
            id(count,:) = [i,c2k];
        end
    end
end
id = id(1:count,:);
end

Answer 3

[Image Analyst]

Try this:

numPoints = 7;
M = randi(9, numPoints, numPoints)
% M = [1,2,3,4,4,3,2,1] % Sample data
rowMaxima = max(M, [], 2)
colMinima = min(M, [], 1)
[rows, columns] = size(M);
output = false(size(M));
for col = 1 : columns
	for row = 1 : rows
		if M(row, col) >= rowMaxima(row) && M(row, col) <= colMinima(col)
			output(row, col) = true;
		end
	end
end
[saddleX, saddleY] = find(output)
output = [saddleX(:), saddleY(:)] % Make into N by 2 array

[Amandeep Kaur]

why are you redefining M?

[Amandeep Kaur]

how to rectify this?

[Rik]

His code is a minimal working example (and therefore includes data to run). It is your homework, put some effort into how to adapt this to work as a function.

Answer 4

[sri harsha juttiga]

function [indices,j] = saddle(M)
indices=[];
[m,n]=size(M);
f=0;
for ii=1:m
    for jj=1:n
        a=M(ii,jj);
        x=max(M(ii,:));
        y=min(M(:,jj));
        
        if (a>=x && a<=y)
            f=f+1;
            indices(f,:)=[ii,jj];            
        end
    end
end
if isempty(indices)
    indices=[];
else
    indices=indices(1:f,:);
end
end

[Indrajit Marathe]

It Is Correct

[Takkallapally Sai Shodhan Rao]

What is this line doing?

indices(f,:)=[ii,jj];

[Walter Roberson]

The required output is a list of locations that are saddle points, expressed as two columns, first row and then column numbers of where the saddle point was found. The line you are indicating is the one that is recording the row and column numbers into the solution.

Answer 5

[Yaksha SJ]

function s = saddle(M)
[r, c] = size(M);
% Initialize the saddle points to an empty array
s = [];
% Check the dimensions to see if input is a row or column vector
if r > 1
    cols = min(M);          % find the min value in each column if more than 1 row
else
    cols = M;               % vector is a special case, min would give a single value
end
if c > 1
    rows = max(M');         % find the max value in each row
else
    rows = M;               % vector is a special case, max would give a single value
end
for ii = 1:c                % visit each column
    for jj = 1:r            % and each row, that is, each element of M
        if M(jj,ii) == cols(ii) && M(jj,ii) == rows(jj) % if both conditions hold
            s = [s; jj ii];                             % saddle point! Let's add it!
        end
    end
end

[Walter Roberson]

Note: you can use min(M, [], 1) to force taking the min along the first dimension, which would return all of M if M only had one row.

[Adam Casole-Buchanan]

This was a huge help.

Answer 6

[Amandeep Kaur]

function [indices] = saddle(M)
[a,~] = size(M);
j = 1;i = 1;
[max_M,~] = max(M,[],2);
count = 0;
for ii = 1:a
[c,d] = find(M==max_M(ii));
mi = min(M(:,d));
         if(max_M(ii) == mi)
            output(j,1) = c(i);
            output(j,2) = d(i);
            j = j+1;
            i = i+1;
            count = count+1;
         end
end
            if count>0
            indices = output;
            else 
            indices = [];
            end
end

I am writing this code, it is giving following message

Answer 7

[Vivek Jaswal]

Someone please help me out where am I going wrong in this code?

function x=saddle(M)
    [b,c]=size(M);
    for i=1:b
        for j=1:c
            if M(i,j)==max(M(i,:))
                [d,e]=max(M(i,:));
                if d==min(M(:,e))
                    a(i,1)=i; a(i,2)=e;
                else
                    a(i,1)=0; a(i,2)=0;
                end
            end
            j=j+1;
        end
        i=i+1;
    end
    x=a(any(a,2),:);
    if x==0
        x=[];
    end
end

[Walter Roberson]

Please read https://www.mathworks.com/matlabcentral/answers/518275-trouble-making-a-loop-repeat-correctly#answer_426331

Also, if there are no matches then a(any(a,2),:) would be empty, and empty would not compare equal to 0 in your x==0 line.

[Vivek Jaswal]

I just changed the code by preallocating matrix a and removing the if x==0 conditon because a(any(a,2),:) would automatically give null vector if matrix a is zero . However, Im still unable to submit the code. What could be the possible reason?

function x=saddle(M)
    [b,c]=size(M);
    a=zeros(b,2);
    for i=1:b
        for j=1:c
            if M(i,j)==max(M(i,:))
                [d,e]=max(M(i,:));
                if d==min(M(:,e))
                    a(i,1)=i; a(i,2)=e;
                else
                    a(i,1)=0; a(i,2)=0;
                end
            end
        end
        j=j+1;
    end
    i=i+1;
    x=a(any(a,2),:);
end

[Walter Roberson]

Everyone else here has been working based on the problem statement,

Return a matrix called indices that has exactly two columns.

You do not have any matrix called indices.

[Vivek Jaswal]

Sorry for that. I used variable x instead of indices matrix which returns 2 columns and rows equal to the number of saddle points in the input matrix M.

[Walter Roberson]

It doesn't matter to me which variable you use, but it does matter to the grading system.

[Vivek Jaswal]

I have corrected the variable name. Could you please let me know where I am doing wrong?

function indices=saddle(M)
    [b,c]=size(M);
    a=zeros(b,2);
    for i=1:b
        for j=1:c
            if M(i,j)==max(M(i,:))
                [d,e]=max(M(i,:));
                if d==min(M(:,e))
                    a(i,1)=i; a(i,2)=e;
                else
                    a(i,1)=0; a(i,2)=0;
                end
            end
        end
        j=j+1;
    end
    i=i+1;
    indices=a(any(a,2),:);
end

[Walter Roberson]

what leads you to suspect that your code wrong?

[Vivek Jaswal]

Because I am not able to submit the assignment on this question.

For input matrix Z, the indices are coming out to be correct but there is an error while submission.

[Image Analyst]

The code in my answer https://www.mathworks.com/matlabcentral/answers/483543-assignment-write-a-function-called-saddle-that-finds-saddle-points-in-the-input-matrix-m#answer_409282

gives the correct answer:

rowMaxima =

4

colMinima =

1 2 3 4 4 3 2 1

saddleX =

1 1

saddleY =

4 5

output =

1 4

1 5

You can see that the 4's are saddle points and there are two of the 4's at locations (1,4) and (1,5).

Answer 8

[gourav naik]

function out=saddle(m)
[x,y]=size(m);
ind=[];
for i=1:x
    for j=1:y
        a=max(m(i,:));
        b=min(m(:,j));
        if m(i,j)<=b && m(i,j)>=a
            ind=[ind ;i,j];
        end
    end
end
out=ind;
end
       

try these simple and short

[Walter Roberson]

Under what condition could it be true that m(i,j)<b ?

[JIGNESH PATIL]

Great help!

Answer 9

[Yasin Peker]

function indices = saddle(M)
    
    k = size(M);
    r = cell(k(1),k(2));
    l = cell(k(1),k(2));
    
    for i = 1:k(2)
        for ii = 1:k(1)
            t = (M(ii,i) <= M(:,i));
            if sum(t) == k(1)
                r{ii,i} = [ii,i];
            end
        end
    end
   for y = 1:k(1)
       for yy = 1:k(2)
           p = M(y,yy) >= M(y,:);
           if sum(p) == k(2)
               l{y,yy} = [y,yy];
           end
       end
   end
   for v = 1:k(1)
       for vv = 1:k(2)
           o =  (r{v,vv} == l{v,vv});
           indices=[];
           if sum(o) == 2
               indices = r{v,vv};
           
           end
       end
   end
end

[Yasin Peker]

I always get the same error message

Error using ==

Matrix dimensions must agree.

Error in saddle (line 25)

o = (r{v,vv} == l{v,vv});

What I have to do to?

What should I do to improve my code?

Answer 10

[Kumar Vivek]

Try this out if you are not getting the problem.

function indices = saddle(M)
    b = max(M, [],2);
    l = min(M, [],1);
      d = b==l;      %converting the common elements to logical 1
      if isempty(d)
        indices = [];
      else
      [rd,cd] = find(d); %finding the location of that common element
      indices = [rd(:),cd(:)];
      end   
end

Answer 11

[Prithvi Shams]

function indices = saddle(M)
    
    B = size(M);
    idx = 0;
    A = [];
    %% 
    
    for i = 1:B(1)
        for j = 1:B(2)
            if (M(i,j) == max(M(i,:))) && (M(i,j) == min(M(:,j)))
                idx = idx + 1;
                A(idx) = M(i,j); %Capture the saddle points in array A
                R(idx) = i; %Capture row indices of saddle points in vector R
                C(idx) = j; %Capture column indices of saddle points in vector C
            end

        end
    end
    %% 
    if isempty(A)
        indices = [];
    else
    for k = 1:numel(A)          
                    indices(k, 1) = R(k);
                    indices(k, 2) = C(k);
            
        
    end
    end
end

Answer 12

[David Gonzalez]

function indices = saddle(M)
   
    indices = [];
    for jj = 1:size(M,2)
        for ii = 1:size(M,1)
            if M(ii,jj) == min(M(:,jj)) && M(ii,jj) == max(M(ii,:))
                indices = [indices; ii jj];
            end
        end
    end

Answer 13

[Taif Ahmed BIpul]

function indices=saddle2(M)
k=0;
indices1=zeros(k);
indices2=zeros(k);
rowIndices=zeros(k);
colIndices=zeros(k);
for i=1:size(M,1)
    for j=1:size(M,2)
        if M(i,j)==max(M(i,:)) && M(i,j)==min(M(:,j))
            k=k+1;
          rowIndices(k)=i;
          colIndices(k)=j;
          indices1=[rowIndices' colIndices'];
        else
            indices2=[];
        end
    end
end
if isempty(indices1)
    indices=indices2;
else
    indices=indices1;
end

Answer 14

[Nikolay Ampilogov]

Diar Yihan Liu and other members of this topic!

I think that there is a mistake in the verification pricedure or discription of this exercise [https://www.coursera.org/ ; coourse Introduction to Programming with MATLAB > Week 9 > Assignment: Saddle Points].

There is a frase at the end of the discription: "If there is no saddle point in M, then indices is the empty array." It means that in this case your result should back somethink like:

indices =

  0×2 empty double matrix

My code wich passed by the test calling (Code to call your function) is:

function indices = saddle(M)
indices = double.empty(0,2); % To return empty matrix in the mistake case
if (size(M, 1) < 2) || (size(M, 2) < 2) || ~isnumeric(M) % Check the argument
    fprintf('The argument is not a numeric matrix with proper size.');
    return
end
% Find the indices of saddle points defined as points wich are the local
% minimums for columns and the local maximums for rows of M simultaneously.
[indLocalSaddleRow, indLocalSaddleCol] = find(islocalmin(M, 1) & islocalmax(M, 2));
indices = [indLocalSaddleRow indLocalSaddleCol];
end

To check it for multi saddle surface, please place this before calling:

Z = repmat(Z, 2);

But my code is not acceptable by Assessment after Submit.

The code by gourav naik (on 25 Apr 2020; here) is not sattisfy to requarement "'If there is no saddle point in M, then indices is the empty array." But his code pass by Assessment after Submit succssesfully.

[Walter Roberson]

gourav's code returns [] if there is not saddle point, and that is an empty array. It does not have exactly two columns, but it is empty, and that is valid to interpret the bit about empty as over-riding the part about two columns.

MATLAB has an indefinite number of different empty arrays, but typically when people refer to "the empty array" they are referring to [] which is 0 x 0.

Note: nothing in the assignment expects an error message for invalid parameters.

[Nikolay Ampilogov]

Dear Walter, thanks for your attention.

1. It does not have exactly two columns, but it is empty, and that is valid to interpret the bit about empty as over-riding the part about two columns.

Agreed, rather better to use [] instead double.empty(0,2).

And to add this before the end:

if isempty(indices)
    indices = [];
end

2. Note: nothing in the assignment expects an error message for invalid parameters.

Agreed, this user-friendly polite here is not necessary:

fprintf('The argument is not a numeric matrix with proper size.');

3. What do you think?

How many saddle points an angulated plane has? Z = [1 2 3; 4 5 6; 7 8 9];

How many saddle points a not angulated plane has? Z = ones(3,3);

Thanks a lot!

Answer 15

[Vipin Parthan]

function indices=saddle(M)
[r,c]=size(M);
%Compute largest row element and the least column element.
rMax=max(M,[],2);
cMin=min(M,[],1);
% Initialize empty matrix
indices=[];
% Conditional to find saddle point
for j=1:c
    for i=1:r
        if M(i,j)==rMax(i) && M(i,j)==cMin(j)
           indices=[indices; i,j]; % Store into output argument
        end
    end
end
end

Hope this code helps. Please suggest if any modifications can be made to make the code more efficient.