{"id":25910,"date":"2019-07-04T20:36:28","date_gmt":"2019-07-05T00:36:28","guid":{"rendered":"https:\/\/www.dannyadam.com\/blog\/?p=25910"},"modified":"2020-01-14T22:42:56","modified_gmt":"2020-01-15T03:42:56","slug":"smawk-in-cpp","status":"publish","type":"post","link":"https:\/\/www.dannyadam.com\/blog\/2019\/07\/smawk-in-cpp\/","title":{"rendered":"SMAWK in C++"},"content":{"rendered":"\n

I recently implemented kmeans1d<\/a>\u2014discussed in a prior post<\/a>\u2014for efficiently performing globally optimal 1D k<\/em>-means clustering. The implementation utilizes the SMAWK algorithm<\/a> (Aggarwal et al., 1987), which calculates argmin(i<\/em>)<\/code> for each row i<\/em> of an arbitrary n \u00d7 m<\/code> totally monotone<\/em> matrix, in O(m(1 + lg(n\/m)))<\/code>.<\/p>\n\n\n\n

I’ve factored out my SMAWK C++ code into the example below. In general, SMAWK works with an implicitly<\/em> defined matrix, utilizing a function that returns a value corresponding to an arbitrary position in the matrix. An explicitly<\/em> defined matrix is used in the example for the purpose of illustration.<\/p>\n\n\n\n

The program prints the column indices corresponding to the minimum element of each row in a totally monotone matrix. The matrix is from monge.pdf<\/a>\u2014a course document that I found online.<\/p>\n\n\n

<\/p>\n