Introduction to Algorithms - The Reading Notes: Part 4, Maximun Sum Sub-Array (BF)

Maximum Sub Sub-Array is an interesting problem. It goes like this, I'm given a series of values and I'm asked to find a continuous sub-series that has the maximum sum. 

For example, if I'm given a series of value -3, 2, 5, 6, -1, 2, -5, 5, then I find that the sub-series 2,5,6 gives 13 which quite large, but 2, 5, 6, -1, 2 sums up even more, it gives 14. If I look further, I find that the sub-series 2, 5, 6, -1, 2, -5, 5 gives the same maximum of 14. So we may have more than one maximum and our goal is to find any one of them.

ITA mentions the brutal force algorithm that has Ω(n^2) running time, it says the algorithm is to calculate sums of all sub-series possible (there is O(n^2) number of sub-series) and if we can evaluate each sub-series in constant time then we can have Ω(n^2) algorithm, but it does not say how. ITA introduces also a very fast (O(nlgn) algorithm based on DaC (Divide and Conquer). 

I understand that this ITA chapter is for DaC so no need to talk more details on this brutal force algorithm and it's put in the exercise. So, let's finish the Ω(n^2) brutal force algorithm first then we will see how to implement the DaC one.

So you already know the number of sub-series is O(n^2), suppose we have a n-length series, but why?  The answer is this number equals to the number of ways you have when you try to select any two numbers in the series (those two numbers defines the start and end of the sub-series), that is n(n-1)/2.

Now comes to the question how we calculate the sum of each sub-series. If we just simply calculate sums for all sub-series, then we have to sum n sub-series of length 1, n-1 sub-series of length 2, n-2 sub-series of length 3, ..., 1 sub-series of length n. In total, we need to do add n+2(n-1)+3(n-2)...+ n times, which is equivalent to sum(for i = 1 to n) (i*(n-i+1)),  which renders our algorithm O(n^3) in terms of time consumption.

Now we need to do more to get a faster algorithm. Just one more glance at our previous O(n^3) algorithm we find that the sub-series have many common parts and we add those parts repeatedly many times once for each sub-series. That's the key to reduce running time.

I will now use a n*n matrix to save sums of each sub-series, say, [0-1], [0-2]... [1,2], [1,3]... Also each single element represents also a sub-series of length 1, they are also stored in the matrix [0,0], [1,1] ... So only the upper triangle of the matrix is used. The advantage to save the sums in the matrix is that it's very easy to find a sub-series that can be used to build the next sum, because we know that:
sum(sub[i, j]) = sum(sub[i, j-1]) + v[j] = sum(sub[i, j-1]) + sub[j, j]

OK, that's enough for the theory, let's see the code. But wait a moment, before implementing the algorithm, let's put in place the unit test!

I'll use another class for the MaxSubArray unit test, separated from that of the sort algorithms. With CppUnit, I just simply create a .h and .cpp for the new tests, no other configuration is needed.

MiscTest.h

   1:  #ifndef MISCTEST_H  

   2:  #define MISCTEST_H  

   3:  #include <cppunit/extensions/HelperMacros.h> 

   4:    

   5:    

   6:  class MiscTest : public CppUnit::TestFixture { 

   7:    

   8:      CPPUNIT_TEST_SUITE( MiscTest); 

   9:      CPPUNIT_TEST( testMaxSubArray_0); 

  10:      CPPUNIT_TEST_SUITE_END(); 

  11:    

  12:      private: 

  13:      public: 

  14:    

  15:      void setUp(); 

  16:      void tearDown(); 

  17:    

  18:      // Test cases. 

  19:      void testMaxSubArray_0(); 

  20:    

  21:  }; 

  22:  #endif 

MiscTest.cpp

   1:  #include "MiscTest.h" 

   2:  #include "MaxSubArray.h" 

   3:    

   4:  using namespace Common::Algorithm::MaxSubArray; 

   5:    

   6:  // Registers the fixture into the 'registry' 

   7:  CPPUNIT_TEST_SUITE_REGISTRATION( MiscTest ); 

   8:    

   9:  void MiscTest::setUp() 

  10:  { 

  11:  } 

  12:  void MiscTest::tearDown() 

  13:  { 

  14:  } 

  15:    

  16:  // Test normal case. 

  17:  void MiscTest::testMaxSubArray_0() 

  18:  { 

  19:      int iArray[] = {-10, 5, 7, -2, 19, 50, -30, 32, -24, 18}; 

  20:      std::vector<int> v(iArray, iArray + sizeof(iArray) / sizeof(int)); 

  21:    

  22:      int rStart = 0; 

  23:      int rEnd = 0; 

  24:      int rSum = 0; 

  25:      MaxSubArray::CalcBF(v, rStart, rEnd, rSum); 

  26:       

  27:      CPPUNIT_ASSERT_EQUAL( 1, rStart); 

  28:      CPPUNIT_ASSERT_EQUAL( 7, rEnd); 

  29:      CPPUNIT_ASSERT_EQUAL(81, rSum); 

  30:    

  31:  } 

Finally, I can start implementing the algorithm. Then I run the unit test each time I think my algorithm will work, then fix bugs and retry. Here is the final version that passes the test above:

   1:  void MaxSubArray::CalcBF(std::vector<int> &v, int &oStart, int &oEnd, int &oSum) 

   2:  { 

   3:      // Trivial cases, size = 0 or 1. 

   4:      if (v.size() == 0) 

   5:      { 

   6:      oStart = 0;  

   7:      oEnd = 0; 

   8:      oSum = 0; 

   9:      return; 

  10:      } 

  11:    

  12:      if (v.size() == 1) 

  13:      { 

  14:      oStart = 0; 

  15:      oEnd = 0; 

  16:      oSum = v[0]; 

  17:      return; 

  18:      } 

  19:    

  20:      oSum= 0; 

  21:      oStart = 0; 

  22:      oEnd = 0; 

  23:      std::vector<int> vResult; 

  24:    

  25:      // Initialize vResult. 

  26:      for (size_t i = 0; i < v.size(); i++) 

  27:      { 

  28:      for (size_t j = 0; j < v.size(); j++) 

  29:      { 

  30:          if (i == j) 

  31:          { 

  32:          vResult.push_back(v[i]); 

  33:          } 

  34:          else 

  35:          { 

  36:          vResult.push_back(0); 

  37:          } 

  38:      } 

  39:      } 

  40:    

  41:    

  42:      // Calculate the results. 

  43:      // We use a matrix to store sum of all intervals 

  44:      // 00   01   02   03   04 

  45:      // 10   11   12   13   14 

  46:      // 20   21   22   23   24 

  47:      // 30   31   32   33   34 

  48:      // 40   41   42   43   44 

  49:      // M[i,i] = v[i] 

  50:      // M[i,j] = sum(i,j) for 0 <= i < j <= v.size().  

  51:      // It takes O(n^2) time. 

  52:      for (size_t i = 0; i < v.size(); i++) 

  53:      { 

  54:      for (size_t j = 0; j < v.size(); j++) 

  55:      { 

  56:          if (i < j) 

  57:          { 

  58:          vResult[ i * v.size() + j] = vResult[ i * v.size() + j - 1 ] + 

  59:                                       vResult[ j * v.size() + j]; 

  60:          if (oSum < vResult[i * v.size() +j]) 

  61:          { 

  62:              oSum = vResult[i * v.size() + j]; 

  63:              oStart = i; 

  64:              oEnd = j; 

  65:          } 

  66:          } 

  67:      } 

  68:      } 

  69:  } 

Let discuss the faster version that takes only O(nlgn) time, in the next post. Thank you and like to know your feedback.

Introduction to Algorithms - The Reading Notes: Part 3, Merge Sort

Merge sort is a better sorting algorithm than insertion sort in terms of worst case running time. It's also the algorithm that I ran into when I have my interview for my current job.

The ITA book uses it as an example of the Divide and Conquer philosophy which basically divides a big problem into several smaller ones then solve each of them first, when the smaller problems are solved, the big problem becomes easier to solve. This usually results in a recursive algorithm as the case of the merge sort. I'm not sure it's a good place to introduce this concept in the beginning part of the book, the learning curve is quite steep.

The merge sort contains two parts, the divide or recursive part and the merge part. The idea is to divide the whole list to sort into two lists each of half the original size and sort the two lists separately, then merge the two sorted smaller lists into one sorted list to get the problem solved. The magic is to repeat this procedure for the two smaller lists too, so they became four even smaller lists, and so on.

The merge part is quite straightforward, compare the elements at the head position of two sorted list, and put the larger (or smaller) into the result list until one of the list contains no element, then we can safely put the rest of the other list into the result list. Only one thing to remark, the vector constructor who takes to iterators s and e means to construct a vector that contains elements from s to e-1 of the original vector.

   1:  void MergeSort::Merge(std::vector<int> &v, int p, int q, int r, bool bNonDecreasing) 

   2:  { 

   3:      std::cout << "Merging sub array: " << p << ":"<< q-1 << " and " << q << ":" << r-1 << std::endl; 

   4:      std::vector<int> vSub1(v.begin()+p, v.begin()+q); 

   5:      std::vector<int> vSub2(v.begin()+q, v.begin()+r); 

   6:      std::cout << "vSub1.size: " << vSub1.size() << ", vSub2.size: "<< vSub2.size() << std::endl; 

   7:      int iLastValue = (bNonDecreasing ? INT_MAX : INT_MIN); 

   8:       

   9:      vSub1.push_back(iLastValue); 

  10:      vSub2.push_back(iLastValue); 

  11:    

  12:      int i = 0; 

  13:      int j = 0; 

  14:      for (int k = p; k < r; k++) 

  15:      { 

  16:      if ( bNonDecreasing && (vSub1[i] < vSub2[j]) || 

  17:          !bNonDecreasing && (vSub1[i] > vSub2[j])) 

  18:      { 

  19:         v[k] = vSub1[i]; 

  20:         i++; 

  21:      } 

  22:      else 

  23:      { 

  24:          v[k] = vSub2[j]; 

  25:          j++; 

  26:      } 

  27:    

  28:      } 

  29:  } 

The recursive part is a bit tricky. Personally, I prefer to give a unique interface to the users of my sorting library, so I'd like to call my interface MergeSort::Sort(input_vector_to_sort, order). Then I found that I need a helper method that can be called recursively and I named it as DoSort(). DoSort() takes two additional parameters, the start and the end position in the list that defines the sub-list to be sorted. It starts by dividing the input vector into two smaller ones then it calls itself recursively for each smaller vector, finally it merges the two smaller vector (sorted now).

   1:  void MergeSort::DoSort(std::vector<int> &v, int p, int r, bool bNonDecreasing) 

   2:  { 

   3:      std::cout << "Sorting sub array: " << p << ":" << r << std::endl; 

   4:      if (p < r) 

   5:      { 

   6:      int q = (p+r)/2;  

   7:      std::cout << "Dividing sub array: " << p << ":" << q  << ", " << q+1 << ":" << r << std::endl; 

   8:      DoSort(v, p, q, bNonDecreasing); 

   9:      DoSort(v, q+1, r, bNonDecreasing); 

  10:      Merge(v, p, q+1, r+1, bNonDecreasing); 

  11:      } 

  12:  } 

Finally, the interface method is fairly simple:

   1:  void MergeSort::Sort(std::vector<int> &v, bool bNonDecreasing)  

   2:  { 

   3:      if (v.size() < 1 ) 

   4:      { 

   5:      return; 

   6:      } 

   7:    

   8:      DoSort(v, 0, v.size()-1, bNonDecreasing); 

   9:  } 

Introduction to Algorithms - The Reading Notes: Part 2, Insertion Sort

Insertion Sort is probably the simplest algorithm so it is used in many books as the first example. ItA discusses this minion algorithm right in the Part I Foundations, Chapter 2 Getting Started.

The aim of the algorithm is to sort a set of keys in a certain order: You have some keys as input then the algorithm will give you a ordered list of your keys. Here is how the insertion sort works: suppose all the keys are in an input list, then the algorithm starts working on the the keys one by one in a certain order, for example from left to right. Each time it works on a key, it save it's value, then it looks all keys already processed (they are to the left of the current key), from right to left, by comparing the current key with them and moving the processed keys one place to the right if it should be placed after the current key, according to the ordering rule. This process ends until when an already processed key that should be placed to the left of the current key or there is no more already processed keys. Then we put the current key in the place of the last already processed key we found. Now that we find a good place for the current key, we can start processing the next unprocessed key.

The algorithm is simple, code the pseudo code in C++ is straightforward. What I'd to say here is how I set up the whole project with CppUnit and SCons.

CppUnit is very handy for unit test, especially when I'm writing libraries. Just as in this ITA project, I'd like to put all the algorithms in some libraries, I don't need to write a separate main cpp file just to test these algorithms, instead, I setup a CppUnit testing framework for this. It's easier to maintain. For how to install/use CppUnit, here is the CppUnit Documentation.

First, I implement the Insertion Sort algorithm in InsertSort.cpp and .h files and I put them in a folder named Sorting. With TDD in mind, I write only the class declaration but leaving the method empty.

Then I setup the CppUnit framework: I need three files: SortingTest.h and .cpp, where I'll implement test code for all the sorting algorithms I'll write; TestMain.cpp. where is the "main" function of the test code. The beauty of using CppUnit is this "main" function has only infrastructure interest, it's not related to the particular test cases. So once setup, I don't need to change it. I'll only work on the SortingTest class.

Now I will write a test case:

   1:  // Test normal case.

   2:  void SortingTest::testInsertSort_0()

   3:  {

   4:      int iArray[] = {10, 5, 7, -2, 19, 50, 300, 320, 160, 1000};

   5:      std::vector<int> v(iArray, iArray + sizeof(iArray) / sizeof(int));

   6:      Common::Algorithm::Sort::InsertSort(v);

   7:      CPPUNIT_ASSERT_EQUAL(v[0], -2);

   8:      CPPUNIT_ASSERT_EQUAL(v[1], 5);

   9:      CPPUNIT_ASSERT_EQUAL(v[2], 7);

  10:      CPPUNIT_ASSERT_EQUAL(v[3], 10);

  11:      CPPUNIT_ASSERT_EQUAL(v[4], 19);

  12:      CPPUNIT_ASSERT_EQUAL(v[5], 50);

  13:      CPPUNIT_ASSERT_EQUAL(v[6], 160);

  14:      CPPUNIT_ASSERT_EQUAL(v[7], 300);

  15:      CPPUNIT_ASSERT_EQUAL(v[8], 320);

  16:      CPPUNIT_ASSERT_EQUAL(v[9], 1000);

  17:  }

The aim of the test case is to test the basic function of the algorithm, I initialize a vector with 10 integers, then I call the InsertSort(), finally, I test that the vector is sorted by examining that each element has the expected value. CppUnit provides a macro CPPUNIT_ASSERT_EQUAL for this kind of test.

Now that I have the algorithm code (although not yet complete), I have the testing code, I can compile both and run my test. I use SCons for this. SCons is very convenient yet powerful.  Basically, you write a configuration file usually named as SConstruct, inside you tell scons how to build your project.

   1:  Library(target='Sorting/Sorting', \ 

   2:          source=Glob('Sorting/*.cpp')) 

   3:  Program(target='CppUnitTest/TestMain', \ 

   4:          source=Glob('CppUnitTest/*.cpp'), \ 

   5:          LIBS=['cppunit','Sorting'], \ 

   6:          LIBPATH='Sorting', \ 

   7:          CPPPATH=['Sorting', 'CppUnitTest']) 

The Library keyword at line 1 specifies a library to build, the source code are all the .cpp files in the Sorting folder.

The test code should be built with the Program keyword, as in line 3. It needs all source code in the CppUnitTest folder and two libraries: the CppUnit library and the Sorting library that I'm testing. The Sorting library is in my local folder so I need to tell SCons where to find it with LIBPATH keyword as in line 6 above. Finally, the test code need the Sorting library header to compile, I'll tell SCons to find the Sorting headers in the Sorting folder with CPPPATH keyword as in line 7.

OK, now I save the Sconstruct file then I type scons. It compiles my Sorting library and the testing code.

I can run the test immediately and it fails evidently. Now you can start to write the InsertSort() method, but personally, I will write some more test cases before writing the InsertSort() method. For example, I will write one case when the input is empty, another when all inputs have the same value, etc.

Finally, I write my InsertSort() method and correct all failing cases, once all test cases pass, I'm quite confident that my InsertSort() works correctly.

Here is the how the InsertSort() is implemented:

   1:  void Sort::InsertSort(std::vector<int> &v)  

   2:  { 

   3:      int key = 0; 

   4:    

   5:      // Trivial case, nothing to do.  

   6:      if (v.size() <= 1) 

   7:      {    

   8:          return; 

   9:      }    

  10:    

  11:      for (int j = 1; j < v.size(); j++) 

  12:      {    

  13:          key = v[j]; 

  14:          int i = j-1; 

  15:          while (i >= 0 && v[i] > key)                                                                                             

  16:          {    

  17:              v[i+1] = v[i]; 

  18:              i--; 

  19:          }    

  20:          v[i+1] = key; 

  21:      }    

  22:  } 

  23:    

Modification: When I started to write the merge sort, I found it could be better to rename the class and the methods, and finally, I ended up with a solution that gives each sorting algorithm a class and they all have the same Sort() method declaration.

   1:  void InsertSort::Sort(std::vector<int> &v, bool bNonDecreasing) 

Introduction to Algorithms - The Reading Notes: Part 1, Introduction

I started reading this book recently and I will share my understandings and thoughts with you.

I will discuss the problems in the book and I'd like to inject in particular more on the software engineering aspects of those algorithms: how to implement them so they can be used in a real-life software project to solve practical problems.

Finally, I will code those algorithms in C++ and build the code under Fedora Linux with Scons. I will also adopt the TDD methodology (TDD stands for Test Driven Development) and use CppUnit for unit testing.

Here are some useful links for this project:
The code formatter, it formats the source code into HTML so they look better when put in the blog. Currently it formats C#, VB and some other languages but not C/C++. I'll continue looking for one but before I find something, I'll use this one for the moment.

The SCons user's guide.

The CppUnit Documentation.