character to integer

problem : implement atoi function

declaration : int atoi(char*s);

solution 1 : (left to right )

int atoi(char*s)
{
    int valuesofar=0;
    if(s)
    {    
	while(*s && *s>='0' && *s<='9')
   	{
       		valuesofar = valuesofar*10 + (*s-'0');
       		s++;
   	}
    }
   return valuesofar;
}

solution 2: (right to left )

int atoi(char*s)
{
    int valuesofar=0;
    int power=1;
    char*x;
    if(s)
    {   
	x = s;
	while(*x)
	x++;            // reach the end of the string
  
	while(x>=s&& *x>='0' && *x<='9')
   	{
       		valuesofar += (*x-'0') * power ;
       		x--;
		power*=10;           // adjust power
   	}
    }
   return valuesofar;
}

fair result from an unfair coin

you are given an unfair coin in which head has higher probability of occurring than tails.

solution :

assume

TH as head
HT as tail
TT, HH than toss again

now new head and tail have equal probabilities

Using bit vectors

a nice discussion on why one should use bit vectors and not integer arrays in some particular situations

bit vector

print a unsigned long int using putchar

problem : print an unsigned long integer using only putchar

solution : we'll have to break the number and print the individual digit, we can use % operation to get the digits

code :

void putlong(unsigned long n) {
  if (n < 10) {
    putchar(n + '0');
    return;
  }
  putlong(n / 10);
  putchar(n % 10 + '0');
}

reverse a string using recursion

problem : reverse a string using recursion

: solution

void print_reverse(char* str)
{
	if(*str=='\0')return;
	else
	print_reverse(str+1)
	putchar(*str);
}

permutation of parantheses

problem : generate all the permutations of valid parantheses

e.g.

input 1
output {}

input 2
output {}{}, {{}}

input 3
output: {}{}{}, {{{}}}, {{}{}}, {{}}{}, {}{{}}

solution :

note : number of permutation can be easily found by noticing that it is forming a catalan series, 1,2,5,... so nth term will be (2^n -n).

solution:

sorting O(nlogn)

earlier post on sorting covered sorting with complexity O(n2)

this post will cover the O(nlogn) case

1) Quick sort
// explanation : TODO


2) merge sort
TODO:

3) Heap Sort

Sorting

Some basic sorting algorithms {must know}

1) Bubble sort
2) Insertion sort
3) Selection sort

bubble sort :



> worst case time complexity : O(n^2)
> best case time complexity : O(n) { when list is already sorted }
> worst case space complexity: O(1) auxiliary

> not used anymore,

Insertion sort :
algotithm : assume a sorted array in the given array, select one of the card and insert it into its correct position in the sorted array .



> better than selection and bubble sort
> space complexity : O(1)
> worst case time complexity : O(n^2)
> best case time complexity : O(n) {when array is already sorted }
> it is stable : stability means that it does not change the order of elements with equal keys
> modified version : shell sort
> for small input, insertion sort may perform better than even quick sort

selection sort
simply select the element one by one in increasing order and insert them into their correct position



> worse (almost half ) than insertion sort.
> time complexity O(n2) { both worse and best }
> variant : heap sort

BackTracking

backtracking is used as a searching technique
so what are we searching basically ?
we are searching the tree for a particular goal leaf node/nodes.

How to apply backtracking
1) Make a choice
2) Compute the consequences
3) If the search is unsuccessful or needs to continue for some other reason,
4) Undo the consequences,
5) Undo the choice
6) Make a different choice
7) repeat from 2

Every language that supports loops, supports backtracking .

basic problem 1 : just by following the definition given above we can have a very trivial case where backtracking can be applied using just for loops and continue statement
problem : find the number of different Pythagoras triplets where hypotenuse is less than 100 .
solution :
1) make choice of sides in the three for loops
2) compute the condition for triplet, if condition fails, means we need to backtrack and stop processing further solution (printing in this case) so just continue; and start with new values of one of the sides and again repeat the above steps.

#include<stdio.h>
int main()
{
	int n = 100;
	int i,j,k,count=1;
	for(i=5;i<=n;i++)
	{
		for(j=1;j<i;j++)
		{
			for(k=1;k<=j;k++)
			{
				if((j*j + k*k )!= i*i)
				 continue;
				printf("%2d | %d %d %dn",count++,i,j,k);
			}
		}
	}
	return 0;
}

