. 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