GATE 2012 CS Syllabus

GATE 2013 Comprehensive Information Page @ http://www.codeblocks.info/2012/08/gate-2013.html

GATE 2012 - SYLLABUS FOR COMPUTER SCIENCE AND INFORMATION TECHNOLOGY (CS)

Engineering Mathematics

Mathematical Logic:
Propositional Logic; First Order Logic.


Probability:
Conditional Probability; Mean, Median, Mode and Standard Deviation; Random Variables; Distributions; uniform, normal, exponential, Poisson, Binomial.


Set Theory & Algebra:
Sets; Relations; Functions; Groups; Partial Orders; Lattice; Boolean Algebra.


Combinatorics:
Permutations; Combinations; Counting; Summation; generating functions; recurrence relations; asymptotics.


Graph Theory:
Connectivity; spanning trees; Cut vertices & edges; covering; matching; independent sets; Colouring; Planarity; Isomorphism.


Linear Algebra:
Algebra of matrices, determinants, systems of linear equations, Eigen values and Eigen vectors.


Numerical Methods:
LU decomposition for systems of linear equations; numerical solutions of non-linear algebraic equations by Secant, Bisection and Newton-Raphson Methods; Numerical integration by trapezoidal and Simpson's rules.


Calculus:
Limit, Continuity & differentiability, Mean value Theorems, Theorems of integral calculus, evaluation of definite & improper integrals, Partial derivatives, Total derivatives, maxima & minima.

Computer Science and Information Technology

Digital Logic:
Logic functions, Minimization, Design and synthesis of combinational and sequential circuits; Number representation and computer arithmetic (fixed and floating point).


Computer Organization and Architecture:
Machine instructions and addressing modes, ALU and data-path, CPU control design, Memory interface, I/O interface (Interrupt and DMA mode), Instruction pipelining, Cache and main memory, Secondary storage.


Programming and Data Structures:
Programming in C; Functions, Recursion, Parameter passing, Scope, Binding; Abstract data types, Arrays, Stacks, Queues, Linked Lists, Trees, Binary search trees, Binary heaps.


Algorithms:
Analysis, Asymptotic notation, Notions of space and time complexity, Worst and average case analysis; Design: Greedy approach, Dynamic programming, Divide-and-conquer; Tree and graph traversals, Connected components, Spanning trees, Shortest paths; Hashing, Sorting, Searching. Asymptotic analysis (best, worst, average cases) of time and space, upper and lower bounds, Basic concepts of complexity classes  P, NP, NP-hard, NP-complete.


Theory of Computation:
Regular languages and finite automata, Context free languages and Push-down automata, Recursively enumerable sets and Turing machines, Undecidability.


Compiler Design:
Lexical analysis, Parsing, Syntax directed translation, Runtime environments, Intermediate and target code generation, Basics of code optimization.


Operating System:
Processes, Threads, Inter-process communication, Concurrency, Synchronization, Deadlock, CPU scheduling, Memory management and virtual memory, File systems, I/O systems, Protection and security.


Databases:
ER-model, Relational model (relational algebra, tuple calculus), Database design (integrity constraints, normal forms), Query languages (SQL), File structures (sequential files, indexing, B and B+ trees), Transactions and concurrency control.


Information Systems and Software Engineering:
information gathering, requirement and feasibility analysis, data flow diagrams, process specifications, input/output design, process life cycle, planning and managing the project, design, coding, testing, implementation, maintenance.


Computer Networks:
ISO/OSI stack, LAN technologies (Ethernet, Token ring), Flow and error control techniques, Routing algorithms, Congestion control, TCP/UDP and sockets, IP(v4), Application layer protocols (icmp, dns, smtp, pop, ftp, http); Basic concepts of hubs, switches, gateways, and routers. Network security  basic concepts of public key and private key cryptography, digital signature, firewalls.


Web technologies:
HTML, XML, basic concepts of client-server computing.


Download the syllabus as a single PDF file or separate files for Maths & CS Subjects.


GATE 2012 information page @ Indian Institute of Science.
Written by Irshad Pananilath

GATE - 2011 - Computer Science - Previous Question Paper

GATE 2013 Comprehensive Information Page @ http://www.codeblocks.info/2012/08/gate-2013.html

Download CS2011.pdf Written by Irshad Pananilath

GATE - 2010 - Computer Science - Previous Question Paper

GATE 2013 Comprehensive Information Page @ http://www.codeblocks.info/2012/08/gate-2013.html

Download CS2010.pdf Written by Irshad Pananilath

GATE - 2009 - Computer Science - Previous Question Paper

GATE 2013 Comprehensive Information Page @ http://www.codeblocks.info/2012/08/gate-2013.html

Download CS2009.pdf Written by Irshad Pananilath

GATE - 2008 - Computer Science - Previous Question Paper

GATE 2013 Comprehensive Information Page @ http://www.codeblocks.info/2012/08/gate-2013.html

Download CS2008.pdf Written by Irshad Pananilath

GATE - 2007 - Computer Science - Previous Question Paper

GATE 2013 Comprehensive Information Page @ http://www.codeblocks.info/2012/08/gate-2013.html

Download CS2007.pdf Written by Irshad Pananilath

GATE - 2006 - Computer Science - Previous Question Paper

GATE 2013 Comprehensive Information Page @ http://www.codeblocks.info/2012/08/gate-2013.html

