codelab

A binary search tree (BST), also known as an ordered binary tree, is a node-based data structure in which each node has no more than two child nodes. Each child must either be a leaf node or the root of another binary search tree. The left sub-tree contains only nodes with keys less than the parent node; the right sub-tree contains only nodes with keys greater than the parent node. Example: Insert 20 into the Binary Search Tree. Tree is not available. So create root node and place 20 into it.                                                    20 Insert 23 into the given Binary Search Tree. Since 23 > 20, then 23 will be inserted in the right sub-tree of 20.                                                     20                                                         \                                                          23 Insert 13 into the given Binary Search Tree.  Since 13 < 20, then 13 will be inserted in left sub-tree of 20.               

A prime number (or a prime) is a natural number greater than 1 that has no positive divisors other than 1 and itself. Remember two is the only even and also the smallest prime number. First few prime numbers are 2, 3, 5, 7, 11, 13, 17....etc. Prime numbers have many applications in computer science and mathematics. Any number greater than 1 can be factorized into prime numbers; for example 540 = 22*33*51. This fact makes primes very significant to communications. Most modern computer cryptography works by using the prime factors of large numbers. The large number that was used to encrypt a file can be publicly known and available, because the encryption works so only the prime factors of that large number can be used to decrypt it again. Though finding those factors is technically only a matter of time, it’s a matter of so much time that we say it cannot be done. A modern super-computer could chew on a 256-bit factorization problem for longer than the current age of the universe,

Heap Sort is one of the best sorting methods being in-place and with no quadratic worst-case scenarios. The algorithm can be divided into 2 basic parts: [1]  Creating a Heap of the unsorted list. [2]   Then a sorted array is created by repeatedly removing the largest/smallest element from the heap, and inserting it into the array. The heap is reconstructed after each removal. Heap is a tree-based data structure that satisfies two special properties:  ***  Heap data structure is always a Complete Binary Tree, which means all levels of the tree are fully filled. *** All nodes are either [greater than or equal to] or [less than or equal to] each of its children. If the parent nodes are greater than their children, heap is called a Max-Heap, and if the parent nodes are smaller than their child nodes, heap is called Min-Heap.

The N Queens puzzle is the problem of placing eight chess queens on an n×n chessboard so that no two queens threaten each other. Thus, a solution requires that no two queens share the same row, column, or diagonal. The number of rotationally and reflectively distinct solutions for the first few N are 1, 0, 0, 2, 10, 4, 40, 92,... Example: The graphical demonstrations for the 8 queens problem: 

Doubly-linked list is a more sophisticated form of linked list data structure. Each node contains two fields, called links that are references to the previous and to the next node in the sequence of nodes. The two node links allow traversal of the list in either direction. The previous link of the first node and the next link of the last node points to NULL. While adding or removing a node in a doubly linked list requires changing more links than the same operations on a singly linked list, the operations are simpler and potentially more efficient (for nodes other than first nodes) because there is no need to keep track of the previous node during traversal or no need to traverse the list to find the previous node, so that its link can be modified. Example: A doubly linked list whose nodes contain three fields of integer value, the link to the next node, and the link to the previous node.

A linked list is a data structure consisting of a group of nodes which together represent a sequence. Under the simplest form, each node contains one or more data fields and a reference to the next node. The last node points to a null reference to indicate the end of the list.  The entry point into a linked list is the head of the list. Head is not a separate node, but a reference to the first Node in the list. If the list is empty, then the head has the value null. Linked list allows for efficient insertion, deletion, and traversal of elements in the sequence. Example: A singly linked list whose nodes contain two fields: an integer value and a link to the next node. The last node is linked to a terminator used to signify the end of the list.

