Configuring password less access to remote systems using ssh-keygen utility

When we say password less authentication, we mean that the client authentication is carried out using public and private keys.

Generate public/private key pair
The ssh-keygen utility is used to generate the public/private key pair. The keys generated are stored under .ssh directory in the user home directory. The private key is never shared and stored in the local machine whereas the public key is distributed to the machines you want to login to.

Read more ...

Installing And Configuring SSH server on Windows

We will be making use of Cygwin utilities to configure and run ssh as service on windows machine. Installing Cygwin on a windows machine is pretty straight forward. Download the latest Cygwin installation setup.exe from the Cygwin site and follow the below instructions.

1. Installing Cygwin
Step 1. Double click setup.exe

Step 2. Choose the download source

Step 3. Select the root directory of the Cygwin. This directory is synonymous to / in linux

Step 4. Select the directory where you want to keep the installation files. You can save this directory and use at a later point to install Cygwin on any windows machine using this directory.

Click 'OK' if prompted to create the directory if it does not exists

Step 5. Select the type of connection you are using to connect to internet.

Step 6. Choose a download site.

Step 7. Clicking next opens up the 'Select Packages' screen.

Step 8. Select the Open SSH server and client programs from the 'Select Packages' screen.

Step 9. Click next to start the installation.

This will install the following utilities in your Cygwin's /usr/bin directory

ssh-add.exe
ssh-agent.exe
ssh-host-config
ssh-keygen.exe
ssh-keyscan.exe
ssh-user-config
ssh.exe

2. Configuring ssh as Windows service

Run ssh-host-config utility to configure sshd server on windows. Select 'no' when prompted for 'Should privilege separation be used? (yes/no)'. Select 'yes' when prompted for 'Do you want to install sshd as service?'. Choose default options for other options.

The above will install CYGWIN sshd service on Windows. To start the service execute

net start sshd

3. Connecting using Cygwin ssh client (ssh.exe)

ssh.exe user@ssh-server

4. Connecting through putty

Add the server's host key to registry. This will add an entry into the ~/.ssh/known_hosts file

Login using windows user and password

Read more ...

Reverse a stack in place

Write a C/C++ Program to reverse a stack in place?

You can only use the following ADT functions on the stack:
1. empty()
2. push()
3. pop()
4. top()

Solution:
1. Whenever in place conversion is required, use recursion which will make use of function stack to store the variables
2. Pop out all the elements from the given stack recursively and store them in a variable.
3. As the stack unwinding happens, push the variable obtained at each unwinding step to the bottom of the stack. Refer method push_to_bottom below

//pop out all the elements, use function stack to store the elements
void stack_reverse(std::stack<int> &s)
{
  if(s.empty())
  {
    return;
  }
  int elem = s.top(); s.pop();
  stack_reverse(s);

  //pass the element obtained during the unwinding of the function 
  //stack and store it at the bottom of the given stack 's'
  push_to_bottom(s, elem);
}

void push_to_bottom(std::stack<int> &s, int elem)
{
  //stack is empty so elem will be placed at the bottom of the stack 's'
  if(s.empty())
  {
    s.push(elem);
    return;
  }

  //stack is not empty, so popping out the elements, using function
  //stack to store the elements and storing the given element at the
  //bottom of the given stack 's'
  int top = s.top(); s.pop();
  push_to_bottom(s, elem);
  s.push(top);
}

Read more ...

Traversing a Binary Tree

There are basically two ways of traversing a binary tree
1. Depth First Traversals
2. Breadth First Traversal

Depth First Traversal
A binary tree can be traversed in three ways using the depth first approach namely

1. Inorder Traversal

template <typename T>
  void BTTraveller<T>::inOrder(BSTNode<T> *node, std::deque<T> &out)
  {
    if(node)
    {
      inOrder(node->left, out);
      out.push_back(node->key);
      inOrder(node->right, out);
    }
  }

2. Preorder Traversal

template <typename T>
  void BTTraveller<T>::preOrder(BSTNode<T> *node, std::deque<T> &out)
  {
    if(node)
    {
      out.push_back(node->key);
      preOrder(node->left, out);
      preOrder(node->right, out);
    }
  }

3. Postorder Traversal