Download CS2006.pdf Written by Irshad Pananilath

GATE - 2005 - Computer Science - Previous Question Paper

GATE 2013 Comprehensive Information Page @ http://www.codeblocks.info/2012/08/gate-2013.html

Download CS2005.pdf Written by Munia Balayil

GATE - 2004 - Computer Science - Previous Question Paper

GATE 2013 Comprehensive Information Page @ http://www.codeblocks.info/2012/08/gate-2013.html

Download CS2004.pdf Written by Munia Balayil

GATE - 2003 - Computer Science - Previous Question Paper

GATE 2013 Comprehensive Information Page @ http://www.codeblocks.info/2012/08/gate-2013.html

Download CS2003.pdf Written by Munia Balayil

GATE - 2002 - Computer Science - Previous Question Paper

GATE 2013 Comprehensive Information Page @ http://www.codeblocks.info/2012/08/gate-2013.html

Download CS2002.pdf Written by Munia Balayil

GATE - 2001 - Computer Science - Previous Question Paper

GATE 2013 Comprehensive Information Page @ http://www.codeblocks.info/2012/08/gate-2013.html

Download CS2001.pdf Written by Munia Balayil

GATE - 2000 - Computer Science - Previous Question Paper

GATE 2013 Comprehensive Information Page @ http://www.codeblocks.info/2012/08/gate-2013.html

Download CS2000.pdf Written by Munia Balayil

GATE - 1999 - Computer Science - Previous Question Paper

GATE 2013 Comprehensive Information Page @ http://www.codeblocks.info/2012/08/gate-2013.html

Download CS1999.pdf Written by Munia Balayil

GATE - 1998 - Computer Science - Previous Question Paper

GATE 2013 Comprehensive Information Page @ http://www.codeblocks.info/2012/08/gate-2013.html

Download CS1998.pdf Written by Munia Balayil

GATE - 1997 - Computer Science - Previous Question Paper

GATE 2013 Comprehensive Information Page @ http://www.codeblocks.info/2012/08/gate-2013.html

Download CS1997.pdf Written by Munia Balayil

GATE - 1996 - Computer Science - Previous Question Paper

GATE 2013 Comprehensive Information Page @ http://www.codeblocks.info/2012/08/gate-2013.html

Download CS1996.pdf Written by Munia Balayil

GATE - 1995 - Computer Science - Previous Question Paper

GATE 2013 Comprehensive Information Page @ http://www.codeblocks.info/2012/08/gate-2013.html

Download CS1995.pdf Written by Munia Balayil

GATE - 1994 - Computer Science - Previous Question Paper

GATE 2013 Comprehensive Information Page @ http://www.codeblocks.info/2012/08/gate-2013.html

Download CS1994.pdf Written by Munia Balayil

GATE - 1993 - Computer Science - Previous Question Paper

GATE 2013 Comprehensive Information Page @ http://www.codeblocks.info/2012/08/gate-2013.html

Download CS1993.pdf Written by Munia Balayil

GATE - 1992 - Computer Science - Previous Question Paper

GATE 2013 Comprehensive Information Page @ http://www.codeblocks.info/2012/08/gate-2013.html

Download CS1992.pdf Written by Munia Balayil

GATE - 1991 - Computer Science - Previous Question Paper

GATE 2013 Comprehensive Information Page @ http://www.codeblocks.info/2012/08/gate-2013.html

Download CS1991.pdf Written by Munia Balayil

Function to count the number of terminal(leaf) nodes in a binary tree.

The function "terminal_count()" counts the number of leaf nodes of a binary tree.

int terminal_count(struct node *t)
{
  static int count = 0;
  if((t -> Llink == NULL) && (t -> Rlink == NULL))
    return 1;
  else
    count = count + terminal_count(t -> Llink) + terminal_count(t -> Rlink);
  return count;
}

Written by Munia Balayil

Height of a Binary Tree

Function to find the height of a binary tree

int height(struct node *t)
{
  if(t == NULL)
    return 0;
  int left = height(t -> Llink);
  int right = height(t -> Rlink);
  if(left > right)
    return left + 1;
  else 
    return right + 1; 
  }
}

Written by Munia Balayil

Reverse a Circular Doubly Linked List - Recursive Solution

Function to reverse a Circular Doubly Linked List

A doubly linked list is a linked data structure that consists of a set of sequentially linked records called nodes. Each node contains two fields, called links, that are references to the previous and to the next node in the sequence of nodes.

The structure of a node in a Doubly linked list is as given below.

struct node
{
  struct node *Llink;
  int data;
  struct node *Rlink;
}

If we create the Doubly linked list in a circular fashion, it forms a Circular doubly linked list.

The function "reverse" reverses a circular doubly linked list with the head node given.

void swap(struct node *p,struct node *q)
{
  struct node *r;
  r = p;
  p = q;
  q = r;
}

void reverse(struct node *head)
{
  struct node *t = head -> Rlink;
  while(t != head)
  {
    swap(t -> Llink, t ->Rlink);
    t = t -> Llink;
  }
  swap(head -> Llink, head -> Rlink)
}

Written by Munia Balayil

Reverse a Linked List - Recursive Solution

Function to reverse a linked list - recursive solution