Quick sort is an efficient sorting algorithm. It is even two or three times faster than mergesort and heapsort in some particular cases. The sorting method compares n items in O(nlogn) time in average and best cases, while it is O(n^2) in worst case. Quick sort comes under divide and conquer algorithm which divides the large set of array in small by picking up a pivot element as a reference element, and do sorting. Algorithm: (1) Make a list of items that need to be sorted, let’s apply in an array. (2)  Choose a suitable element as pivot element from the array list, because complexity largely depends on choosing the pivot element. (3) Rearrange the array list so that all the elements with value less than the pivot will come before the pivot and the element with value greater will come after the pivot with in the same array, which make pivot element in the sorted position. (4) Apply recursively the third step to the sub array of the element with smaller values and separ

Merge sort is based on divide and conquer method. It takes the list to be sorted and divide it in half to create two unsorted lists. The two unsorted lists are then sorted and merged to get a sorted list. The two unsorted lists are sorted by continually calling the merge-sort algorithm; we eventually get a list of size 1 which is sorted. The two lists of size 1 are then merged. Best case : When the array is already sorted O(nlogn). Worst case : When the array is sorted in reverse order O(nlogn). Average case : O(nlogn). Space Complexity: Extra space is required, because space complexity is O(n) for arrays and O(logn) for linked lists. 

A program can show incorrect output when the input is not validated to see whether it is correct or not. The best way of avoiding such situation is that treat all input as a sequence of characters, and then perform the necessary data conversion. We can use getchar() to read all input as a string, and afterward convert the string to the correct data type. #include<stdio.h> #include<ctype.h> #include<stdlib.h> #define MAXBUFFERSIZE 80 void cleartoendofline(void);          /* ANSI function prototype */ void cleartoendofline(void) { char ch; ch = getchar(); while(ch != '\n') ch = getchar(); }

Insertion sort is a simple algorithm that sorts an array one item at a time. When people manually sort something (for example, a deck of playing cards), most use a method that is similar to insertion sort. The algorithm is efficient for small data sets. How insertion sort works:  The second element of an array is compared with the elements that appear before it (only first element in this case). If the second element is smaller than first element, second element is inserted in the position of first element. After first step, first two elements of an array are sorted. The third element of an array is compared with the elements that appears before it (first and second element). If third element is smaller than first element, it is inserted in the position of first element. If third element is larger than first element but, smaller than second element, it is inserted in the position of second element. If third element is larger than both the elements, it is kept in the positio

Bubble sort algorithm starts by comparing the first two elements of an array and swapping if necessary, i.e., if you want to sort the elements of array in ascending order and if the first element is greater than second then, you need to swap the elements but, if the first element is smaller than second, you mustn't swap the element.  Then, again second and third elements are compared and swapped if it is necessary and this process go on until last and second last element is compared and swapped. This completes the first step of bubble sort. If there are n elements to be sorted then, the process mentioned above should be repeated n-1 times to get required result. But, for better performance, in second step, last and second last elements are not compared as the element is automatically placed at last after first step.  In the third step, last and second last, second last and third last elements are not compared and so on. Graphical representation of bubble sort:

Stack is an area of memory that holds all local variables and parameters used by any function. It also remembers the order in which functions are called so that function returns occur correctly. Stack is a LIFO data structure. Stack operations are PUSH (insert operation), POP (Delete operation), and Display (stack). Each time a function is called, its local variables and parameters are “pushed onto” the stack. When the function returns, these locals and parameters are “popped”. #include <stdio.h> #define MAXSIZE 25 struct stack { int stk[MAXSIZE]; int top; }; typedef struct stack STACK; STACK s;

In Fibonacci series, each number is the sum of the two preceding numbers. For example: 0, 1, 1, 2, 3, 5, 8, ….., ∞ (infinity). The following programs return the nth number entered by user residing in the Fibonacci series. Method 1 (Using recursion): Time Complexity: T(n) = T(n-1) + T(n-2) which is exponential, i.e. this implementation does a lot of repeated work. Extra Space: O(n) if we consider the function call stack size, otherwise O(1). #include<stdio.h> int fib(int n) { if ( n <= 1 ) return n; return fib(n-1) + fib(n-2); } int main () { int n ; printf(" Enter Number to Compute nth Fibonacci Series: "); scanf("%d",&n); printf("\n\n %dth term of Fibonacci Series is %d\n",n, fib(n)); return 0; }

