An example where the output of the k-medoid algorithm is different than the output of the k-means algorithm I understand the difference between k medoid and k means. But can you give me an example with a small data set where the k medoid output is different from k means output.
 A: A medoid has to be a member of the set, a centroid does not.
Centroids are typically discussed in the context of solid, continuous objects, but there's no reason to believe that the extension to discrete samples would require the centroid to be a member of the original set.
A: k-medoid is based on medoids (which is a point that belongs to the dataset) calculating by minimizing the absolute distance between the points and the selected centroid, rather than minimizing the square distance. As a result, it's more robust to noise and outliers than k-means.
Here is a simple, contrived example with 2 clusters (ignore the reversed colors)

As you can see, the medoids and centroids (of k-means) are slightly different in each group. Also you should note that every time you run these algorithms, because of the random starting points and the nature of the minimization algorithm, you will get slightly different results. Here is another run:

And here is the code:
library(cluster)
x <- rbind(matrix(rnorm(100, mean = 0.5, sd = 4.5), ncol = 2),
           matrix(rnorm(100, mean = 0.5, sd = 0.1), ncol = 2))
colnames(x) <- c("x", "y")
# using 2 clusters because we know the data comes from two groups
cl <- kmeans(x, 2) 
kclus <- pam(x,2)
par(mfrow=c(1,2))
plot(x, col = kclus$clustering, main="Kmedoids Cluster")
points(kclus$medoids, col = 1:3, pch = 10, cex = 4)
plot(x, col = cl$cluster, main="Kmeans Cluster")
points(cl$centers, col = 1:3, pch = 10, cex = 4)
A: Both k-means and k-medoids algorithms are breaking the dataset up into k groups. Also, they are both trying to minimize the distance between points of the same cluster and a particular point which is the center of that cluster. In contrast to the k-means algorithm, k-medoids algorithm chooses points as centers that belong to the dastaset. 
The most common implementation of k-medoids clustering algorithm is the Partitioning Around Medoids (PAM) algorithm. PAM algorithm uses a greedy search which may not find the global optimum solution. 
Medoids are more robust to outliers than centroids, but they need more computation for high dimensional data.