template <typename T>
  void BTTraveller<T>::postOrder(BSTNode<T> *node, std::deque<T> &out)
  {
    if(node)
    {
      postOrder(node->left, out);
      postOrder(node->right, out);
      out.push_back(node->key);
    }
  }

Breadth First Traversal
There is only one kind of Breadth first traversal viz. Level Order traversal. This traversal does not move along the branches of the tree but makes use of a FIFO queue. In the sample code, I have used std::deque as the helper queue for achieving the same.

template <typename T>
  void BTTraveller<T>::levelOrder(BST<T> *bstree, std::deque<T> &out)
  {
    std::deque<BSTNode<T>*> hQ;
    hQ.push_back(bstree->m_root);
    levelOrder(hQ, out);
  }

  template <typename T>
  void BTTraveller<T>::levelOrder(std::deque<BSTNode<T>*> &hQ, std::deque<T> &out)
  {
    while(hQ.empty() == false)
    {
      BSTNode<T> *current = hQ.front();
      if(current != NULL)
      {
        hQ.pop_front();
        out.push_back(current->key);
        addChildren(current, hQ);
      }
    }
  }

The BTTraveller class takes care of returning Binary Tree node elements in the order you are traversing the tree.

 1 #ifndef _BTTraveller_H_
 2 #define _BTTraveller_H_
 3 #include "BSTNode.h"
 4 #include <deque>
 5 
 6 //File: BTTraveller.h
 7 namespace algorithms
 8 {
 9   template <typename T>
10   class BTTraveller
11   {
12   public:
13     static void inOrder(BST<T> *bstree, std::deque<T> &elems);
14     static void preOrder(BST<T> *bstree, std::deque<T> &elems);
15     static void postOrder(BST<T> *bstree, std::deque<T> &elems);
16     static void levelOrder(BST<T> *bstree, std::deque<T> &elems);
17 
18   private:
19     static void inOrder(BSTNode<T> *node, std::deque<T> &elems);
20     static void preOrder(BSTNode<T> *node, std::deque<T> &elems);
21     static void postOrder(BSTNode<T> *node, std::deque<T> &elems);
22     static void levelOrder(std::deque<BSTNode<T>*> &helperQ, std::deque<T> &elems);
23     static void addChildren(BSTNode<T> *node, std::deque<BSTNode<T>*> &helperQ);
24 
25     BTTraveller();
26     BTTraveller(const BTTraveller&);
27     const BTTraveller& operator=(const BTTraveller&);
28   };
29 };
30 
31 #include "BTTraveller.hpp"
32 #endif //_BTTraveller_H_

 1 //File: BTTraveller.hpp
 2 namespace algorithms
 3 {
 4   template <typename T>
 5   void BTTraveller<T>::inOrder(BST<T> *bstree, std::deque<T> &out)
 6   {
 7     inOrder(bstree->m_root, out);
 8   }
 9 
10   template <typename T>
11   void BTTraveller<T>::preOrder(BST<T> *bstree, std::deque<T> &out)
12   {
13     preOrder(bstree->m_root, out);
14   }
15 
16   template <typename T>
17   void BTTraveller<T>::postOrder(BST<T> *bstree, std::deque<T> &out)
18   {
19     postOrder(bstree->m_root, out);
20   }
21 
22   template <typename T>
23   void BTTraveller<T>::levelOrder(BST<T> *bstree, std::deque<T> &out)
24   {
25     std::deque<BSTNode<T>*> hQ;
26     hQ.push_back(bstree->m_root);
27     levelOrder(hQ, out);
28   }
29 
30   template <typename T>
31   void BTTraveller<T>::inOrder(BSTNode<T> *node, std::deque<T> &out)
32   {
33     if(node)
34     {
35       inOrder(node->left, out);
36       out.push_back(node->key);
37       inOrder(node->right, out);
38     }
39   }
40 
41   template <typename T>
42   void BTTraveller<T>::preOrder(BSTNode<T> *node, std::deque<T> &out)
43   {
44     if(node)
45     {
46       out.push_back(node->key);
47       preOrder(node->left, out);
48       preOrder(node->right, out);
49     }
50   }
51 
52   template <typename T>
53   void BTTraveller<T>::postOrder(BSTNode<T> *node, std::deque<T> &out)
54   {
55     if(node)
56     {
57       postOrder(node->left, out);
58       postOrder(node->right, out);
59       out.push_back(node->key);
60     }
61   }
62 
63   template <typename T>
64   void BTTraveller<T>::levelOrder(std::deque<BSTNode<T>*> &hQ, std::deque<T> &out)
65   {
66     while(hQ.empty() == false)
67     {
68       BSTNode<T> *current = hQ.front();
69       if(current != NULL)
70       {
71         hQ.pop_front();
72         out.push_back(current->key);
73         addChildren(current, hQ);
74       }
75     }
76   }
77 
78   template <typename T>
79   void BTTraveller<T>::addChildren(BSTNode<T> *node, std::deque<BSTNode<T>*> &hQ)
80   {
81     if(node->left != NULL)
82     {
83       hQ.push_back(node->left);
84     }
85     if(node->right != NULL)
86     {
87       hQ.push_back(node->right);
88     }
89   }
90 }

