## Saturday, March 1, 2014

### Definition of an Algorithm, Properties of an Algorithm, Structure of an Algorithm, Analysis of an Algorithm, Time Complexity, Factors that affects time complexity analysis, Factors that should not affect time complexity analysis, Asymptotic Notations - Big-oh Notation, Little-oh Notation, Omega Notation

Definition of an Algorithm: An algorithm is any well-defined computational procedure that is composed of a finite set of steps and takes some value or set of values as input and produces some value or set of values as output in a finite length of time.
Properties of an Algorithm: An algorithm must satisfy the following criteria-
1)      Input: Zero or more quantities are externally supplied.
2)      Output: At least one quantity is produced.
3)      Definiteness: Each instruction is clear and unambiguous.
4)      Finiteness: If we trace out the instructions of an algorithm, then for all cases the algorithm terminates all cases, the algorithm terminates after a finite number of steps.
5)      Effectiveness: Every Instruction must be very basic so that it can be carried out in principle, by a person using only pencil and paper. It is not enough that each operation definite as in criteria 3. It is also must be feasible.
Structure of an Algorithm
2)      Assignment Step
3)      Decision Step
4)      Repetitive Step
5)      Output Step

Analysis of Algorithms
Efficiency of an algorithm can be measured in terms of:
• Execution time (time complexity)
• The amount of memory required (space complexity)
Time Complexity: A measure of the amount of time required to execute an algorithm.
a)      Analysis is based on the amount of work done by the algorithm
b)      Time complexity expresses the relationship between the size of the input and the run time for the algorithm
c)       Usually expressed as a proportionality, rather than an exact function

·        Factors that should not affect time complexity analysis:
1)      The programming language chosen to implement the algorithm.
2)      The quality of the compiler.
3)      The speed of the computer on which the algorithm is to be executed

·        Factors that affects Time Complexity:
1)      Characteristics of the computer system (e.g. processor speed, amount of memory, ﬁle-system type, etc.)
2)      The way the algorithm is implemented
3)      The particular instance of data the algorithm is operating on (e.g., amount of data, type of data).
4)      Number of arithmetic operations performed
6)      Number of times through a critical loop
7)      Number of array elements accessed
Asymptotic Notations: Asymptotic notations are used to make meaningful statement about the efficiency of algorithms. These notations introduce some terminology that enables us to make meaningful statements about the time and space complexities of an algorithm. Commonly used asymptotic notations are:
1.       Big-Oh Notation (Upper Bound)
2.       Omega Notation (Lower Bound)
3.       Theta Notation (Tight Bound)
4.       Little-oh Notation
5.       Little-omega Notation
Big-Oh Notation
Definition: The function f(n) = O(g(n)) (read as “f of n is big-oh of g of n”) iff there exist positive constants c and n0 such that f(n) ≤ c * g(n) for all n≥n0.

Omega Notation
Definition: The function f(n) = (g(n)) (read as “f of n is omega of g of n”) iff there exist positive constants c and n0 such that f(n) ≥ c * g(n) for all n≥n0.

Theta Notation
Definition: The function f(n) = Ɵ(g(n)) (read as “f of n is theta of g of n”) iff there exist positive constants c1, c2 and n0 such that c1* g(n) f(n) ≤ c2 * g(n) for all n≥n0.

### Difference Between Static Memory Allocation & Dynamic Memory Allocation

 STATIC MEMORY ALLOCATION DYNAMIC MEMORY ALLOCATION Memory is allocated before the execution of the program begins (During Compilation). Memory is allocated during the execution of the program. Variables remain permanently allocated. Allocated only when program unit is active. In this type of allocation Memory cannot be resized after the initial allocation. In this type of allocation Memory can be dynamically expanded and shrunk as necessary. Implemented using stacks. Implemented using heap. Faster execution than Dynamic. Slower execution than static. It is less efficient than Dynamic allocation strategy. It is more efficient than Static allocation strategy. Implementation of this type of allocation is simple. Implementation of this type of allocation is complicated. Memory cannot be reuse when it is no longer needed. Memory can be freed when it is no longer needed & reuse or reallocate during execution.