void reverse(struct node *pred, struct node *curr)
{
  if(curr)
  {
    reverse(curr, curr -> link);
    curr -> link = pred;
  }
  else
    first = pred;
}

void main()
{
  reverse(NULL, first);
}

Written by Munia Balayil

Reverse a Linked List - Iterative Solution

Function to reverse a linked list - iterative solution

void reverse(struct node *first)
{
  // p is used to traverse the linked list
  struct node *p = first;
  // q points to the start of the reversed list
  struct node *q = NULL;
  // r is a temporary variable used in this process
  struct node *r;

  while(p)
  {
    r = q;
    q = p;
    p = p -> link;
    q -> link = r;
  }
  first = q;
}

Written by Munia Balayil

Count the Number of Nodes in a Linked List - Recursive Solution

Function to count the number of nodes in a linked list - recursive solution

int count(struct node *p)
// p is a pointer to the first node of the list.
{
  if(p)
    return 1 + count(p->link);
  else
    return 0;
}

Written by Munia Balayil

Function to count the number of nodes in a linked list - iterative solution

int count(struct node *first)
// first is a pointer to the first node
{
  struct node *p = first;
  int count = 0;
  while(p)
  {
    ++count;
    p = p->link;
  }
  // Final value of count gives the number of nodes
  // in the linked list.
  return count;
}

Written by Munia Balayil

Heap Sort in C - Iterative Algorithm

"Heapsort is a comparison-based sorting algorithm to create a sorted array (or list), and is part of the selection sort family. Although somewhat slower in practice on most machines than a well-implemented quicksort, it has the advantage of a more favorable worst-case O(n log n) runtime. Heapsort is an in-place algorithm, but is not a stable sort." - Wikipedia

#include<stdio.h>
#define maxheapsize 50
#define LEFT(i) 2*i
#define RIGHT(i) 2*i+1

MAX_HEAPIFY(int *a, int i, int size)
{
  // Largest of a[i], a[LEFT(i)] and a[RIGHT(i)]
  // is determined and the index is stored in "largest".
  int l, r, largest, temp;
  l = LEFT(i);
  r = RIGHT(i);
  if ((l <= size)&&(a[l] > a[i]))
    largest = l; 
  else largest = i;
  if((r <= size)&&(a[r] > a[largest]))
    largest = r;
  
  // If largest != i, swap a[i] and a[largest]
  // and heapify the subtree rooted at largest
  if(largest != i)
  {
    temp = a[i];
    a[i] = a[largest];
    a[largest] = temp;

    MAX_HEAPIFY(a, largest, size);
  }
}

BUILD_MAX_HEAP(int *a, int size)
{
  int i;

  // 2nd half of the array are leaf nodes, so each is a
  // 1-element heap to begin with.
  for(i = size/2; i > 0; i--)
    MAX_HEAPIFY(a, i, size);
}

HEAPSORT(int *a, int size)
{
  int sortedarray[maxheapsize], actualsize, root;
  int i, s = 0, j, temp;
  actualsize = size;
  
  // Build the heap tree
  BUILD_MAX_HEAP(a, size); 
  
  for(i = size; i > 0; i--)
  { 
    // Save the root to another array
    sortedarray[++s] = a[1];
    root = a[1];

    // exchange a[1](root) and a[i]
    temp = a[1];
    a[1] = a[i];
    a[i] = temp;
    
    size--;
    
    // MAX_HEAPIFY lets the value of a[i] "float down" in
    // the max-heap so that the subtree rooted at index i
    // obeys the max-heap property
    MAX_HEAPIFY(a, 1, size);

    printf("\nHeap tree after removing the largest element %d\n", root);
    for(j = 1; j<=size; j++)
      printf("%d ", a[j]);
    if(size == 0)
      printf("NULL\n");
  }

  // Print the sorted array
  printf("\nSorted array\n");
  for(i = actualsize; i > 0; i--)
    printf("%d ", sortedarray[i]);
}

int main()
{ 
  int a[maxheapsize], n, i;
  printf("\nEnter the size of the array (< 50):");
  scanf("%d", &n);
  printf("\nEnter the elements of the array\n");
  for(i = 1; i <= n; i++)
    scanf("%d", &a[i]);

  HEAPSORT(a, n);

  return 0;
}

Written by Munia Balayil

GATE 2010 C Programming Question

GATE 2013 Comprehensive Information Page @ http://www.codeblocks.info/2012/08/gate-2013.html

What is the value printed by the following C program?

#include <stdio.h>

int f(int *a, int n)
{
  if(n <= 0) return 0;
  else if(*a % 2 == 0) return *a + f(a + 1, n - 1);
  else return *a - f(a + 1, n - 1);
}

int main()
{
  int a[] = {12, 7, 13, 4, 11, 6};
  printf("%d", f(a, 6));
  return 0;
}

(A) -9
(B) 5
(C) 15
(D) 19

Answer
------
(C) 15

Explanation
-----------
f(12,....6, 6) = 12 + f(7,....6, 5)
f(7,....6, 5) = 7 - f(13,....6, 4)
f(13,....6, 4) = 13 - f(4,....6, 3)
f(4,....6, 3) = 4 + f(11,....6, 2)
f(11,....6, 2) = 11 - f(6, 1)
f(6, 1) = 6 + f(NULL, 0)
f(NULL, 0) = 0

