Saturday, June 29, 2013

. Verify that the Mathematical Induction is valid.



The validity of Mathematical Induction can be proved by using well-ordering property.
Assume that P(1) is true and P(k)P(k+1) is also true. If the proof using mathematical induction is not valid then P(n) is true for all positive integers would be false.
Let the set of positive integers for which P(n) is false be T where T is a non-empty set. Since there is at least one element in T, by well-ordering property, T has a least element. Let the least element be m. Then m cannot be 1, since P(1) is assumed as true. Hence, m must be greater than 1.
So, m-1 is a positive integer other than 1, which is also not in T as m is the least element in T. This shows P(m-1) is true as m-1 is not in T.
Also by our assumption, P(m-1)P(m), so P(m) must be true to make the implication true. T. Hence, P(n) must be true for all positive integer n.
Therefore, mathematical induction is valid.

State strong Mathematical Induction (or second principle of M.I).



According to strong mathematical induction, P(n) is a statement(or a proposition) that may be true or false for all the positive integers which can be proved by stating p(n) is true for all n1 with the help of following steps:
1.       Show that P(1), P(2), ….., P(q) is true for q1. (basis step)
2.       Assume P(i) is true for all integer i such that, 1 i k and kq. (strong inductive hypothesis)
3.       Show that P(k+1) is true on the basis of strong inductive hypothesis. (inductive steps)

Write an algorithm to count total number of nodes in the singly linked list.



Conditions:
·         ‘SingleNode’ is the node representation of singly linked list, where,
struct my_node{      //structure name ‘my_node’
                   int data;    //data field
                   struct my_node *next;      //pointer to next node
                  };
typedef struct my_node SingleNode;    //defining a node of singly linked list ‘SingleNode’
·         ‘phead’ is a head pointer pointing to the first node
·         ‘last’ is a pointer to SingleNode
·         ‘count’ is a integer variable initially set to zero
ALGORITHM:
1.       Start
2.       check if the list is empty or not
if phead ==NULL
OUTPUT ‘Zero nodes’ and exit
else goto step 3
3.       Set the head pointer to a temporary variable
last=phead
4.       Traverse till the last node
SET while(last->next!= NULL)
{ increase the node count by 1
SET count++
point to the next node in the list
SET last=last->next
}
5.       Increase the value of count by 1 for last node if the list has more than one node otherwise this condition is applicable if the list has exactly one node.
6.       Display the total count of nodes
OUTPUT count
7.       Stop

Write an algorithm to delete the last node of the singly linked list.



Conditions:
·         ‘SingleNode’ is the node representation of singly linked list, where,
struct my_node{      //structure name ‘my_node’
                   int data;    //data field
                   struct my_node *next;      //pointer to next node
                  };
typedef struct my_node SingleNode;    //defining a node of singly linked list ‘SingleNode’
·         ‘phead’ is a head pointer pointing to the first node
·         ‘last’ is a pointer to SingleNode
·         ‘secondlast’ is a pointer to SingleNode
ALGORITHM:
1.       Start
2.       check if the list is empty or not
if phead==NULL
OUTPUT ‘No any node to delete’ and exit
else goto step 3
3.       Set the head pointer to temporary pointer
SET last=phead->next
SET secondlast=phead
4.       Find the last node
SET while(last->next!=NULL)
      { SET last=last->next
        SET secondlast= secondlast->next  }
5.       set the newly last node to NULL
SET secondlast->next= NULL
6.       Display the element of deleted node
OUTPUT last->data
7.       Free the deleted node from the system
SET free(last)
8.       Stop

Write an algorithm to delete the first node of the singly linked list.



Conditions:
·         ‘SingleNode’ is the node representation of singly linked list, where,
struct my_node{      //structure name ‘my_node’
                   int data;    //data field
                   struct my_node *next;      //pointer to next node
                  };
typedef struct my_node SingleNode;    //defining a node of singly linked list ‘SingleNode’
·         ‘phead’ is a head pointer pointing to the first node
·         ‘temp’ is a pointer to SingleNode
ALGORITHM:
1.       Start
2.       check if the list is empty or not
if phead==NULL
OUTPUT ‘No any node to delete’ and exit
else goto step 3
3.       set the head pointer to the temporary pointer
temp=phead
4.       Increase the position of head pointer by 1
SET phead= phead->next
5.       Display the element of deleted node
OUTPUT temp->data
6.       Free the deleted node from the system
SET free(temp)
7.       Stop