The Towers of Hanoi is a mathematical game or puzzle. The objective is to move the all of the discs one at a time from an arbitrary peg to another. Putting a larger disc over a smaller one must be avoided at all times and the transfer must be made in the least possible moves, which is 2^n - 1, where n is the number of disks. For example, the minimum number of moves required to move three discs are 2^3 - 1 = 7. #include <stdio.h> void towers(int, char, char, char); int main() { int num; printf("Enter the number of disks: "); scanf("%d", &num);

The following program asks user an arithmetic operator (+,-,*,/) and two operands and perform the corresponding calculation on the operands. # include <stdio.h> int main() { char o; float num1,num2; printf("Enter an operator: either + or - or * or /\n\n=> "); scanf("%c",&o); printf("\nEnter two numbers:\n"); scanf("%f%f",&num1,&num2);

A struct is a complex data type declaration that defines a physically grouped list of variables to be placed under one name in a block of memory.   #include <stdio.h> #include <string.h> struct Books  { char title[50]; char author[50]; char subject[100]; int book_id;   }; int main( )  { struct Books Book1; struct Books Book2;

Method 1: The following program generates a multiplication table for a given integer to a given range. #include <stdio.h> int main()  { int n, range, i; printf("Enter the value of n: "); scanf("%d",&n); printf("\nEnter the range: "); scanf("%d",&range); for(i=1;i<=range;++i)  { printf("%2d X %2d = %3d\n", n, i, n*i); } return 0; }

The C language provides no explicit support for strings in the language itself. The string-handling functions are implemented in libraries. The string library (string.h or strings.h) has some useful functions for working with strings, like strcpy, strcat, strcmp, strlen, strcoll, etc. We will take a look at some of these string operations.  #include <stdio.h> #include<string.h> #include<ctype.h> #include<stdlib.h> int length(char str[]); void reverse(char str[]); int palindrome(char str[]); void copy(char str1[], char str2[]); int compare(char str1[], char str2[]); void concat(char str1[], char str2[]); void search(char str1[], char str2[]); void count(char str1[]); int main() { char a[100], b[100]; int result, option;

#include <stdio.h> int main()  { int a[10][10], b[10][10], mult[10][10], r1, c1, r2, c2, i, j, k; printf("Enter Rows and Columns for First Matrix:\n"); scanf("%d%d", &r1, &c1); printf("\nEnter Rows and Columns for Second Matrix:\n"); scanf("%d%d",&r2, &c2); while (c1!=r2)  { printf("\nWrong Input: Column of First Matrix is Not Equal to Row of Second Matrix.\n\n"); printf("\nEnter Rows and Columns for First Matrix:\n"); scanf("%d%d", &r1, &c1); printf("\nEnter Rows and Columns for Second Matrix:\n"); scanf("%d%d",&r2, &c2); }

#include<stdio.h> int main()  { char line[150]; int i,v,c,ch,d,s,o; o=v=c=ch=d=s=0; printf("Enter A Sentence:\n\n\t"); gets(line); for(i=0;line[i]!='\0';++i) { if(line[i]=='a' || line[i]=='e' || line[i]=='i' || line[i]=='o' || line[i]=='u' || line[i]=='A' || line[i]=='E' || line[i]=='I' || line[i]=='O' || line[i]=='U') ++v;

This program checks each character one by one. If the character is in lowercase, then it is converted into uppercase. But if it is in uppercase then converts into lowercase. The source code is successfully compiled and run on any operating system. #include <stdio.h> #include <ctype.h> int main() { char sentence[100]; int count, ch, i; printf("Enter One or Multiple Sentence:\n\n\t"); for (i = 0; (sentence[i] = getchar()) != '\n'; i++) {         ; }

#include<stdio.h> void swap(int *num1, int *num2) { int temp;  temp = *num1; *num1 = *num2;  *num2 = temp;  } int main() { int num1, num2;