Hence, 12 + (7 - (13 - (4 + (11 - (6 + (0)))))) = 15
Written by Munia Balayil

GATE 2011 C Progamming Question

GATE 2013 Comprehensive Information Page @ http://www.codeblocks.info/2012/08/gate-2013.html

Consider the following recursive function that takes two arguments

unsigned int foo(unsigned int n, unsigned int r)  {
  if(n > 0) return ((n % r) + foo(n / r, r));
  else return 0;
}

What is the return value of the function "foo" when it is called as foo(345, 10)?

(A) 345
(B) 12
(C) 5
(D) 3

Answer: (B) 12

5 + 4 + 3 + 0 = 12

What is the return value of the function "foo" when it is called as foo(513, 2)?

(A) 9
(B) 8
(C) 5
(D) 2

Answer: (D) 2

1 + 1 = 2

Written by Munia Balayil

GATE 2011 C Programming Question

GATE 2013 Comprehensive Information Page @ http://www.codeblocks.info/2012/08/gate-2013.html

What does the following fragment of C program print?

  char c[] = "GATE2011";
  char *p = c;
  printf("%s", p + p[3] - p[1]);

(A) GATE2011
(B) E2011
(C) 2011
(D) 011

Answer: (C) 2011

Explanation:
p[3] = A (Ascii = 65)
p[1] = E (Ascii = 69)
p[3] - p[1] = 4
p + p[3] - p[1] = p + 4


printf starts printing from the p + 4 till the end giving 2011

Written by Munia Balayil

Interview Question - IF condition to print "Hello World" in C

What should be the so that the following code snippet prints ”Hello World”?

if( <condition> )
  printf ("Hello");
else
  printf("World");

Solution 1 - Using fork() system call

#include <stdio.h>

int main(void)
{
  if(fork())
    printf ("Hello ");
  else
    printf("World");

  return 0;
}

Solution 2 - Using return value of printf() function

#include <stdio.h>

int main(void)
{
  if(printf("Hello ") == 1)
    printf ("Hello");
  else
    printf("World");

  return 0;
}

Written by Munia Balayil

5+3+2 = 151022, 9+2+4 = 183652, 8+6+3 = 482466, 5+4+5 = 202541, 7+2+5 = ?

CAT 2010 Question:
5+3+2 = 151022
9+2+4 = 183652
8+6+3 = 482466
5+4+5 = 202541 then 7+2+5 = ?


Ans:
5+3+2 = 15 10 22 [5*3=15, 5*2=10, 15+10-3=22]
9+2+4 = 18 36 52 [9*2=18, 9*4=36, 18+36-2=52]
8+6+3 = 48 24 66 [8*6=48, 8*3=24, 48+24-6=66]
5+4+5 = 20 25 41 [5*4=20, 5*5=25, 20+25-4=41]


then 7+2+5 = 143547 [7*2=14, 7*5=35, 14+35-2=47]

Written by Munia Balayil

Count the Number of Bits Set in an Integer [Shift Operator]

Shift operators shift the bits in an integer variable by a specified number of positions. The << operator shifts bits to the left, and the >> operator shifts bits to the right. The syntax for these binary operators is x << n and x >> n Each operator shifts the bits in x by n positions in the specified direction. For a right shift, zeros are placed in the n high-order bits of the variable; for a left shift, zeros are placed in the n low-order bits of the variable.

Here are a few examples:

Binary 00001000 (decimal 8) right-shifted by 2 gives 00000010 (decimal 2).
Binary 00001000 (decimal 8) left-shifted by 3 gives 01000000 (decimal 64).

One of the application of shift operation is to count the number of bits set in an unsigned integer.
For example: f(0) = 0, f(1) = 1, f(2) = 1, f(3) = 2.

More information @ Wikipedia

Option 1: In a while loop, increment a counter if the last bit in the unsigned integer is 1 all the while right shifting the integer in each iteration of the while loop.

// C program to count the number of bits set in an integer

#include<stdio.h>

int main()
{
  unsigned int i, b[32] = {0};
  int j = 31, count = 0;
  printf("\nEnter the unsigned integer:");
  scanf("%d", &i);

  while(i != 0)
  {
    // Bitwise AND operation b/w i & 0x00000001 is 1
    // if the last bit of i is 1 and 0 if the last
    // last bit is 0
    b[j] = i & 0x00000001; 
    // Increment count whenever the bit is 1    
    if(b[j] == 1)
      count++;
    j--;
    // Right shifting i by 1 to get the next bit
    i = i >> 1;
  }

  printf("\nThe number of bits set in %d is %d", i, count);

  // The array b gives the binary representation of i
  printf("\nThe binary representation of %d is ", i);
  for(i = j + 1; j < 32; j++)
    printf("%d", b[j]); 

  return 0;
}

Brian Kernighan's method: Published in 1988, the C Programming Language 2nd Ed. (by Brian W. Kernighan and Dennis M. Ritchie) mentions this in exercise 2-9. On April 19, 2006 Don Knuth pointed out to him that this method "was first published by Peter Wegner in CACM 3 (1960), 322. (Also discovered independently by Derrick Lehmer and published in 1964 in a book edited by Beckenbach.)".

long count_bits(long n) {     
  unsigned int c; // c accumulates the total bits set in v
  for (c = 0; n; c++) 
    n &= n - 1; // clear the least significant bit set
  return c;
}