code on ideone :http://ideone.com/vDlB0
second problem : generate all the permutations of a string.

solution at : http://quickalgo.blogspot.com/2011/08/permutations-of-string.html
note: notice the tree in the above post, the solutions are the leaf nodes  and we are doing depth first traversal in that tree printing only the leaf nodes.
code :

#include <stdio.h>
#include <string.h>

void swap(char*a,char*b);
void permute(char* s, int i, int n);

int main()
{
	char s[] = "abc";    
	int n = strlen(s);
	permute(s,0,n);      
	return 0;
}
void swap(char*a,char*b)
{
	char t;
	t = *a;
	*a=*b;
	*b=t;
}

void permute(char* s, int i, int n)
{
	int j;
	if(i==n)   // reached the leaf node.
	{
		printf("%sn",s); // process solution  
	}
	else
	{
		for(j=i;j<n;j++)
		{
			swap((s+i),(s+j));  // choose an option and move forward
			permute(s,i+1,n);   // compute new solution
			swap((s+i),(s+j));  // backtrack after printing
		}
	}
}

third problem : 8 queens puzzle
solution is here : http://quickalgo.blogspot.com/2011/08/8-queens-problem.html
code for reference

#include<stdio.h>
#include<stdlib.h>
int t[8] = {-1};
int sol = 1;

void printsol()
{
	int i,j;
	char crossboard[8][8];
	for(i=0;i<8;i++)
	{
		for(j=0;j<8;j++)
		{
			crossboard[i][j]='_';
		}
	}
	for(i=0;i<8;i++)
	{
			crossboard[i][t[i]]='q';
	}

	for(i=0;i<8;i++)
	{
		for(j=0;j<8;j++)
		{
			printf("%c ",crossboard[i][j]);
		}
		printf("n");
	}  
}
int empty(int i)
{
	int j=0;
	while((t[i]!=t[j])&&(abs(t[i]-t[j])!=(i-j))&&j<8)j++;
	return i==j?1:0;
}

void queens(int i)
{
	for(t[i] = 0;t[i]<8;t[i]++)
	{
		if(empty(i))
		{
			if(i==7){
				printsol();
				printf("n solution %dn",sol++);
			}
			else
			queens(i+1);
		}
	}
}



int main()
{
	queens(0);
	return 0;
}

problem 4: knight's tour problem
The knight is placed on the empty board and, moving according to the rules of chess, must visit each square exactly once. A knight's tour is called a closed tour if the knight ends on a square attacking the square from which it began (so that it may tour the board again immediately with the same path). Otherwise the tour is open http://en.wikipedia.org/wiki/Knight's_tour

explanation of problem :

what is a knight's tour ==>

sequence of moves (i.e., a tour) by a knight chess piece (which may only make moves which simultaneously shift one square along one axis and two along the other) such that each square of the board is visited exactly once.
solution : problem 5: Rat in a maze

problem 6: coloring a map

problem 7: sudoku puzzle

Linked List

Implemented using pointers,

typedef struct node{
    int value;
    struct node* next;
}listnode;

listnode*head = NULL;
listnode*tail = NULL;

Primary operations :

1) searching
2) insertion
3) deletion

Searching can be done in two ways , either iteratively or recursively recursive code : simple
if-else recursive method. type : tail recursive. base case -> either list is empty or value found at head

listnode* search(listnode*head,int x)
{
    if(head==NULL)
        return;
    else if(head->value==x)
        return head;
    else
    return search(head->next,x);
}

time complexity : O(n) space complexity: O(1)

Insertion in a list :


important cases :
1) list can be empty, so head pointer will have to be adjusted,
2) pass address of the head and tail pointer in addnode() function.
3) otherwise simply insert at the tail of the list and update the tail pointer.

void addnode(listnode**head,listnode**tail,int value)
{
	listnode* temp = (listnode*)malloc(sizeof(listnode));
	temp->value = value;
	temp->next = NULL;
	
	if(*head == NULL) //list was empty
	{
		*head = temp;
		*tail = *head;   // adjust tail pointer
	}
	
	else
	(*tail)->next = temp;   // add at the end of tail
	*tail = (*tail)->next;  // adjust tail pointer
	return ;
}