The properties of any element Aij will be diagonal element if and only if i = j. #include<stdio.h> int main(){ int a[100][100],i,j,sum=0,m,n; printf("\nEnter the row and column of matrix: \n"); scanf("%d %d",&m,&n); printf("\nEnter the elements of matrix: \n"); for(i=0;i<m;i++) for(j=0;j<n;j++) scanf("%d",&a[i][j]); printf("\nThe matrix is\n");

The following code implements linear search (Searching algorithm) which is used to find whether a given number is present in an array or not and if it is present then at what location it occurs. It is also known as sequential search. It is very simple and works as follows: we keep on comparing each element with the element to search until the desired element is found. Time required to search an element using linear search algorithm depends on the size of list. In the best case, element is present at the beginning of list and in the worst case, element is present at the end. Time complexity of linear search is O(n).  #include <stdio.h> int main() { int array[100], search, c, n; printf("\nEnter the number of elements in array: "); scanf("%d",&n); printf("\n\nEnter %d integer(s): \n", n); for (c = 0; c < n; c++) scanf("%d", &array[c]); printf("\n\nEnter the number to search: "); scanf("

#include <stdio.h> int main(void)  { int i=0, j=0, n=0, t, a[n]; printf ("\n How many numbers you want to sort: "); scanf ("%d", &n); printf ("\n"); for (i = 0; i <n; i++)   { printf ("\n (%d) Enter a number: ", (i+1)); scanf ("%d", &a[i]); } for (j=0 ; j<(n-1) ; j++)  { for (i=0 ; i<(n-1) ; i++)  {

#include <stdio.h> int main() { int n=0, i; float num[n], sum=0.0, average; printf("How many numbers you want to average: "); scanf("%d",&n); while (n<=0)  { printf("\n\nError! it should be a positive integer.\n"); printf("\n\nEnter the number again: "); scanf("%d",&n); }

Web pages are written in HTML, the web programming language that tells web browsers how to structure and present content on a web page. In other words, HTML provides the basic building blocks for the web. And for a long time, those building blocks were pretty simple and static: lines of text, links, and images. Today, we expect to be able to do things like play online chess or seamlessly scroll around a map of our neighborhood, without waiting for the entire page to reload for every chess move or every map scroll. The idea of such dynamic web pages began with the invention of the scripting language JavaScript. JavaScript support in major web browsers meant that web pages could incorporate more meaningful real-time interactions. For example, if you have filled out an online form and hit the “submit” button, the web page can use JavaScript to check your entries in real-time and alert you almost instantly if you had filled out the form incorrectly. But the dynamic web as we

The problem seems complicated but the concept behind it is very simple; display the content from the same file you are writing the source code. A predefined macro __FILE__ contains the location of the programming file, it is working on. For example: t he output of following programs display the location of their files.  #include <stdio.h> int main() { printf("%s",__FILE__); }

#include <stdio.h> int main() { int n, c, k, space = 1; printf("\nEnter number of rows: "); scanf("%d", &n); printf("\n\t"); space = n - 1; for (k = 1; k <= n; k++) { for (c = 1; c <= space; c++) printf(" "); space--;

GCD means Greatest Common Divisor. For two integers a and b, if there are any numbers d so that a/d and b/d doesn’t have any remainder, such a number is called a common divisor. Common divisors exist for any pair of integers a and b, since we know that 1 always divides any integer. We also know that common divisors cannot get too big since divisors cannot be any larger than the number they are dividing. Hence a common divisor d of a and b must have d <= a and d <= b. LCM means Least Common Multiplies. For two integer a and b, to know if there are any smallest numbers d so that d/a and d/b doesn't have a remainder. Such a number is called a Least Common Multiplier. Here is source code of the C program to calculate the GCD and LCM of two integers. It compiles and runs on any operating system. Method 1: #include <stdio.h> int main() { int a, b, x, y, t, gcd, lcm; printf("Enter Two Integers: "); scanf("%d%d", &x, &y);