Use built-in functions in compilers: GCC has the following built-in function to count the number of bits. The compiler can generate a single POPCNT instruction in the best case or generate a call to a function to count the number of bits in the worst case.

int __builtin_popcount (unsigned int x);

SWAR Algorithm: This uses a divide & conquer algorithm where the problem of summing the number of bits set in a 32 bit unsigned integer is divided into two problems of summing the number of bits set in a 16 bit integer. This strategy is applied recursively resulting in log₂(32) = 5 steps. - From Hacker's Delight, p. 66, Figure 5-2

int pop(unsigned x)
{
    x = x - ((x >> 1) & 0x55555555);
    x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
    x = (x + (x >> 4)) & 0x0F0F0F0F;
    x = x + (x >> 8);
    x = x + (x >> 16);
    return x & 0x0000003F;
}

These are some of the ways to tackle this problem.

References:

• Bit Twiddling Hacks
• Hamming Weight
• Fast Bit Counting Routines
• Population Count (Ones count)

Written by Munia Balayil

Basic Stack Operations in C

Basic stack operations in C

"A stack is a basic computer science data structure and can be defined in an abstract, implementation-free manner, or it can be generally defined as a linear list of items in which all additions and deletion are restricted to one end that is Top." - Wikipedia

	/**
	* A Stack is a last in, first out (LIFO) abstract data type and data
	* structure.It is characterized by three fundamental operations: push,
	* pop and stack top.
	* PUSH : The push operation adds a new item to the top of the stack, or
	* initializes the stack if it is empty, but if the stack is full and
	* does not contain more space to accept the given item it is considered
	* as an Overflow state (It means that the stack is overloaded or no more
	* space for new item).
	* POP : The pop operation removes an item from the top of the stack,
	* but if the stack is empty then it goes into underflow state (It means
	* no items are present in the stack to be removed).
	* STACK TOP : The stack top operation gets the data from the top-most
	* position and returns it to the user without deleting it. The same
	* underflow state can also occur in stack top operation if stack is empty.
	**/
	#include<stdio.h>
	#define MAX 50
	int main()
	{
	int stack[MAX], top = -1, e;
	int choice;
	void PUSH(int *, int, int *);
	void POP(int *, int *);
	void DISPLAY_TOP(int *, int *);
	while(1) {
	printf("\nMenu\n1.PUSH\n2.POP\n3.DISPLAY STACK TOP\n4.EXIT\n");
	printf("Type 1 to Push, 2 to Pop, 3 to display and 4 to Exit : \n");
	scanf("%d", &choice);
	switch(choice) {
	case 1:
	printf("Enter element to be pushed : \n");
	scanf("%d", &e);
	PUSH(stack, e, &top);
	break;
	case 2:
	POP(stack, &top);
	break;
	case 3:
	DISPLAY_TOP(stack, &top);
	break;
	case 4:
	exit(0);
	default:
	printf("Invalid entry!!\n");
	}
	}
	return 0;
	}
	void PUSH(int *stack, int item, int *top)
	{
	if((*top) == MAX - 1) {
	printf("Stack Overflow!\n");
	return;
	} else {
	stack[++(*top)] = item;
	printf("%d inserted\n", item);
	}
	}
	void POP(int *stack, int *top)
	{
	int item;
	if((*top) == -1) {
	printf("Stack underflow\n");
	} else {
	item = stack[(*top)];
	printf("Popped item : %d\n", item);
	(*top)--;
	}
	}
	void DISPLAY_TOP(int *stack, int *top)
	{
	int i;
	if(*top == -1)
	printf("Stack underflow\n");
	else {
	printf("The stack contents are :\n");
	for(i = 0; i <= (*top); i++)
	printf("%d ",stack[i]);
	printf("\nThe top of the stack : %d\n", stack[(*top)]);
	printf("\n");
	}
	}

view raw stack.c hosted with ❤ by GitHub

Written by Munia Balayil

Program to delete an element from an array in C

To delete an element from an array (in C)

	/**
	* Program to delete an element from an array
	**/
	#include<stdio.h>
	#include<stdlib.h>
	int main(void)
	{
	int *array, size;
	int e, i, pos;
	printf("\nEnter the size of the array : ");
	scanf("%d", &size);
	array = malloc(size * sizeof(int));
	printf("\nEnter the elements of the array : ");
	for(i = 0; i < size; i++)
	scanf("%d",&array[i]);
	printf("\nEnter the element to be deleted : ");
	scanf("%d", &e);
	printf("\n\nOriginal array size : %d", size);
	printf("\nOriginal array :\n");
	for(i = 0; i < size; i++)
	printf("%d ",array[i]);
	/* Find out position of 'e' in the array */
	for(pos = 0; pos < size; pos++)
	if(array[pos] == e)
	break;
	/* Shift the array elements backwards from 'pos' */
	for(i = pos; i < (size - 1); i++)
	array[i] = array[i + 1];
	array = realloc(array, (size - 1) * sizeof(int));
	/* Print updated array */
	printf("\n\nThe updated array size : %d", (size - 1));
	printf("\nThe updated array :\n");
	for(i = 0; i < (size - 1); i++)
	printf("%d ", array[i]);
	return 0;
	}

view raw del_array_element.c hosted with ❤ by GitHub

Written by Munia Balayil

