Kalanand's September 2008 Log

September 1st

Sort using C++ STL built-in functions

#include < iostream>     // std::cout
#include < algorithm>    // std::sort
#include < vector>       // std::vector

bool myfunction (int i,int j) { return (i myvector (myints, myints+8);               // 32 71 12 45 26 80 53 33

  // using default comparison (operator <):
  std::sort (myvector.begin(), myvector.begin()+4);           //(12 32 45 71)26 80 53 33

  // using function as comp
  std::sort (myvector.begin()+4, myvector.end(), myfunction); // 12 32 45 71(26 33 53 80)

  // using object as comp
  std::sort (myvector.begin(), myvector.end(), myobject);     //(12 26 32 33 45 53 71 80)

  // print out content:
  std::cout << "myvector contains:";
  for (std::vector::iterator it=myvector.begin(); it!=myvector.end(); ++it)
    std::cout << ' ' << *it;
  std::cout << '\n';

  return 0;
}

Finding prime numbers

#include <iostream>
#include <vector>

const int max = 100;

int main() 
{
   std::vector allnums;
   std::vector primes;

   for (int i = 1; i <= max; ++i)
      allnums.push_back(i);   

   allnums[0]=0;

   for (int i = 2; i < allnums.size(); ++i) {   
      if (allnums[i-1] != 0) {
         primes.push_back(allnums[i-1]);
         for (int j = 2 * allnums[i-1]; j < max; j += allnums[i-1]) 
            allnums[j-1] = 0;  
      }
   }

   std::cout << "The prime numbers up to " << max << " are : " << std::endl;
   for (int i = 1; i < primes.size(); ++i) {
      std::cout << primes[i] << "\t";   
      if(i%5 == 0) std::cout << std::endl;
   }

   std::cout << std::endl;
   return 0;
}

~>./PrimeNumbers
The prime numbers up to 100 are : 
3	5	7	11	13	
17	19	23	29	31	
37	41	43	47	53	
59	61	67	71	73	
79	83	89	97	

Calculate mean, median, mode of an array

#include <iostream>
#include <algorithm>


// Calculate mean. Works for both sorted and unsorted arrays. 
float CalcMean(const int array[] , int size){
    if ( size <= 0 ) return 0;
    int sum = 0;
    for (int i = 0; i < size; i++) sum += array[i];
    return (float)sum / size;
}


// Calculate median. Works for sorted arrays. 
float CalcMedian(const int array[], int size){
    if( size <= 0 ) return 0;

    if( size % 2 ) return (float)array[size/2];
    else return (float)(array[size/2] + array[size/2+1]) / 2;
}



// Calculate mode. Works for sorted arrays. 
int CalcMode(const int array[], int size){
   if( size <= 0) return 0;

   int frequency = 1;  // frequency of the current element 
   int max_frequency = 0; // frequency of the mode 
   int mode = array[0]; // start with the first element 

   for (int i=0; i < size -1; i++) {

      if (array[i] == array[i+1]) { 
         frequency++; 

         if(frequency > max_frequency) { 
            max_frequency = frequency; 
            mode = array[i]; 
         }

      }
      else frequency = 1; // reset the counter
   }

   return mode;
}



int main() 
{
   const int size = 9;
   int numbers[size] =  { 3, 2, 4, 5, 1, 1, 2, 2, 3 };
   
   std::sort( std::begin(numbers), std::end(numbers) );

   float mean   = CalcMean( numbers, size);
   float median = CalcMedian( numbers, size);
   float mode   = CalcMode( numbers, size);

   std::cout << "Mean   : " << mean << std::endl;
   std::cout << "Median : " << median << std::endl;
   std::cout << "Mode   : " << mode << std::endl;
    
   return 0;
}

~>./MeanMedianMode
Mean   : 2.55556
Median : 2
Mode   : 2

September 3rd

Search algorithms: linear search

Example:Linear search in an array

void LinearSearch(int arr[], int value)
{
    int pos = -1; // index of the item we are searching for 

    for(int i=0; i< sizeof(arr) / sizeof(arr[0]); i++) {
        if(value == arr[i]) pos = i;
        break;
    }

    return pos;
}

std::vector<int> v;

// Finds the first element in the vector that has the value 42:
// If there is no such value, it == v.end()
std::vector<int>::const_iterator it = std::find(v.begin(), v.end(), 42);

Binary search

Example: There are many use cases of searching a sorted collection in daily life. A dictionary is a sorted list of word definitions. Given a word, one can find its definition. A telephone book is a sorted list of people's names, addresses, and telephone numbers. Knowing someone's name allows one to quickly find their telephone number and address.

Here is a simple example of binary search in an array:

int BinarySearch(int arr[], int value, int min, int max) 
{

  int pos = -1; // index of the item we are searching for 

  while (max >= min && pos == -1) {
    int mid = min + (max-min)/2;

    if(arr[mid] ==  value) pos = mid;
    else if(arr[mid] < value) min = mid++;
    else if(arr[mid] > value) max = mid--;
  }
  return pos;
}

   std::vector<int> v;

// Finds whether an element in the vector that has the value 42 or not:
   bool found = std::binary_search(v.begin(), v.end(), 42);

// Now, let's say we want to insert 11 and 14 into the sorted vector
  std::vector<int>::iterator where;
  where = std::lower_bound(v.begin(), v.end(), 11);
  v.insert(where, 11);

  where = std::upper_bound(v.begin(), v.end(), 14);
  v.insert(where, 14);

Search by hashing

Open Addressing:
One way to resolve collisions is to place the colliding record in another location that is still open. This storage algorithm is called open-addressing. Open addressing requires that the array be initialized so that the program can test if an array position already contains a record.
With this method of resolving collisions, we still must decide how to choose the locations to search for an open position when a collision occurs... There are 2 main ways to do so.

1. Linear Probing: Uses the following algorithm:

1. For a record with given key, compute the index hash(key).
2. If data[hash(key)] does not already contain a record, then store the record in data[hash(key)] and end the storage algorithm.
3. If the location data[hash(key)] already contains a record then try data[hash(key)+1]. If that location already contains a record, try data[hash(key)+2], and so forth until a vacant position is found. When the highest numbered array position is reached, simply go to the start of the array. For example, if the array indices are 0..99, and 98 is the key, then try 98,99,0,1 and so on, in that order. Searching for a vacant spot in this manner is called linear probing.

3. Let i = hash(key). If the location data[i] already contains a record then let i = (i+hash2(key)) % SIZE, and try the new data[i]. If that location already contains a record, then let i= (i+hash2(key)) % SIZE, and try that data[i], and so forth until a vacant position is found.

1. hash2(key) = 1 + ( key % (SIZE-2) )
2. hash2(key) = max(1, (key / SIZE) % SIZE)

Comparison of search algorithms

• If the list to be searched contains more than a few items (a dozen, say) a binary search will require far fewer comparisons than a linear search, but it imposes the requirement that the list be sorted.
• Similarly, a hash search can be faster than a binary search but imposes still greater requirements. If the contents of the array are modified between searches, maintaining these requirements may even take more time than the searches.
• If it is known that some items will be searched for much more often than others, and it can be arranged so that these items are at the start of the list, then a linear search may be the best.

Example1: Here is a simple program to computate hash key for a string:

#include <iostream>
#include <functional>
#include <string>
 
int main()
{
   std::string str = "I am sitting in my office ...";
   std::hash hash_fn;
   std::size_t str_hash = hash_fn(str);
 
   std::cout << "Hash table key value is:" << str_hash << std::endl;
}

Hash table key value is:10134380172069548041

Example2: A program to compare hash keys:

#include <iostream>
#include <functional>
#include <string>

int main ()
{
  char char1[] = "Test";
  char char2[] = "Test";
  std::string str1 (char1);
  std::string str2 (char2);

  std::hash ptr_hash;
  std::hash str_hash;

  std::cout << "Same hashes:\n" << std::boolalpha;
  std::cout << "char1 and char2: " << (ptr_hash(char1)==ptr_hash(char2)) << '\n';
  std::cout << "str1 and str2: " << (str_hash(str1)==str_hash(str2)) << '\n';

  return 0;
}

Same hashes:
char1 and char2: false
str1  and str2:  true

Example3: The following program demonstrates creation of a hash function for a user defined type.

#include <iostream>
#include <functional>
#include <string>
 
struct S
{
    std::string first_name;
    std::string last_name;
};
 
template <class T>
class MyHash;
 
template<>
class MyHash<S>
{
public:
    std::size_t operator()(S const& s) const 
    {
        std::size_t h1 = std::hash<std::string>()(s.first_name);
        std::size_t h2 = std::hash<std::string>()(s.last_name);
        return h1 ^ (h2 << 1);
    }
};
 
int main()
{
    std::string s1 = "Kalanand";
    std::string s2 = "Mishra";
    std::hash<std::string> h1;
 
    S n1;
    n1.first_name = s1;
    n1.last_name =  s2;
 
    std::cout << "s1 = " << s1.c_str() << std::endl;
    std::cout << "s2 = " << s2.c_str() << std::endl;
    std::cout << "n1 = " << s1.c_str()  << " " 
              << s2.c_str() << std::endl << std::endl;

    std::cout << "hash(s1) = " << h1(s1) << "\n"
              << "hash(s2) = " << std::hash<std::string>()(s2) << "\n"
              << "hash(n1) = " << MyHash<S>()(n1) << "\n";
 
}

s1 = Kalanand
s2 = Mishra
n1 = Kalanand Mishra

hash(s1) = 9491039084864179940
hash(s2) = 5501961356046300852
hash(n1) = 1946461744545948556

September 4th

Card shuffling and dealing program

#include<iostream>
#include<ctime>

void shuffle( int deck[][13] ) 
{
   int row, column;

   for (int card = 1; card <= 52; card++) {
      do {
         row = rand() % 4;
         column = rand() % 13;
      }
      while ( deck[row][column] !=0);

      deck[row][column] = card;
   }
}


void deal( int deck[][13], const char* face[], const char* suit[] )
{
   for (int card = 1; card <= 52; card++) 
      for (int row = 0; row < 4; row++) 
         for (int column = 0; column < 13; column++) 
            if(deck[row][column] == card) 
               std::cout << face[column] << " of " << suit[row] 
                         << (card %2 == 0 ? '\n' : '\t');
}


int main() 
{
   const char* suit[4] = {"Hearts", "Diamonds", "Clubs", "Spades"};
   const char* face[13] = {"Ace", "Deuce", "Three", "Four", "Five", 
                           "Six", "Seven", "Eight", "Nine", "Ten", 
                           "Jack", "Queen", "King"};
   int deck[4][13] = {0};

   srand( time(0) );
   shuffle(deck);
   deal(deck, face, suit); 

   return 0;
}

Jack of Clubs       Seven of Spades
Queen of Diamonds   King of Clubs
Six of Hearts       Five of Diamonds
Ten of Clubs        Ace of Clubs
Deuce of Spades     Ten of Spades
Four of Spades      Five of Hearts
Queen of Clubs      Three of Spades
Ten of Diamonds     Seven of Hearts
Five of Clubs       Deuce of Clubs
Nine of Hearts      Deuce of Diamonds
Queen of Spades     Seven of Diamonds
Eight of Clubs      Ace of Diamonds
Four of Hearts      Eight of Diamonds
Five of Spades      Six of Clubs
Jack of Diamonds    Ace of Spades
Six of Spades       Three of Diamonds
Deuce of Hearts     Jack of Spades
Three of Clubs      Queen of Hearts
Six of Diamonds     Four of Diamonds
Ace of Hearts       King of Diamonds
Nine of Diamonds    Seven of Clubs
Nine of Clubs       Three of Hearts
Ten of Hearts       Eight of Hearts
Eight of Spades     Nine of Spades
Four of Clubs       King of Spades
Jack of Hearts      King of Hearts

String manipulation in C++: examples

#include <iostream>
#include <algorithm>

int main() 
{
   char first_name[] = "Kalanand ", last_name[] = "Mishra";
   char* name = strcat(first_name, last_name);
   char name_copy[20]; 


   /* Copy, concatenate, and find length */
   strcpy(name_copy, name);
   std::cout << "name = " << name << ",  length = " << strlen(name) << "\n";
   std::cout << "Copy of the name = " << name_copy << "\n";

   std::cout << "strcmp(name, last_name) = " 
             << strcmp(name, last_name) << "\n";

   std::cout << "strncmp(name, first_name, 8) = " 
             << strncmp(name, first_name, 8) << "\n";



   /* Break the string into pieces */
   char* token = strtok(name, " ");
   std::cout << "tokens: ";

   while( token != NULL ) { 
      std::cout << token << " ";
      token = strtok( NULL, " ");
   }

   std::cout << std::endl;


   /* Convert the name to upper case */
   char s[20] = "kalanand Mishra";
   std::transform( std::begin(s), std::end(s), std::begin(s), toupper);
   std::cout << "All in upper case: " << s << std::endl;

   /* Convert the name to lower case */
   std::transform( std::begin(s), std::end(s), std::begin(s), tolower);
   std::cout << "All in lower case: " << s << std::endl;


   return 0;
}

name = Kalanand Mishra,  length = 15
Copy of the name = Kalanand Mishra
strcmp(name, last_name) = -2
strncmp(name, first_name, 8) = 0
tokens: Kalanand Mishra 
All in upper case: KALANAND MISHRA
All in lower case: kalanand mishra

Function pointers

#include <iostream>

void function1( int a) 
{
   std::cout << "You entered " << a << " so function1 was called\n\n";
}


void function2( int b) 
{
   std::cout << "You entered " << b << " so function2 was called\n\n";
}


void function3( int c) 
{
   std::cout << "You entered " << c << " so function3 was called\n\n";
}


int main() 
{
void (*f[3]) (int) = {function1, function2, function3};
int choice;

std::cout << "Enter an integer to run this program: ";
std::cin >> choice;

(*f[choice %3])(choice); 

return 0;
}

Rotating a matrix

• Transpose
• Reverse each row

• Transpose
• Reverse each column

• Method 1: Rotate by +90 degrees or -90 degrees twice
• Method 2: Reverse each row and then reverse each column or vice versa

Here is an example code to demonstrate the rotation of a 4x4 matrix.

#include <iostream>

/*
int** getRotate90PlusMatrix(int array[][4], int size) 
{
   int** rotated = new int*[size];

   for (int i = 0; i < size; i++)
      for (int j = 0; j < size; j++)
         rotated[i][j]  =  array[j][size-1-i];

   return rotated;
}
*/



void Rotate90Plus(int array[][4], int size) 
{
   int n = size, temp;

   for (int i = 0; i < n/2; i++) {
      for (int j = 1; j < n-i; j++) { 

         temp                 =  array[i][j];
         array[i][j]          =  array[j][n-1-i];
         array[j][n-1-i]      =  array[n-1-i][n-1-j];
         array[n-1-i][n-1-j]  =  array[n-1-j][i];
         array[n-1-j][i]      =  temp;
      }
   }

}



void Rotate90Minus(int array[][4], int size) 
{
   int n = size, temp;

   for (int i = 0; i < n/2; i++) {
      for (int j = 1; j < n-i; j++) { 

         temp                 =  array[i][j];
         array[i][j]          =  array[n-1-j][i];
         array[n-1-j][i]      =  array[n-1-i][n-1-j];
         array[n-1-i][n-1-j]  =  array[j][n-1-i];
         array[j][n-1-i]      =  temp;
      }
   }

}



void Rotate180(int array[][4], int size) 
{
   int n = size;

   for (int i = 0; i < n/2; i++) 
      for (int j = 0; j < n; j++) 
         std::swap( array[i][j], array[n-1-i][n-1-j] );
}






void PrintMatrix(int array[][4], int size) 
{
   for (int i=0; i < size; i++) {

      if(i%4) std::cout << "\n";
      for (int j=0; j < size; j++)
         std::cout << array[i][j] << "  ";
   }

   std::cout << "\n";
}



int main()
{
   int a[4][4] = { {1, 2, 3, 4}, {5, 6, 7, 8}, {9, 0, 1, 2}, {3, 4, 5, 6} };

   std::cout << "Original matrix: " << std::endl;
   PrintMatrix(a, 4);


   Rotate90Plus(a, 4);
   std::cout << "\nRotated original matrix +90 degree: " << std::endl;
   PrintMatrix(a, 4);



   Rotate90Minus(a, 4);
   std::cout << "\nRotated previous matrix -90 degree: " << std::endl;
   PrintMatrix(a, 4);



   Rotate180(a, 4);
   std::cout << "\nRotated original matrix 180 degree: " << std::endl;
   PrintMatrix(a, 4);

   return 0;
}

Original matrix: 
1  2  3  4  
5  6  7  8  
9  0  1  2  
3  4  5  6  

Rotated original matrix +90 degree: 
4  8  2  6  
3  1  0  5  
2  7  6  4  
1  5  9  3  

Rotated previous matrix -90 degree: 
1  2  3  4  
5  6  7  8  
9  0  1  2  
3  4  5  6  

Rotated original matrix 180 degree: 
6  5  4  3  
2  1  0  9  
8  7  6  5  
4  3  2  1  

September 5th

Some observations about C++ classes

• The constructor is a special member function with the same name as the class that is used to initialize the members of the class object. The constructor is called when an object of that class is instantiated.
• Constructors can be overloaded. Constructors can specify default arguments.
• Constructors cannot specify return type and cannot attempt to return values.
• When an object of a class is declared, initializers can be provided. These initializers are passed to the class's constructor.
• It is possible for a class not to have a default constructor. However, if no constructor is defined, the compiler creates a default/dummy constructor. A default constructor supplied by the compiler doesn't perform any initialization, so when the object is created it is not guaranteed to be in a consistent state.
• The destructor of an automatic object is called when the object goes out of scope.
• Destructors do not receive parameters and do not return values. A class can have only one destructor. Destructors cannot be overloaded.
• Attempting to declare a constructor or destructor const is a syntax error.
• The default access mode for classes is private, so all members after the class header and before the first member access specifier are considered to be private.
• Data members of a class cannot be initialized in the class definition. They must be initialized in a constructor, or their values may be set after their object is created.
• One should use #ifdef, #define, and #endif preprocessor directives to prevent header files from included more than once in a program.
• For reasons of economy of storage, only one copy of each member function exists per class, and this member function is invoked by every object of that class. Each object, on the other hand, has its own copy of the class's data members.
• A friend function of a class is a function defined outside that class and that has the right to access all members of the class. Friendship declaration can be placed anywhere in the class definition.
• Describing the functionality of a class independent of its implementation is called data abstraction. C++ classes define abstract data types (ADTs). ADTs are ways of representing real-world notions to some satisfactory level of precision.

Operator overloading

• To overload an operator, write a function definition; the function name must be the key word operator followed by the symbol for the operator being overloaded.
• It is not possible to change the number of operands an operator takes. Overloaded unary operators remain unary; overloaded binary operators still remain binary. C++'s only ternary operator, ?:, cannot be overloaded.
• It is not possible to create symbols for new operators; only existing operators may be overloaded.

Inheritance, polymorphism

• A class from which objects can be instantiated are called concrete classes.
• A class is made abstract by declaring one or more of its virtual functions pure. A pure virtual function is one with an initializer of = 0 in its declaration.
• If a class is derived from a class with a pure virtual function without supplying a definition for the pure virtual function in the derived class, then the derived class is also an abstract class and cannot have any objects.
• C++ enables polymorphism - the ability for objects of different classes related by inheritance to respond differently to the same member function call. Polymorphism is implemented via virtual functions.
• A derived class cannot access the private members of its base class. However, it can access the public and protected members of its base class.
• A derived-class constructor always calls the constructor of its base class first to create and initialize the derived class's base-class members. Destructors are called in the reverse order, so a derived-class destructor is called before its base-class destructor.
• The implementation of a derived class doesn't need access to the source code of a base class, but does need the interface to the base class and the base class's object code.
• A derived class cannot directly access private members of its base class.
• Dynamic binding requires that at execution time, the call to a virtual member function be routed to the virtual function version appropriate for the class. A virtual function table called the vtable is implemented as an array containing function pointers. Each class that contains virtual functions has a vtable. For each virtual function in the class, the vtable has an entry containing a function pointer to the version of the virtual function to use for an object of that class.
• Any class that has one or more 0 pointers in its vtable is an abstract class. Classes without any 0 vtable pointers are concrete classes.

September 9th

Checking dependencies

checkdeps

checkdeps -a

September 12th

Checking memory leak using valgrind

valgrind --tool=memcheck `cmsvgsupp` --leak-check=yes --show-reachable=yes --num-callers=20 --track-fds=yes cmsRun your_cfg.py >& test01.out &

September 16th

Custom build

scram b clean
scram b -v -k USER_CXXFLAGS="-O0\ -g" >& build01.log &

Go to August's log