Deletion : find the pointer to the node that is to be deleted and remove the desired node from the list. 

Why linked list is preferred ?:
1) insertions and deletions are simple as compared to arrays where number of elements have to be shifted
2) linked list are recursive objects : cut the first element , and what we have is another linked list. 

Important operations and questions about linked lists

1) reverse a linked list
 a) recursive
b) iterative

2) sort a linked list
a) using bubble sort technique
b) using merge sort {best way under normal condition}

3) doubly linked list {repeat 1, and 2 for the doubly linked list }

4)detect whether a linked list contain a loop or not, find and remove the loop

5) find the middle of the linked list 6) find the nth node from the last in a linked list

7) reverse alternate k nodes in a singly linked list 

8) remove duplicates from sorted/unsorted singly linked list

9) print a linked list in reverse order

10) given two linked list , find their point of intersection

11) generate doubly linked list from a binary search tree

12) insert nodes into the list in sorted fashion

13) given a linked list of characters, check whether it is palindrome or not

// todo :

C precedence table

C Operator Precedence Table

Memory allocation in C

In a C program we can have three types of variables


static variables, global variables {initialized + uninitialized}, automatic variables


a computer program memory is divided into three sections


data segment {DATA + BSS + HEAP}
stack
code segment


1) Data segment :


a)DATA : contains
----> global and static variables used by the program that are initialized.
Ex: static int i = 10 will be stored in data segment and global int i = 10 will be stored in data segment.


can be further divided into
=> initialized read-only area
e.g. const char* string = "hello world" makes the string literal "hello world" to be stored in initialized read-only area and the character pointer variable string in initialized read-write area.
=> initialized read-write area.
string defined by char s[] = "hello world" in C and a C statement like int debug=1 outside the main would be stored in initialized read-write area.


b)BSS
The BSS segment also known as uninitialized data starts at the end of the data segment and contains all global variables and static variables that are initialized to zero or do not have explicit initialization in source code. For instance a variable declared static int i; would be contained in the BSS segment.


c)Heap
The Heap area is managed by malloc, realloc, and free, The Heap area is shared by all shared libraries and dynamically loaded modules in a process.


2) Stack
The stack area is just below the heap area and they grow the opposite direction.
The stack area contains the program stack, a LIFO structure, A "stack pointer" register tracks the top of the stack; it is adjusted each time a value is "pushed" onto the stack.
stores local (auto) variables, passing function arguments, storing return address, etc


3) Code segment,
also known as a text segment or simply as text, is one of the sections of a program in an object file or in memory, which contains executable instructions.
It has a fixed size and is usually read-only. If the text section is not read-only, then the particular architecture allows self-modifying code.


links
http://www.bravegnu.org/gnu-eprog/c-startup.html
http://blog.ooz.ie/2008/09/0x03-notes-on-assembly-memory-from.html
http://stackoverflow.com/questions/79923/what-and-where-are-the-stack-and-heap
http://www.maxi-pedia.com/what+is+heap+and+stack

difference between pointers and arrays

Are these two things same?

char* firstname = "rohit;

char secondname[] ="jangid";

answer is NO, they are not same .

why ?

suppose both these lines are there in a program hello.c.
two things happen

memory to "rohit" is allocated in a write protected area of the program also called "data section" of the program, means that we can't make any changes in "rohit". obviously firstname is only pointing to this memory section and we can use firstname++ without any error

whereas memory to "jangid" is actually allocated in a local stack, in array secondname.
here secondname can be treated as const pointer, which means that we can's use secondname++, but we can modify the string "jangid" without any error as it is not protected.

longest increasing subsequence

problem: given an integer array, find the longest increasing subsequence in it.

solution : trivial dp problem.

code // ->

finding binomial coefficient

problem: find the coefficient of x^r in the expansion of (x+1)^n . nCr basically

solution : using dynamic programming

8 queens problem

problem : you have to place 8 queens on a chess board in such a way that no two queens are able to kill each other. generate all such ways

solution : use backtracking to trace all the possible ways to do this. there are 92 such ways

note: there is no need to use 2d array to represent chess board , here chess board can be represented as single dimension array chess[], where chess[i] = j implies a piece is there on i'th row and j'th column.

tree from inorder and preorder

problem : given preorder and inorder traversal of a binary tree , generate the tree from it.

solution:

lets take the basic case first