Check the occurrence of a pattern in a string/text

	/**
	* Program to check the occurrences of a pattern in a text/string
	* This program checks whether the pattern occur in the string
	* or not, if yes at what positions and also print the text/string
	* highlighting the occurrences
	**/
	#include <stdio.h>
	#include<string.h>
	void check_substring(char *, char *);
	int main()
	{
	char str[500], substr[50];
	printf("\nEnter any string(Max length = 500 char):");
	fgets(str, 500, stdin);
	printf("\nEnter the pattern to be checked:");
	fgets(substr, 50, stdin);
	printf("\nstring = %s", str);
	printf("substring to be checked = %s", substr);
	check_substring(str, substr);
	return 0;
	}
	void check_substring(char *s, char *subs)
	{
	int i, j, k, no_of_occurence = 0;
	int l1, l2, f, pos;
	int position[100]; /* Keeps all positions where the
	substring occurs */
	l1 = strlen(s);
	printf("\n\nlength of string = %d", l1);
	l2 = strlen(subs);
	printf("\nlength of substring pattern being checked = %d", l2);
	k = 0;
	/* Traversing through the string */
	for(i = 0; i < l1; i++) {
	f = i;
	pos = i; /* Note the starting position */
	for(j = 0; j < l2; j++) {
	if(s[i] == subs[j])
	i++;
	else {
	i = f + 1;
	break;
	}
	}
	i--;
	/* On finding an occurrence */
	if(j >= l2) {
	/* Place start position in the position array */
	position[k++] = pos;
	no_of_occurence++;
	}
	}
	/* If the pattern occurs in the string/text */
	if(no_of_occurence > 0) {
	printf("\n\nThe substring occurs %d times at", no_of_occurence);
	/* Print all positions */
	for(i = 0; i < k; i++)
	printf("\nposition %d", position[i]);
	/* The string/text is printed with all occurrences enclosed
	between ^ and ^ */
	printf("\n\nThe text highlighting the occurrences of the substring\n ");
	k = 0;
	for(j = 0; j < l1; j++) {
	if(j == position[k])
	printf("^");
	printf("%c", s[j]);
	if(j == position[k] + l2 - 1) {
	printf("^");
	k++;
	}
	}
	}
	/* If the pattern does not occur in the string/text */
	else
	printf("\n\nThe substring does not occur in the string\n");
	}

view raw substring.c hosted with ❤ by GitHub

Written by Munia Balayil

Check if a String is Palindrome in C

"A palindrome is a word, phrase, number, or other sequence of units that may be read the same way in either direction, with general allowances for adjustments to punctuation and word dividers." - Wikipedia

This is a C program to check if a given string is a palindrome or not.

	/**
	* A palindrome is a word, phrase, number or other sequence
	* of units that can be read the same way in either direction
	**/
	#include<stdio.h>
	#include<stdlib.h>
	#include<string.h>
	int main(void)
	{
	int i, j, l;
	char str1[20], str2[20];
	printf("Enter any word:");
	scanf("%s", str1);
	/* Find the length of the string */
	l = strlen(str1);
	j = 0;
	/* Store the reversed string in another string str2 */
	for(i = l - 1; i >= 0; i-- )
	str2[j++] = str1[i];
	str2[j] = '\0';
	/* Compare str1 and str2 */
	/* strcmp returns 0 when the strings are equal, */
	/* a negative integer when s1 is less than s2, */
	/* or a positive integer if s1 is greater than s2, */
	/* according to the lexicographical order. */
	if(strcmp(str1, str2) == 0)
	printf("The word is a palindrome\n");
	else
	printf("The word is not a palindrome\n");
	return 0;
	}

view raw palindrome.c hosted with ❤ by GitHub

Written by Munia Balayil

Factorial of a number in C - Iterative algorithm

	/**
	* To find the factorial of a number
	**/
	#include<stdio.h>
	#include<stdlib.h>
	int main(void)
	{
	int n, i, f;
	printf("Enter any number:");
	scanf("%d", &n);
	if(n < 0) {
	printf("\nFactorial does not exist for negative numbers\n");
	exit(0);
	}
	for(f = 1, i = n; i > 0; i--)
	f = f * i;
	printf("\nFactorial of %d is %d\n", n, f);
	return 0;
	}

view raw factorial.c hosted with ❤ by GitHub

Written by Munia Balayil

Check if a number is prime or not

	/**
	* To check whether a number is prime or not
	**/
	#include<stdio.h>
	#include<stdlib.h>
	int main(void)
	{
	int n, i, p = 1;
	printf("Enter any number:");
	scanf("%d", &n);
	/* 0 and 1 are neither a prime nor a composite number */
	if((n == 0) || (n == 1)) {
	printf("The number is neither prime nor composite\n");
	exit(0);
	}
	/* 2 is a prime number */
	if(n == 2) {
	printf("The number is prime\n");
	exit(0);
	}
	/* Check for all numbers other than 0, 1 and 2 */
	for(i = 2; i < n/2; i++)
	if(n % i == 0) {
	printf("Number is a composite number\n");
	p = 0;
	}
	if(p == 1)
	printf("The number is prime\n");
	return 0;
	}

view raw check_prime.c hosted with ❤ by GitHub

Written by Munia Balayil