You need to include BTTraveller class as a friend class in both the BSTNode as well as BST class declarations. This ensures that the BTTraveller class has access to private data members of these two classes

The BSTNode class

 1 #ifndef _BSTNode_H_
 2 #define _BSTNode_H_
 3 #include <iostream>
 4 
 5 //File: BSTNode.h
 6 namespace algorithms
 7 {
 8   template <typename T>
 9   class BST;
10 
11   template <typename T>
12   class BTTraveller;
13 
14   template <typename T>
15   class BSTNode
16   {
17   public:
18     BSTNode(T key);
19     ~BSTNode();
20 
21     friend class BST<T>;
22     friend class BTTraveller<T>;
23 
24   private:
25     BSTNode<T> *left;
26     BSTNode<T> *right;
27     T key;
28   };
29 };
30 
31 #include "BSTNode.hpp"
32 #endif //_BSTNode_H_

The BST class

 1 #ifndef _BinarySearchTree_H_
 2 #define _BinarySearchTree_H_
 3 #include "BSTNode.h"
 4 
 5 //File: BST.h
 6 namespace algorithms
 7 {
 8   template <typename T>
 9   class BTTraveller;
10 
11   template <typename T>
12   class BST
13   {
14   public:
15     BST();
16     ~BST();
17 
18     //modifiers
19     void insert(T key);
20     void remove(T key);
21     void clear();
22 
23     //accessors
24     bool find(T key);
25     bool isEmpty() const;
26 
27     friend class BTTraveller<T>;
28 
29   private:
30     void remove(BSTNode<T> **node);
31     void clear(BSTNode<T> *node);
32     BSTNode<T>** find(BSTNode<T> **node, const T key);
33     BSTNode<T>** getSuccessor(BSTNode<T> **node);
34     BSTNode<T>* getNewNode(T key);
35 
36     //instance fields
37     BSTNode<T> *m_root;
38   };
39 };
40 
41 #include "BST.hpp"
42 #endif //_BinarySearchTree_H_

The BSTNode.hpp and BST.hpp files remains the same as in the post
The Client Program

 1 #include "BST.h"
 2 #include "BTTraveller.h"
 3 #define MAX 20
 4 using namespace algorithms;
 5 
 6 //File: Main.cpp
 7 
 8 template <typename T>
 9 void DumpDeque(std::deque<T> &q)
10 {
11   std::cout << std::endl;
12   std::deque<T>::const_iterator itr;
13   for(itr = q.cbegin(); itr != q.cend(); ++itr)
14   {
15     std::cout << *itr << " ";
16   }
17   std::cout << std::endl;
18   q.clear();
19 }
20 
21 int main(int argc, char *argv[])
22 {
23   int nodes[MAX] = { 50, 40, 60, 70, 80, 20, 30, 10, 90, 15, 35, 65, 75, 5, 1, 100, 110, 130, 120, 111 };
24   BST<int> bstInt;
25   for(int i = 0; i < MAX; ++i)
26   {
27     bstInt.insert(nodes[i]);
28   }
29 
30   std::deque<int> elems;
31   BTTraveller<int>::inOrder(&bstInt, elems);
32   DumpDeque(elems);
33   BTTraveller<int>::preOrder(&bstInt, elems);
34   DumpDeque(elems);
35   BTTraveller<int>::postOrder(&bstInt, elems);
36   DumpDeque(elems);
37   BTTraveller<int>::levelOrder(&bstInt, elems);
38   DumpDeque(elems);
39 
40   return 0;
41 }