given: inorder and preorder traversals of a tree in array form

assuming tree to be having unique elements only

returns the head pointer to the tree generated



output at code on ideone

E R data model

consists of sets of entities and set of relationships between those entities.

entity ==> set of attributes

relationship ==> an association between several entities

note: a function that an entity plays in a relationship is called its role

relationship's attributes are called descriptive attributes

mapping cardinalities : better explained in korth

weak entity sets : entity that cannot be uniquely identified by its attributes alone; therefore, it must use a foreign key in conjunction with its attributes to create a primary key. The foreign key is typically a primary key of an entity it is related to.
a weak entity set is indicated by a bold rectangle (the entity) connected by a bold type arrow to a bold diamond (the relationship). This type of relationship is called an identifying relationship

Relational data model

relational model consists of collection of tables (relations) . table contain columns and rows. row in a table represents the relationship between the set of values.
we can say that basically table is collection of relationships(specified by rows)

note : n-tuple means a tupe with n values where tuple means a row .

main topics

keys :
definitions

super key : is a set of one or more attributes that , taken collectively , allow us to identify uniquely a tuple in the relations , so there can be many different super keys in a relation

candidate keys : a super key whose no subset is a super key ( basically minimal superkey)

primary key : a candidate key chosen by the database designer as the principle means of identifying the tuples ( example as roll_no)

foreign key : if a relation(referencing relation) contains within its attribute the primary key or even the super key of another relation(referenced relation) than that attribute is called foreign key.
a row in the referencing table cannot contain values that don't exist in the referenced table (except potentially NULL).

note : A FOREIGN KEY constraint can reference columns in tables in the same database or within the same table. These are called self-referencing tables. For example, consider an employee table that contains three columns: employee_number, employee_name, and manager_employee_number. Because the manager is also an employee, there is a foreign key relationship from the manager_employee_number column to the employee_number column.

note: The constraint enforces referential integrity by guaranteeing that changes cannot be made to data in the primary key table if those changes invalidate the link to data in the foreign key table. If an attempt is made to delete the row in a primary key table or to change a primary key value, the action will fail when the deleted or changed primary key value corresponds to a value in the FOREIGN KEY constraint of another table. To successfully change or delete a row in a FOREIGN KEY constraint, you must first either delete the foreign key data in the foreign key table or change the foreign key data in the foreign key table, which links the foreign key to different primary key data.


Relational operations :

join
Cartesian product
union
intersection
and set difference

DBMS: basics

dbms ==> database management system basically comprises of (database + a program to manage it)

to better categorize the database, there are certain types of data model

relational :
there are tables to represent data + the relationships between them, table contain columns, tables are also called relations and columns as attributes.

ER model : contain set of entities( like objects ) and set of relationships among these objects

object oriented : not that much important will deal in later posts :-)


to specify database obviously we need a language : this language comprises of two parts
1) data definition language (DDL) specifies schema
2) data modification language (DML) database queries and updates.

they are basically implemented as different types of statements in one general language like SQL

lets not go into the details of DML for now, and focus on DML

every data has some sort of constraints on like, roll number of students can't be negative , cell numbers can't be zero digit etc
so while specifying database we need some way to specify these contraints as well. this is done in DDL,
some contraints are

1) domain constraints
2) referential integrity
3) assertions
4) authorizations

DDL is an interpreted language and its output is stored in a data dictionary which contains metadata.

now we have some good basics , so lets dive into some detailed topics

? what is database design?

basically database design means that you have to design schema for database

design process : ( from korth )

1) understand the user requirements
2) and decide the data model (quite obvious)
3) using the model, transform user requirements into conceptual schema of database
if model is relational decide tables, columns.
use normalization enter the set of attributes and get the tables as output
or we can use ER model as well .

the widely (particularly for large scale) used data model is the ER model .
ER model has some mapping cardinalities which are the additional rules to be satisfied by the database contents, ( the number of entities to which another entity can be associated )

the concept of normalization : gives us the benefit of auto generated tables with no lesser redundancy but on the cose of extra information required called functional dependencies

two bad things that can go while designing a database is

1) information can get repeated
2) we may get unable to represent certain desired information

definitions

atomicity : all or none
consistency : same everywhere
isolation
durability : persistance even after the system failure
transaction : collection of operations that perform a single logical function.