Swapping without using temporary variable in C - XOR

	/**
	* Swapping without using a temporary variable in C
	* (XOR)
	**/
	#include<stdio.h>
	int main(void)
	{
	int a = 5; /* a = 0101 */
	int b = 10; /* b = 1010 */
	printf("Initially, a = %d and b = %d\n", a, b);
	a = a ^ b; /* a = 0101 XOR 1010 = 1111 */
	b = a ^ b; /* b = 1111 XOR 1010 = 0101 */
	a = a ^ b; /* a = 1111 XOR 0101 = 1010 */
	printf("After swapping, a = %d and b = %d\n", a, b);
	return 0;
	}

view raw swap_xor.c hosted with ❤ by GitHub

Written by Munia Balayil

Swapping without using temporary variable in C - Multiplication & Division

	/**
	* Swapping without using a temporary variable in C
	* (Multiplication & Division)
	**/
	#include<stdio.h>
	int main(void)
	{
	int a = 5, b = 10;
	printf("Initially, a = %d and b = %d\n", a, b);
	a = a * b; /* a = 5 * 10 = 50 */
	b = a / b; /* b = 50 / 10 = 5 */
	a = a / b; /* a = 50 / 5 = 10 */
	printf("After swapping, a = %d and b = %d\n", a, b);
	return 0;
	}

view raw swap_mul_div.c hosted with ❤ by GitHub

Written by Munia Balayil

Binary Search in C

"In computer science, a binary search or half-interval search algorithm finds the position of a specified value (the input "key") within a sorted array.[1][2] In each step, the algorithm compares the input key value with the key value of the middle element of the array. If the keys match, then a matching element has been found so its index, or position, is returned. Otherwise, if the sought key is less than the middle element's key, then the algorithm repeats its action on the sub-array to the left of the middle element or, if the input key is greater, on the sub-array to the right. If the remaining array to be searched is reduced to zero, then the key cannot be found in the array and a special "Not found" indication is returned." - Wikipedia

	/** Binary Search locates the position of an item in a sorted list.
	*
	* Divide : It works by dividing the list into two halves and
	* comparing the input value to be searched with the
	* middle element of the list.
	*
	* Conquer : If the input value is equal to the mid value, search
	* is successful. If greater, call binary search only
	* on the greater sub-array of the sorted list and if
	* lesser, call binary search on the lesser sub-array.
	* Continue this until you find the input value or you
	* reach a scenario where no match is found even after
	* the sub-array reduces to a size of 1.
	**/
	#include<stdio.h>
	int main(void)
	{
	int list[20], n, i, search_num, result;
	printf("Enter the size of the array:");
	scanf("%d", &n);
	printf("Enter the elements in the list in ascending order\n");
	for(i = 0; i < n; i++)
	scanf("%d", &list[i]);
	printf("Enter element to be searched:");
	scanf("%d", &search_num);
	result = binary_search(list, n, search_num);
	// binary_search returns -1 if search_num not found
	if(result == -1) {
	printf("No such element in the list.\n");
	printf("Search unsuccessful :-(\n");
	}
	// binary_search returns the position of the search_num
	// if element found in the list
	else {
	printf("Element found at location %d", result);
	printf("of the list(starting from zero)\n");
	}
	return 0;
	}
	int binary_search(int arr[], int size, int search_val)
	{
	int low, high, mid;
	low = 0;
	high = size - 1;
	while(low <= high) {
	mid = (low + high)/2;
	// if search_val = middle element return mid
	if(search_val == arr[mid])
	return mid;
	// if search_val < middle element search lower/lesser
	// half of the sorted list
	else if(search_val < arr[mid])
	high = mid - 1;
	// if search_val > middle element search higher/greater
	// half of the sorted list
	else if(search_val > arr[mid])
	low = mid + 1;
	}
	return -1;
	}

view raw binary_search.c hosted with ❤ by GitHub

Written by Munia Balayil

Swapping without using temporary variable in C - Addition & Subtraction

	/**
	* Swapping without using a temporary variable in C
	* (Addition & Subtraction)
	**/
	#include<stdio.h>
	int main(void)
	{
	int a = 5, b = 10;
	printf("Initially, a = %d and b = %d\n", a, b);
	a = a + b;
	b = a - b;
	a = a - b;
	printf("After swapping, a = %d and b = %d\n", a, b);
	return 0;
	}

view raw swap_add_mul.c hosted with ❤ by GitHub

Written by Munia Balayil

Quick Sort Using Recursion in C