Output

$ ./BinarySearchTree.exe

1 5 10 15 20 30 35 40 50 60 65 70 75 80 90 100 110 111 120 130

50 40 20 10 5 1 15 30 35 60 70 65 80 75 90 100 110 130 120 111

1 5 15 10 35 30 20 40 65 75 111 120 130 110 100 90 80 70 60 50

50 40 60 20 70 10 30 65 80 5 15 35 75 90 1 100 110 130 120 111

Read more ...

A Binary Search Tree Example

A Binary Tree is a tree where each node may have 0, 1 or 2 children and a Binary Search Tree is a binary tree with a special property that the value of node under discussion is less than all the nodes in its right subtree and greater than all the nodes in its left subtree.
The programs below describes the three basic operations in a binary search tree viz. search, insert and remove

1. Searching a node

  template <typename T>
  BSTNode<T>** BST<T>::find(BSTNode<T> **node, const T key)
  {
    if(*node == NULL || (*node)->key == key)
    {
      return node;
    }
    else if((*node)->key > key)
    {
      return find(&(*node)->left, key);
    }
    else
    {
      return find(&(*node)->right, key);
    }
  }

2. Inserting a node

template <typename T>
  void BST<T>::insert(T key)
  {
    BSTNode<T> **node = find(&m_root, key);
    if(*node == NULL)
    {
      *node = getNewNode(key);
    }
  }

3. Removing a node
Removing a node from binary search tree is the trickiest of all the operations. There are three cases to be considered when removing a node from a binary search tree:

Case 1. If both left and right child are null, the node can simply be deleted.

Case 2. If only one of the right child or left child is null, the address of the node is set to point to the left child or the right child which ever is not null and the current node is deleted.

Case 3. The complex of the three cases, if both left and right child are present. This requires finding the successor of the current node which is to be removed.

template <typename T>
  void BST<T>::remove(BSTNode<T> **node)
  {
    BSTNode<T> *old = *node;
    if((*node)->left == NULL)
    {
      *node = (*node)->right;
      delete old;
    }
    else if((*node)->right == NULL)
    {
      *node = (*node)->left;
      delete old;
    }
    else
    {
      BSTNode<T> **successor = getSuccessor(node);
      (*node)->key = (*successor)->key;
      remove(successor);
    }
  }

Following is the complete example showing the implementation details of the search, find and remove operations in a binary search tree.

The BST Node Class

 1 #ifndef _BSTNode_H_
 2 #define _BSTNode_H_
 3 #include <iostream>
 4 
 5 //File: BSTNode.h
 6 namespace algorithms
 7 {
 8   template <typename T>
 9   class BST;
10 
11   template <typename T>
12   class BSTNode
13   {
14   public:
15     BSTNode(T key);
16     ~BSTNode();
17 
18     friend class BST<T>;
19 
20   private:
21     BSTNode<T> *left;
22     BSTNode<T> *right;
23     T key;
24   };
25 };
26 
27 #include "BSTNode.hpp"
28 #endif //_BSTNode_H_

 1 //File: BSTNode.hpp
 2 namespace algorithms
 3 {
 4   template <typename T>
 5   BSTNode<T>::BSTNode(T key) : left(0), right(0)
 6   {
 7     this->key = key;
 8   }
 9 
10   template <typename T>
11   BSTNode<T>::~BSTNode()
12   {
13   }
14 }
15 

