Binary Tree Sort uses a Binary search tree. The various steps involved in such a sort would be – Construct a binary tree with the given data (integers) such that all numbers to the left of a particular node say ‘nd’ is less than the number contained within the node and to the right, the numbers…
A Selection sorting technique uses a general algorithm which uses an ascending or descending priority queue. The idea would be to pre-process input array X[i] into the descending or ascending priority queues by the functions dpqinsert(dpq, x) or apqinsert(apq, x) respectively. Now, the next and final step would be to select data in appropriate order from…
The popular exchange sort mechanisms are Mean sort, Quick Sort and BSort and Quick sort is the most simple one. Quick sort is most applicable exchange sorting technique for practical applications since it uses relatively less time-space resources. Lets illustrate finding Order of a Quick sort algorithm in C. Lets start with the below list…
Lets explain Bubble sort by illustrating tow specific examples involving steps where smaller numbers bubbles to first and when larger numbers bubbles to last. Number list to sort: 2 5 3 0 6 1 Case 1: Smaller numbers bubbles to first Step 1: 0 5 3 2 6 1 Step 2: 0 3 5 2 …
Efficiency Considerations The following are the efficiency considerations while planning for a sorting program / algorithm – Time required to code the program and the type of sorting technique to be selected Execution time Amount of space required by program In cases where the type of data to be sorted is known, it is easier…
Towers of Hanoi problem consists of 3 pegs A, B and C. Let n denote number of disks in peg A. The objective is to transfer these disks from A to C using B as auxiliary so that at a time only one disk is transferred and a larger one cannot reside on a smaller…
In general cases, a non-recursive program runs more efficiently than a recursive program since a recursive program requires more execution time to enter and exit from a function. Recursive programs flows directly from the definitions and are easy to implement while a corresponding non-recursive program may involve expensive use of stacks which are difficult to…
Recursion Recursion and Iteration are two different concepts of achieving a result by a number of repeated operations. Iteration involves use of for, while and do-while loops for the repeated operation until specified condition. Recursion involves a recursive function calling itself several times until specified condition. A recursive function represents the most simpler form of…
Doubly Linked lists eliminates below drawbacks of circular lists – not able to traverse backward not able to delete and node given only points to that node. In a doubly linked list, every node has three fields – left, right and info. Each node has two pointers left and right which points to the left…
Josephus Problem Josephus problem is that some soldiers are being surrounded by their enemies and there is only one horse to escape i.e. only one soldier could escape and summon help. The remedy is to arrange soldiers’ names as a circular list. Now, any number say ‘n’ is inputed (selected) where n < number of…
Circular lists eliminates same drawbacks of linear lists. In as circular list it is assumed that items are inserted at the front and the list pointer points to the currently inserted node. Now, in this currently inserted circular list items, node or item is the last node of the list (and is this the rear…
Below are the advantages of Dynamic representation of Lists over its Array implementation – No advanced knowledge of number of nodes is required No memory space is wasted by bulk allocation as in the case of a large array since memory space is allocated only when a node is created A reference to a pointer…
When Dynamic Linked Lists are represented as Queues, the first node represents front of queue given by q.front and last node represents the rear of the queue given by q.rear where q.front and q.rear are pointers. Thus Qinsert(q,x) and Qdelete(q) could be implemented as below – Qinsert(q,x){ p = getnode(); info(p) = x; next(p) =…
List is a type of dynamic data structure which rectifies certain drawbacks of Stacks and Queues. Lists generally uses the concept of pointers which points to a memory location containing data. The basic structure of a linear linked list is a as follows – Each item in a list is called NODE. Each NODE…
A Queue is a First In First Out (FIFO) which is an ordered collection of items which are deleted at the front end and inserted at the rear end. A simple queue is represented as below – Simple Sequential Queue A Queue in C may be defined as an array as…
Game Tree is one of the applications of Binary Trees. For example the one implemented for the Tic-Tac-Toe Game. X | X | X O | O | O | | The game is between two players who makes moves ‘X’ and ‘O’ on a board of 3×3 positions. The players who wins is…
Case 1: A list could be represented as a Binary Tree with all the list elements along with their information at the leaf nodes. For example, the linked list ->[A| ]->[B| ]->[C| ]-> ………[I| ] could be represented as following Binary Tree – 5 / \ 2 2 / \ / \ 1 2 1…
Huffman trees are used as message encoding and message decoding trees which is the basic construct of compression and de. The specialty of Huffman tree is that – it helps to reduce the bit codes of each symbol in the message according to their relative frequency of occurrence. the same tree constructed could be used for…
Threaded Binary Trees are those in which the NULL right pointers of all nodes are THREADED to its immediate inorder successor in the Binary Tree. Such pointers or THREADS are also called RIGHT IN threads as they are always threaded to right. Example Structure of a Threaded Binary Tree A / \ B C / \…
There are generally 3 traversal strategies for Binary Trees – INORDER, PREORDER and POSTORDER. For eg:, the inorder, preorder and postorder traversal of an expression tree gives the infix, prefix and postfix forms of the expression. Such a traversal could be used to evaluate the value of expression. Example 1 : Consider the following Binary Tree –…
A Binary Search is such a Binary Tree in which the info field of any of the nodes to the left of a particular node nd will be < that of nd and of those to the right of nd will be >= nd. The in-order traversal of such a tree will give the sorted form…
Binary Trees are one of the core data structures used in any programming language to implement complex systems. C programming language offers various binary tree operations that could be used by the developer. Binary Trees can be dynamically represented in C as shown below – struct nodetype{ int info; struct nodetype * left; struct nodetype * right;…
Here is a C program which accepts an integer and prints out sum from 1 to 1, 1 to 2, 1 to 3 …… 1 up-to that number – main(){ int n,i,s=0; printf(“\nEnter any integer>>”); scanf(“%d”,&n); for(i = 1; i
Hailstones is a sequence of numbers that could be generated from any positive number by performing a specific operation on it until it reaches 1. The fact is that any positive number will reach 1 if we perform this operation. If the number is even, we divide it by 2, otherwise we multiply the number…
Here is a C program to generate random numbers between any range of two digit numbers – #include #include main(){ int s, a, b, n, ran; srand(time(0)); // this is to set the seed to current time so we get different random numbers in each try printf(“\nEnter lower limit>>”); scanf(“%d”,&a); printf(“\nEnter upper limit>>”); scanf(“%d”,&b); printf(“\nEnter…
The ‘for’ loop is another important looping structure which could replace ‘while’ and ‘do .. while’ loops. It has a special feature that the initialization, test condition and the increment or decrements of test variable could be placed in a single line following the ‘for’ keyword as shown below – for (initialization; test condition; change…
Below is a C program to test for a prime number – main(){ float n, count = 0; i = 3; a; printf(“\nEnter any number of your choice>>”); scanf(“%f”, &n); if(n == 0 || n == 1 || n == 2) printf(“\n%d is not a prime number\n”, n); while(i > 2 & i < n){...
Here is a C program that I wrote years back to implement Russian Peasant method of an interesting multiplication technique – main(){ int a, b, sum = 0; printf(“\nEnter the two digits to be multiplied separated by space>> “); scanf(“%d %d”, &a, &b); printf(“%d “,a); printf(” %d\n”,b); do{ if(a % 2) sum += b; else…
Here is an implementation of while loop in C to find numbers whose sum of cubes of individual numbers is that number. You can go a step further and make it so that you accept value of i and n. main(){ int i = 1, a, b, c, n = 1000; printf(“\n Enter a number…
Here is a simple C program to find circumference and area of a circle from given radius – main(){ float r, pi = 3.1416, c, area; printf(“\nEnter value of radius>> “); scanf(“%f”, &r); while (r > = 0.0){ c = 2*pi*r; area = pi*r*; printf(“\nCircumference = %f”, c); printf(“\nArea = %f”, area); scanf(“%f”, &r) } }
Like do-while loop, While loop is the most commonly used looping construct to repeat a process or calculation for a set or collection of inputs or storage based on a condition. It is a looping technique when you want to execute the required process based on a condition for the entire input collection. Below is…
Here is a simple C program to find the sum of squares of first n natural numbers using do-while looping construct – main(){ int n, sum =0; printf(“\nInput any integer of your choice>>”); scanf(“%d”,&n); nsave = n; do{ sum += n*n; n–; } while(n > 0); printf(“Sum of squares upto %d = %d \n”, nsave,…
Looping constructs is an important programming language technique to repeat a process or calculation for a set or collection of inputs or storage based on a condition. Do – While is a looping technique when you want to execute the required process for at least once and then check the condition for the rest of the…
Below are simple C programs for beginners to learn if-else decision construct. Example 1: Program to check if a number is odd or even main (){ int n; printf(“Please enter any number>> “); scanf(“%d”, &n); if(n % 2 == 0) printf(“\n%d is EVEN \n”, n); else printf(“\n%d is ODD \n”, n); } Example 2: Program…
Here is a C program to check for leap year – main () { int year; printf(“Please enter any year as 4 digits>> “); scanf(“%d”, &year); if(year % 4 ==0 && year % 100 !=0 || year % 400 == 0) printf(“%d is a leap year \n”, year); else printf(“%d is not a leap year…
Decision making is an important aspect of programming language that enables the programmer to arrive at a conclusion based on certain data processing, comparisons and conditional situations. In most programming language there are inbuilt functions and language constructs that enable implicit decision making. In other situations, it offers a combination of language constructs such as comparison…
C programming language allows to define and classify data so we can use it appropriately in various parts of the program in the correct form with or without changing the original value or just copying the original value. Any data that we need to use in the program need to be stored in the memory….
C language developed at Bell lab by Dennis Ritchie on UNIX environment. UNIX was later rewritten in C. An earlier version of C is BCPL (Basic Combined Programming Language) developed by Ken Thompson. When it was later improvised by Dennis, it became C (‘C’ from BCPL) programming language. C program could be written either in…
Below is an example Recursive C program to perform Binary – int binsearch(int low, int high, in a[], X){ int mid; if(low > high){ return(-1); } mid = (low + high) / 2; return(X == a[mid] ? mid : X < a [mid] ? binsearch(low, mid-1, a[], X) : binsearch (mid+1,high,a[],X)) }
Below is an example recursive C program to return Fibonacci series for a given number – int fibonacci (int x){ if(n < 0){ printf("Invalid input"); exit(1); } else{ return ((n==1 || n==1)? n : fib(n-2) + fib(n-1)); } }
Here is a C program to find a factorial by recursive method – int factorial (int x ) { return ( n==0? 1: n*(fact(n-1))); }
Simple bubble sort in C – for (i=0; i<n-1; i++){ for(j=i+1; j<n; j++){ if(x[j] < x[i]){ temp = x[j]; x[j] = x[i]; x[i] = temp; } } }
Below is an example to represent a Tree structure in C using struct
Below is a simple C program to perform file operation – include <stdlib.h> main() { FILE * file_source char * file_name = (char*) malloc (sizeof (char)* 13); char * file_content= (char*) malloc (sizeof (char)* 100); printf(“Enter File Name>”); gets (file_name); file_source = fopen(file_name, “r+”); if(file_source == NULL) { printf(“File doesn’t exist”); } else{ while (…
Writing C programs for numerical differentiation is interesting and fun. Here is one that I wrote years back. Enjoy!
Gregory Newton Backward Interpolation Method can be used to derive difference formula when the x values are at equidistant intervals and the value to be interpolated lies towards the end of the table. Below is a detailed explanation of how to apply Gregory Newton Backward Interpolation Method –
Below is a C program to evaluate forward difference and thus print a forward difference table for n function values –
Below is an amazing solution to prove that when n=2, Lagranges interpolation formula reduces to Linear interpolation –
One of the fastest growth rates in the telecommunications industry anywhere in the world is that of mobile radio communication devices. The basic architecture of such a mobile communication network is shown below – Radio telephones or cell phones provide a switched two-way channel between two conversing parties like a conventional telephone. Telephones may…
Olden form of phone systems involved manual exchanges which involved a great task in switching and routing of calls to various subscribers that increased network traffic and longer setup times. Also, fault checking and identification was very difficult. With the introduction of electronic exchanges which used a stored program concept of switching and routing of…
It’s helpful for data communication and IT students to understand the evolution of Data communication systems. The first phase in the evolution of data communication systems was Telegraph Systems. Later, with developments in the telephone systems, it was then possible to interconnect various computer terminals for data communication. With the advancements in network computing and the…
Data Communications is the function of transferring a digital signal from one digital device to another. Data transmission and data communications mean two different things. Data communication has a much wider meaning which embraces not just electrical transmission but, any other factors involved in controlling, checking and handling the movement in a communication-based computer system….
Below is sample C program to convert a postfix string to prefix form. Also included is detailed flow chart of the program and dry run for couple different use cases.
Below is sample C program to convert a prefix string to infix form. Also included is detailed flow chart of the program and dry run for couple different use cases.
Below is an example that I prepared for preorder and postorder traversal of a Binary Tree – enjoy!
Below is the algorithm and C routine for traversing a Binary Tree in postorder.
A binary tree can be traversed in two basic ways – preorder and postorder. Explained below is the process or preorder traverse of a binary tree with an algorithm and the actual C routine.
Binary Tree is a basic data structure that is used behind the scenes of all major technologies whether it’s a Database system or operating system, search engine, Bleeding edge AI systems, Big data or cloud based architectures.
Below is the solution to test convergence of a sample Logarithmic series –