"Quicksort is a sorting algorithm developed by Tony Hoare that, on average, makes O(n log n) comparisons to sort n items. In the worst case, it makes O(n2) comparisons, though this behavior is rare. Quicksort is often faster in practice than other O(n log n) algorithms.[1] Additionally, quicksort's sequential and localized memory references work well with a cache. Quicksort can be implemented with an in-place partitioning algorithm, so the entire sort can be done with only O(log n) additional space." - Wikipedia

	/** Divide : Partition the array A[low....high] into two sub-arrays
	* A[low....j-1] and A[j+1...high] such that each element
	* of A[low....j-1] is less than or equal to A[j], which
	* in turn is is less than or equal to A[j+1...high]. Compute
	* the index j as part of this partitioning procedure.
	* Conquer : Sort the two sub-arrays A[low....j-1] and A[j+1....high]
	* by recursive calls to quicksort
	**/
	#include<stdio.h>
	int main()
	{
	int arr[20], n, i;
	printf("Enter the size of the array\n");
	scanf("%d", &n);
	printf("Enter the elements to be sorted\n");
	for(i = 0; i < n; i++)
	scanf("%d", &arr[i]);
	quicksort(arr, 0, n-1);
	printf("Sorted array\n");
	for(i = 0; i < n; i++)
	printf("%d ", arr[i]);
	return 0;
	}
	void quicksort(int *arr, int low, int high)
	{
	int pivot, i, j, temp;
	if(low < high) {
	pivot = low; // select a pivot element
	i = low;
	j = high;
	while(i < j) {
	// increment i till you get a number greater than the pivot element
	while(arr[i] <= arr[pivot] && i <= high)
	i++;
	// decrement j till you get a number less than the pivot element
	while(arr[j] > arr[pivot] && j >= low)
	j--;
	// if i < j swap the elements in locations i and j
	if(i < j) {
	temp = arr[i];
	arr[i] = arr[j];
	arr[j] = temp;
	}
	}
	// when i >= j it means the j-th position is the correct position
	// of the pivot element, hence swap the pivot element with the
	// element in the j-th position
	temp = arr[j];
	arr[j] = arr[pivot];
	arr[pivot] = temp;
	// Repeat quicksort for the two sub-arrays, one to the left of j
	// and one to the right of j
	quicksort(arr, low, j-1);
	quicksort(arr, j+1, high);
	}
	}

view raw quick_sort.c hosted with ❤ by GitHub

Written by Munia Balayil

Merge Sort Using Recursion in C

GATE 2013 Comprehensive Information Page @ http://www.codeblocks.info/2012/08/gate-2013.html

"Merge sort (also commonly spelled mergesort) is an O(n log n) comparison-based sorting algorithm. Most implementations produce a stable sort, which means that the implementation preserves the input order of equal elements in the sorted output. Merge sort is a divide and conquer algorithm that was invented by John von Neumann in 1945." - Wikipedia

	/**
	* Divide : Divide the n-element array into two n/2-element
	* sub-arrays
	* Conquer : Sort the two sub-arrays recursively using
	* merge sort
	* Combine : Merge the two sorted subsequences to form the
	* sorted array
	**/
	#include<stdio.h>
	int arr[20]; // array to be sorted
	int main()
	{
	int n,i;
	printf("Enter the size of array\n"); // input the elements
	scanf("%d",&n);
	printf("Enter the elements:");
	for(i=0; i<n; i++)
	scanf("%d",&arr[i]);
	merge_sort(arr,0,n-1); // sort the array
	printf("Sorted array:"); // print sorted array
	for(i=0; i<n; i++)
	printf("%d",arr[i]);
	return 0;
	}
	int merge_sort(int arr[],int low,int high)
	{
	int mid;
	if(low<high) {
	mid=(low+high)/2;
	// Divide and Conquer
	merge_sort(arr,low,mid);
	merge_sort(arr,mid+1,high);
	// Combine
	merge(arr,low,mid,high);
	}
	return 0;
	}
	int merge(int arr[],int l,int m,int h)
	{
	int arr1[10],arr2[10]; // Two temporary arrays to
	hold the two arrays to be merged
	int n1,n2,i,j,k;
	n1=m-l+1;
	n2=h-m;
	for(i=0; i<n1; i++)
	arr1[i]=arr[l+i];
	for(j=0; j<n2; j++)
	arr2[j]=arr[m+j+1];
	arr1[i]=9999; // To mark the end of each temporary array
	arr2[j]=9999;
	i=0;
	j=0;
	for(k=l; k<=h; k++) { //process of combining two sorted arrays
	if(arr1[i]<=arr2[j])
	arr[k]=arr1[i++];
	else
	arr[k]=arr2[j++];
	}
	return 0;
	}

view raw merge_sort.c hosted with ❤ by GitHub

Related articles

---

Quick Sort Using Recursion in C
Heapsort in C
Bubble Sort in C
Selection Sort in C
Binary Search in C
Basic Stack Operations in C

Written by Munia Balayil

Selection Sort in C

/*
 * At every iteration, this sorting finds the smallest element
 * in the unsorted subarray and place it in its correct location.
 * Initially the full array = unsorted subarray. If an array has
 * n elements, after 1 iteration, the unsorted subarray contains
 * n-1 elements ( all elements except the smallest one,which is
 * placed at index 0) 
 */


#include<stdio.h>


int main(void)
{
  int i,n,arr[20],j;
  int min,pos,temp;
  printf("Enter the element size:");
  scanf("%d",&n);


  printf("Enter the array elements:");
  for(i=0;i<n;i++)
    scanf("%d",&arr[i]);


  for(i=0;i<n;i++)
  {
    //Assume i^th element to be min 
    min=arr[i];
    //Compare with all other elements to find the minimum one
    for(j=i+1;j<n;j++)
    {
      if(arr[j]<min)
      {
        min=arr[j];
        pos=j;
      }
    }
   //If assumed min is not equal to actual min
   // swap their locations
    if(min!=arr[i])
    {
      temp=arr[i];
      arr[i]=min;
      arr[pos]=temp;
    }
  }


  printf("The sorted array\n");
  for(i=0;i<n;i++)
    printf("%d ",arr[i]);
  
  return 0;
}

Written by Munia Balayil