The Binary Search Tree Class

 1 #ifndef _BinarySearchTree_H_
 2 #define _BinarySearchTree_H_
 3 #include "BSTNode.h"
 4 
 5 //File: BST.h
 6 namespace algorithms
 7 {
 8   template <typename T>
 9   class BST
10   {
11   public:
12     BST();
13     ~BST();
14 
15     //modifiers
16     void insert(T key);
17     void remove(T key);
18     void clear();
19 
20     //accessors
21     bool find(T key);
22     bool isEmpty() const;
23 
24   private:
25     void remove(BSTNode<T> **node);
26     void clear(BSTNode<T> *node);
27     BSTNode<T>** find(BSTNode<T> **node, const T key);
28     BSTNode<T>** getSuccessor(BSTNode<T> **node);
29     BSTNode<T>* getNewNode(T key);
30 
31     //instance fields
32     BSTNode<T> *m_root;
33   };
34 };
35 
36 #include "BST.hpp"
37 #endif //_BinarySearchTree_H_

  1 //File: BST.hpp
  2 namespace algorithms
  3 {
  4   template <typename T>
  5   BST<T>::BST()
  6   {
  7     m_root = 0;
  8   }
  9 
 10   template <typename T>
 11   BST<T>::~BST()
 12   {
 13     clear();
 14   }
 15 
 16   template <typename T>
 17   void BST<T>::clear()
 18   {
 19     clear(m_root);
 20   }
 21 
 22   template <typename T>
 23   void BST<T>::clear(BSTNode<T> *node)
 24   {
 25     if(node != NULL)
 26     {
 27       clear(node->left);
 28       clear(node->right);
 29       delete node;
 30     }
 31   }
 32 
 33   template <typename T>
 34   void BST<T>::insert(T key)
 35   {
 36     BSTNode<T> **node = find(&m_root, key);
 37     if(*node == NULL)
 38     {
 39       *node = getNewNode(key);
 40     }
 41   }
 42 
 43   template <typename T>
 44   void BST<T>::remove(T key)
 45   {
 46     BSTNode<T> **node = find(&m_root, key);
 47     remove(node);
 48   }
 49 
 50   template <typename T>
 51   void BST<T>::remove(BSTNode<T> **node)
 52   {
 53     BSTNode<T> *old = *node;
 54     if((*node)->left == NULL)
 55     {
 56       *node = (*node)->right;
 57       delete old;
 58     }
 59     else if((*node)->right == NULL)
 60     {
 61       *node = (*node)->left;
 62       delete old;
 63     }
 64     else
 65     {
 66       BSTNode<T> **successor = getSuccessor(node);
 67       (*node)->key = (*successor)->key;
 68       remove(successor);
 69     }
 70   }
 71 
 72   template <typename T>
 73   BSTNode<T>** BST<T>::getSuccessor(BSTNode<T> **node)
 74   {
 75     BSTNode<T> **tmp = &(*node)->left;
 76     while((*tmp)->right != NULL)
 77     {
 78       tmp = &(*tmp)->right;
 79     }
 80     return tmp;
 81   }
 82 
 83   template <typename T>
 84   bool BST<T>::find(const T key)
 85   {
 86     BSTNode<T> **pos = find(&m_root, key);
 87     return *pos != NULL;
 88   }
 89 
 90   template <typename T>
 91   bool BST<T>::isEmpty() const
 92   {
 93     return m_root == 0;
 94   }
 95 
 96   template <typename T>
 97   BSTNode<T>** BST<T>::find(BSTNode<T> **node, const T key)
 98   {
 99     if(*node == NULL || (*node)->key == key)
100     {
101       return node;
102     }
103     else if((*node)->key > key)
104     {
105       return find(&(*node)->left, key);
106     }
107     else
108     {
109       return find(&(*node)->right, key);
110     }
111   }
112 
113   template <typename T>
114   BSTNode<T>* BST<T>::getNewNode(T key)
115   {
116     BSTNode<T> *node = new BSTNode<T>(key);
117     if(node == NULL)
118     {
119       std::cerr << "ERROR: Insufficient Memory";
120       std::cerr << std::endl;
121     }
122     return node;
123   }
124 }

The Client Program for testing the BST code above

 1 #include "BST.h"
 2 #define MAX 20
 3 using namespace algorithms;
 4 
 5 //File: Main.cpp
 6 int main(int argc, char *argv[])
 7 {
 8   int nodes[MAX] = { 50, 40, 60, 70, 80, 20, 30, 10, 90, 15, 35, 65, 75, 5, 1, 100, 110, 130, 120 };
 9   BST<int> bstInt;
10   for(int i = 0; i < MAX; ++i)
11   {
12     bstInt.insert(nodes[i]);
13   }
14 
15   std::cout << (bstInt.find(130) ? "true" : "false");
16   bstInt.remove(50);
17   std::cout << (bstInt.find(50)  ? "true" : "false");
18 
19   return 0;
20 }

Output of the run
$ ./BinarySearchTree.exe
truefalse

Read more ...