
function [y] = kmeans(X, k)

[n,d] = size(X);

% Pick k points at random as initial centers.  Do this by randomly
% permuting the points and then taking the first k in the permutation
centers = X(randperm(n),:);
centers = centers(1:k,:);

y = zeros(n,1);

for t = 1:100
  % Fill in the k-means updates here

  % assign each input to the nearest cluster
  for i=1:n
    d = zeros(k,1);
    for j=1:k
      d(j) = norm(X(i,:)-centers(j,:));
    end
    [dmin,y(i)] = min(d);
  end

  % recompute the cluster means
  for j=1:k
    Ij = find(y==j);
    if (length(Ij)) 
       centers(j,:) = mean(X(Ij,:)); 
    end
  end 
 
end
