Heaps : Algorithms

Heaps

Heap is a kind of data structures based on complete tree principle. By definition, a complete binary search tree of N levels has at least 2^N-1 nodes in it. Heap is nearly complete tree. Heap maintains a property called as heap property which holds across all nodes of the heap. 
There are two kinds of heaps we frequently deal with :

Max Heap : It maintains the property that every parent node is greater than its children. Root of the max heap is greatest element.

Min Heap : It maintains the property that every parent node is less than its children. Root of the min heap is least element.

Read more

Binary Search Tree : Bottom up approach to problems

Introduction

In Binary Search Tree, there is a class of problems which have solutions with similar structure.

These problems involve deletion of complete BST, mirroring a BST, replacing parent node with sum of children etc. In this post we would discuss the structure of the solution and their execution in run time in detail. Once this strategy is mastered, most of the BST problems can be solved easily.

Problem statement

1. Delete a given Binary Search Tree

2. Mirror a give Binary Search Tree i.e. Left child should become right and right should become left.

3. Replace the value of a node with sum of its children nodes.

Analysis

Problem 1 :Delete a BST

To delete a binary search tree, we start with leaf nodes. Once all leaf nodes are deleted, we move to upper layer which in turn would have become leaf nodes now. We continue to do so till the time we reach root node and then delete root node.

Algorithm

1. Start with root node.
2. If root is null, return.
3. Check if there is left child, delete the sub tree with root as left child.
4. Check if there is right child, delete the sub tree with root as right child.
5. Delete the root node.

Complete code

void delete_BST(Node *root){

Read more

Find Closest Element in Binary Search Tree

Find Closest Element in Binary Search Tree

The problem of finding a closest element in a tree to a given value is another case where we can use the property of binary search tree.

Problem statement 

Given a Binary Search Tree and a value, find the closest element to the given value in BST.

Analysis

Simple approach is to go to all elements of BST and find out the difference between the given value and value of the element. Get the minimum value and add or subtract that minimum value from the given value, we would get the closest element in the BST.

Do we really need to scan all the nodes? No we don't need to.
Let's consider it case by case.
Case 1 : If the value of the node under consideration is equal to value, then our minimum difference would be zero and closest value would the value itself.

Case 2 : If the value of the node under consideration is greater than given value.
By virtue of BST, we know that nodes on the right side of the given node would be greater than this. Hence the difference between the given value and all nodes on the right side would only increase. Hence there is no element on the right side, which is closer than the node itself. Hence the right sub tree is discarded.

Case 3 : If the value of the node under consideration is less than the given value.
Again same logic applies as in case 2. Since all elements in left sub tree are less than the node, difference between given value and the nodes on left side would only increase. Hence we can safely discard the left sub tree.

Algorithm

1. Start from the root, initialize min to MAX_INT 

Read more

Deleting a Node in Binary Search Tree

Introduction

This post elaborates how we can delete any node in a binary search tree and maintain its binary search tree property.

Problem statement 

Given a number K and a binary search tree, delete the node with value K and also maintain the binary search tree property.

Analysis

First problem is to locate the the node. Once the node is located, there are three cases to be considered before we delete the node.

Case 1 :

If the given node is leaf node. Straight forward, delete the node. 

For example, tree is like given below and we need to delete 4.

It would be deletion of node 4 and setting the left child of 6 as NULL.

Case 2 :

If the node is not leaf node and there is right sub tree to it. In this we would replace the deleted node by the in-order successor of the node in BST. Free the in-order successor node.

Read more

Check if a given tree is Binary Search Tree or not

Introduction

How do we know that a given binary tree is a binary search tree?

Definition of BST:

All the nodes on the left side of a given node are smaller and all nodes on the right side are greater than the given node.

So, essentially, any tree is a binary search tree if both its left sub tree and right sub tree are binary search tree and root satisfy the binary search tree condition.

So, tree is binary search tree if

1. Left sub tree is binary search tree

2. Right sub tree is binary search tree

3. Value of root is greater than max in left sub tree and less than minimum in right sub tree

No further analysis is required for this problem.

Read more

Binary Search Tree : Level order printing

Print nodes of a tree in level order

Problem statement 

Print nodes of a tree level wise i.e. nodes at same level should be printed together.

For example, in following tree output should be 

10,6,15,4,7,13,17

Read more

Binary Search Tree to Doubly linked list conversion

Introduction

In binary search tree, every node contains two pointers, one for left child and other for right child. Similarly, in doubly linked, every node contains two pointers, one for the next node and other for the previous node.

So can we convert a  binary search tree to a doubly linked list?

Problem statement

Given a binary search tree, convert this tree to a doubly linked list. Doubly linked list should be in sorted order.

For example, for below tree

Output should be

Read more

Binary Search Tree : Build binary search tree given inorder and preorder traversal

Introduction : Binary Search Tree

Basic definition and problems related to binary search tree can be read at this post.

Today's problem statement is 
Given in-order and pre-order traversal of a binary search tree, build the binary search tree.
For example,
In-order traversal is {10, 12, 20, 30, 37, 40, 45}
Pre-order traversal is {30, 20, 10, 12, 40, 37, 45}

The resultant binary search tree should be

Read more

Acyclic Linked-List Detection Algorithm

Write a function that takes a pointer to the head of a list and determines whether the list is cyclic or acyclic. Your function should return false if the list is acyclic and true if it is cyclic. You may not modify the list in any way.

int determineTermination( node *head ) { node *fast, *slow; fast = slow = head; while( true ) { if( !fast || !fast->next ) return false; else if( fast == slow || fast->next == slow ) return true; else { slow = slow->next; fast = fast->next->next; } } }

Leave your comments below the post.
Happy coding :)