## Thursday, September 13, 2012

### Shift Reduce Parsing Technique

Parse the String ( a + b ) * c using Shift Reduce Parsing from the given grammar.
1.       E →(E)
2.       E →E+E
3.       E →E*E
4.       E →a | b | c
 Stack Input Operation \$ ( a + b ) * c Push ( \$ ( a + b ) * c Push a \$ ( a + b ) * c Pop a & push E as E →a \$ ( E + b ) * c Push + \$ ( E + b ) * c Push b \$ ( E + b ) * c Pop b & push E as E →b \$ ( E + E ) * c Pop E + E & push E as E →E + E \$ ( E ) * c Push ) \$ ( E ) * c Pop ( E ) & push E as E → ( E ) \$ E * c Push * \$ E * c Push c \$ E * c \$ Pop c & push E as E → c \$ E * E \$ Pop E * E & push E as E →E * E \$ E \$ Accept

Implementation in JAVA:
Compiler.java
import static java.lang.System.out;
import java.util.Scanner;
public class Compiler
{
static Scanner s=new Scanner(System.in);
public static void main(String args[])
{
out.print("How many Rule? :");
int r=s.nextInt();
String[][] rule=new String[r];
out.println("Enter The Rule:");
int i,j;
for(i=0;i
{
for(j=0;j<2 j="j" p="p">
rule[i][j]=s.next();
}
out.println("Rules are:");
for(i=0;i
{
for(j=0;j<2 j="j" p="p">
{
out.print(rule[i][j]);
if(j==0) out.print(" -> ");
}
out.println();
}
int choice;
do
{
out.println("Enter the String:");
String str=s.next();
Stack stck=new Stack(str.length());
for(j=0;j
{
out.println("PUSH : "+str.charAt(j));
stck.push(str.charAt(j));
out.println("top:"+stck.top);

int isPush;
do
{
isPush=0;
String str2 = "";
for(i=stck.top-1;i>=0;i--)
{
int pos=0;
str2=new StringBuffer(str2).insert(pos, stck.stack[i]).toString();
pos++;
for(int k=0;k
{
out.println("Check Rule : String:"+str2);
if(str2.equals(rule[k]))
{
out.println("RULE MATCHED");
for(int pop=0;pop
{
out.println("POP : "+stck.pop());
}
stck.push(rule[k].charAt(0));
isPush=1;
out.println("PUSH : "+rule[k].charAt(0));
}
}
for(int m=0;m
out.print("\nStack: "+stck.stack[m]);
out.println();
}
}while(isPush==1);
}
out.println("\nFINALLY IN THE STACK:");
for(i=0;i
out.print(stck.stack[i]);

out.print("\nDo you want to check for another String(0-NO/1-YES)? ");
choice=s.nextInt();
if(choice==0) System.exit(0);
}while(choice==1);
}
}
Stack.java:

public class Stack
{
public int top,size;
public char stack[];
Stack(int sizeOfStack)
{
this.size=sizeOfStack;
stack=new char[size];
top=0;
}
public boolean push(char x)
{
if(top==size) return false;
else
{
stack[top++]=x;
return true;
}
}
public char pop()
{
if(top==0) return '0';
else return stack[--top];
}
public boolean isEmpty()
{
if(top==0) return true;
else return false;
}
public boolean isFull()
{
if(top==size) return true;
else return false;
}
}

OUTPUT:
How many Rule? :6
Enter The Rule:
E
a
E
b
E
c
E
E+E
E
E*E
E
(E)
Rules are:
E -> a
E -> b
E -> c
E -> E+E
E -> E*E
E -> (E)
Enter the String:
(a+b)*c
PUSH : (
top:1
Check Rule : String:(
Check Rule : String:(
Check Rule : String:(
Check Rule : String:(
Check Rule : String:(
Check Rule : String:(

Stack: (
PUSH : a
top:2
Check Rule : String:a
RULE MATCHED
POP : a
PUSH : E
Check Rule : String:a
Check Rule : String:a
Check Rule : String:a
Check Rule : String:a
Check Rule : String:a

Stack: (
Stack: E
Check Rule : String:(a
Check Rule : String:(a
Check Rule : String:(a
Check Rule : String:(a
Check Rule : String:(a
Check Rule : String:(a

Stack: (
Stack: E
Check Rule : String:E
Check Rule : String:E
Check Rule : String:E
Check Rule : String:E
Check Rule : String:E
Check Rule : String:E

Stack: (
Stack: E
Check Rule : String:(E
Check Rule : String:(E
Check Rule : String:(E
Check Rule : String:(E
Check Rule : String:(E
Check Rule : String:(E

Stack: (
Stack: E
PUSH : +
top:3
Check Rule : String:+
Check Rule : String:+
Check Rule : String:+
Check Rule : String:+
Check Rule : String:+
Check Rule : String:+

Stack: (
Stack: E
Stack: +
Check Rule : String:E+
Check Rule : String:E+
Check Rule : String:E+
Check Rule : String:E+
Check Rule : String:E+
Check Rule : String:E+

Stack: (
Stack: E
Stack: +
Check Rule : String:(E+
Check Rule : String:(E+
Check Rule : String:(E+
Check Rule : String:(E+
Check Rule : String:(E+
Check Rule : String:(E+

Stack: (
Stack: E
Stack: +
PUSH : b
top:4
Check Rule : String:b
Check Rule : String:b
RULE MATCHED
POP : b
PUSH : E
Check Rule : String:b
Check Rule : String:b
Check Rule : String:b
Check Rule : String:b

Stack: (
Stack: E
Stack: +
Stack: E
Check Rule : String:+b
Check Rule : String:+b
Check Rule : String:+b
Check Rule : String:+b
Check Rule : String:+b
Check Rule : String:+b

Stack: (
Stack: E
Stack: +
Stack: E
Check Rule : String:E+b
Check Rule : String:E+b
Check Rule : String:E+b
Check Rule : String:E+b
Check Rule : String:E+b
Check Rule : String:E+b

Stack: (
Stack: E
Stack: +
Stack: E
Check Rule : String:(E+b
Check Rule : String:(E+b
Check Rule : String:(E+b
Check Rule : String:(E+b
Check Rule : String:(E+b
Check Rule : String:(E+b

Stack: (
Stack: E
Stack: +
Stack: E
Check Rule : String:E
Check Rule : String:E
Check Rule : String:E
Check Rule : String:E
Check Rule : String:E
Check Rule : String:E

Stack: (
Stack: E
Stack: +
Stack: E
Check Rule : String:+E
Check Rule : String:+E
Check Rule : String:+E
Check Rule : String:+E
Check Rule : String:+E
Check Rule : String:+E

Stack: (
Stack: E
Stack: +
Stack: E
Check Rule : String:E+E
Check Rule : String:E+E
Check Rule : String:E+E
Check Rule : String:E+E
RULE MATCHED
POP : E
POP : +
POP : E
PUSH : E
Check Rule : String:E+E
Check Rule : String:E+E

Stack: (
Stack: E
Check Rule : String:(E+E
Check Rule : String:(E+E
Check Rule : String:(E+E
Check Rule : String:(E+E
Check Rule : String:(E+E
Check Rule : String:(E+E

Stack: (
Stack: E
Check Rule : String:E
Check Rule : String:E
Check Rule : String:E
Check Rule : String:E
Check Rule : String:E
Check Rule : String:E

Stack: (
Stack: E
Check Rule : String:(E
Check Rule : String:(E
Check Rule : String:(E
Check Rule : String:(E
Check Rule : String:(E
Check Rule : String:(E

Stack: (
Stack: E
PUSH : )
top:3
Check Rule : String:)
Check Rule : String:)
Check Rule : String:)
Check Rule : String:)
Check Rule : String:)
Check Rule : String:)

Stack: (
Stack: E
Stack: )
Check Rule : String:E)
Check Rule : String:E)
Check Rule : String:E)
Check Rule : String:E)
Check Rule : String:E)
Check Rule : String:E)

Stack: (
Stack: E
Stack: )
Check Rule : String:(E)
Check Rule : String:(E)
Check Rule : String:(E)
Check Rule : String:(E)
Check Rule : String:(E)
Check Rule : String:(E)
RULE MATCHED
POP : )
POP : E
POP : (
PUSH : E

Stack: E
Check Rule : String:E
Check Rule : String:E
Check Rule : String:E
Check Rule : String:E
Check Rule : String:E
Check Rule : String:E

Stack: E
PUSH : *
top:2
Check Rule : String:*
Check Rule : String:*
Check Rule : String:*
Check Rule : String:*
Check Rule : String:*
Check Rule : String:*

Stack: E
Stack: *
Check Rule : String:E*
Check Rule : String:E*
Check Rule : String:E*
Check Rule : String:E*
Check Rule : String:E*
Check Rule : String:E*

Stack: E
Stack: *
PUSH : c
top:3
Check Rule : String:c
Check Rule : String:c
Check Rule : String:c
RULE MATCHED
POP : c
PUSH : E
Check Rule : String:c
Check Rule : String:c
Check Rule : String:c

Stack: E
Stack: *
Stack: E
Check Rule : String:*c
Check Rule : String:*c
Check Rule : String:*c
Check Rule : String:*c
Check Rule : String:*c
Check Rule : String:*c

Stack: E
Stack: *
Stack: E
Check Rule : String:E*c
Check Rule : String:E*c
Check Rule : String:E*c
Check Rule : String:E*c
Check Rule : String:E*c
Check Rule : String:E*c

Stack: E
Stack: *
Stack: E
Check Rule : String:E
Check Rule : String:E
Check Rule : String:E
Check Rule : String:E
Check Rule : String:E
Check Rule : String:E

Stack: E
Stack: *
Stack: E
Check Rule : String:*E
Check Rule : String:*E
Check Rule : String:*E
Check Rule : String:*E
Check Rule : String:*E
Check Rule : String:*E

Stack: E
Stack: *
Stack: E
Check Rule : String:E*E
Check Rule : String:E*E
Check Rule : String:E*E
Check Rule : String:E*E
Check Rule : String:E*E
RULE MATCHED
POP : E
POP : *
POP : E
PUSH : E
Check Rule : String:E*E

Stack: E
Check Rule : String:E
Check Rule : String:E
Check Rule : String:E
Check Rule : String:E
Check Rule : String:E
Check Rule : String:E

Stack: E

FINALLY IN THE STACK:
E
Do you want to check for another String(0-NO/1-YES)? 1
Enter the String:
(a+b)
PUSH : (
top:1
Check Rule : String:(
Check Rule : String:(
Check Rule : String:(
Check Rule : String:(
Check Rule : String:(
Check Rule : String:(

Stack: (
PUSH : a
top:2
Check Rule : String:a
RULE MATCHED
POP : a
PUSH : E
Check Rule : String:a
Check Rule : String:a
Check Rule : String:a
Check Rule : String:a
Check Rule : String:a

Stack: (
Stack: E
Check Rule : String:(a
Check Rule : String:(a
Check Rule : String:(a
Check Rule : String:(a
Check Rule : String:(a
Check Rule : String:(a

Stack: (
Stack: E
Check Rule : String:E
Check Rule : String:E
Check Rule : String:E
Check Rule : String:E
Check Rule : String:E
Check Rule : String:E

Stack: (
Stack: E
Check Rule : String:(E
Check Rule : String:(E
Check Rule : String:(E
Check Rule : String:(E
Check Rule : String:(E
Check Rule : String:(E

Stack: (
Stack: E
PUSH : +
top:3
Check Rule : String:+
Check Rule : String:+
Check Rule : String:+
Check Rule : String:+
Check Rule : String:+
Check Rule : String:+

Stack: (
Stack: E
Stack: +
Check Rule : String:E+
Check Rule : String:E+
Check Rule : String:E+
Check Rule : String:E+
Check Rule : String:E+
Check Rule : String:E+

Stack: (
Stack: E
Stack: +
Check Rule : String:(E+
Check Rule : String:(E+
Check Rule : String:(E+
Check Rule : String:(E+
Check Rule : String:(E+
Check Rule : String:(E+

Stack: (
Stack: E
Stack: +
PUSH : b
top:4
Check Rule : String:b
Check Rule : String:b
RULE MATCHED
POP : b
PUSH : E
Check Rule : String:b
Check Rule : String:b
Check Rule : String:b
Check Rule : String:b

Stack: (
Stack: E
Stack: +
Stack: E
Check Rule : String:+b
Check Rule : String:+b
Check Rule : String:+b
Check Rule : String:+b
Check Rule : String:+b
Check Rule : String:+b

Stack: (
Stack: E
Stack: +
Stack: E
Check Rule : String:E+b
Check Rule : String:E+b
Check Rule : String:E+b
Check Rule : String:E+b
Check Rule : String:E+b
Check Rule : String:E+b

Stack: (
Stack: E
Stack: +
Stack: E
Check Rule : String:(E+b
Check Rule : String:(E+b
Check Rule : String:(E+b
Check Rule : String:(E+b
Check Rule : String:(E+b
Check Rule : String:(E+b

Stack: (
Stack: E
Stack: +
Stack: E
Check Rule : String:E
Check Rule : String:E
Check Rule : String:E
Check Rule : String:E
Check Rule : String:E
Check Rule : String:E

Stack: (
Stack: E
Stack: +
Stack: E
Check Rule : String:+E
Check Rule : String:+E
Check Rule : String:+E
Check Rule : String:+E
Check Rule : String:+E
Check Rule : String:+E

Stack: (
Stack: E
Stack: +
Stack: E
Check Rule : String:E+E
Check Rule : String:E+E
Check Rule : String:E+E
Check Rule : String:E+E
RULE MATCHED
POP : E
POP : +
POP : E
PUSH : E
Check Rule : String:E+E
Check Rule : String:E+E

Stack: (
Stack: E
Check Rule : String:(E+E
Check Rule : String:(E+E
Check Rule : String:(E+E
Check Rule : String:(E+E
Check Rule : String:(E+E
Check Rule : String:(E+E

Stack: (
Stack: E
Check Rule : String:E
Check Rule : String:E
Check Rule : String:E
Check Rule : String:E
Check Rule : String:E
Check Rule : String:E

Stack: (
Stack: E
Check Rule : String:(E
Check Rule : String:(E
Check Rule : String:(E
Check Rule : String:(E
Check Rule : String:(E
Check Rule : String:(E

Stack: (
Stack: E
PUSH : )
top:3
Check Rule : String:)
Check Rule : String:)
Check Rule : String:)
Check Rule : String:)
Check Rule : String:)
Check Rule : String:)

Stack: (
Stack: E
Stack: )
Check Rule : String:E)
Check Rule : String:E)
Check Rule : String:E)
Check Rule : String:E)
Check Rule : String:E)
Check Rule : String:E)

Stack: (
Stack: E
Stack: )
Check Rule : String:(E)
Check Rule : String:(E)
Check Rule : String:(E)
Check Rule : String:(E)
Check Rule : String:(E)
Check Rule : String:(E)
RULE MATCHED
POP : )
POP : E
POP : (
PUSH : E

Stack: E
Check Rule : String:E
Check Rule : String:E
Check Rule : String:E
Check Rule : String:E
Check Rule : String:E
Check Rule : String:E

Stack: E

FINALLY IN THE STACK:
E
Do you want to check for another String(0-NO/1-YES)? 0
BUILD SUCCESSFUL (total time: 48 seconds)