Read more

Searching & Sorting techniques using C

If we try to identify those contributions of computer science that will be long lasting,surely one of those will be the refinement of the concept called Algorithm.Ever science man designed the idea of machine which could perform basic mathematical operations,the study of what can be computed and how it can be done well was launched.....Here some example of basic uses of algorithm in coding is given.

Read more

C++ Binary Exercise with Example Code to Develop Your Algorithm Skills

Once you understand the basics of C++ programming language, it is essential for you to develop your problem solving skills using C++ program. In other words, you should know how to develop your programming logic to solve a given problem.

In this tutorial, we’ll give a simple binary problem, which you should solve by writing a C++ program.

Read more

The 2013 HTPC Build

Nodebots! The JavaScript of the future! 

A few people have asked me how to get started in this world of JavaScript and Arduino. I put together the following hack for my talk at JSConf.eu. It’s a lightup GitHub build success indicator I called Buildbrite.

The parts you will need to order before getting started are an Arduino board, a tri-color LED, an A/B to USB cable, and a wire or wires and abreadboard.  

You can also watch the video from JSConf.eu here!

Read more

Computing History at Bell Labs

In 1997, on his retirement from Bell Labs, Doug McIlroy gave a fascinating talk about the “History of Computing at Bell Labs.” That page contains audio for the talk in Real Audio format (it was1997). Almost ten years ago I transcribed the audio but never did anything with it. The transcript is below.

My favorite parts of the talk are the description of the bi-quinary decimal relay calculator and the description of a team that spent over a year tracking down a race condition bug in a missile detector (reliability was king: today you'd just stamp “cannot reproduce” and send the report back). But the whole thing contains many fantastic stories. It's well worth the read or listen. I also like his recollection of programming using cards: “It's the kind of thing you can be nostalgic about, but it wasn't actually fun.”

For more information, Bernard D. Holbrook and W. Stanley Brown's 1982 technical report “A History of Computing Research at Bell Laboratories (1937-1975)” covers the earlier history in more detail.

Corrections added August 19, 2009.

Read more

Unix Viruses

Disk-based computer viruses came of age with MS-DOS; network-based viruses came of age with Microsoft Windows. (The most stunning recent example is the widespread Storm worm which is at this very minute probably sending you pump-and-dump and greeting card spam.)

Most Linux and OS X users have a frustratingly smug attitude of “we're immune to viruses, because we use Unix.” This is obviously false: the original Internet worm ran on Unix. The simple security mechanisms in Unix-based systems do raise the virus-writing bar slightly, but a more likely explanation of the lack of viruses on Unix-based systems is their lack of current market share: Windows users are simply a much bigger and therefore more attractive target.

Especially for these smug Unix users, it should be sobering to read Tom Duff's 1987 technical report “Viral Attacks on UNIX® System Security,” which describes a simple, benign disk-based virus targeted at Unix executables. Even working under the constraints of the Unix permission bits, Duff managed to infect 466 files across 46 systems over a period of a few months, including an experimental “secure” version of Unix (to its credit, the kernel on that system did detect the virus). Duff's paper also describes a simple virus written in shell script. He cautions:

Read more