Data Structures and Algorithms (Stack as Link List) - Tirthankar Pal - MBA from IIT Kharagpur, GATE, GMAT, IIT Written Test, Interview were a part of MBA Entrance, B.S. in Computer Science from NIELIT

Stack implemented by a Link List

#include<stdio.h>

#include<conio.h>

 

struct Node

{

   int data;

   struct Node *next;

}*top = NULL;

 

void push(int);

void pop();

void display();

 

void main()

{

   int choice, value;

   clrscr();

   printf("\n:: Stack using Linked List ::\n");

   while(1){

      printf("\n****** MENU ******\n");

      printf("1. Push\n2. Pop\n3. Display\n4. Exit\n");

      printf("Enter your choice: ");

      scanf("%d",&choice);

      switch(choice){

                     case 1: printf("Enter the value to be insert: ");

                                          scanf("%d", &value);

                                          push(value);

                                          break;

                     case 2: pop(); break;

                     case 3: display(); break;

                     case 4: exit(0);

                     default: printf("\nWrong selection!!! Please try again!!!\n");

      }

   }

}

void push(int value)

{

   struct Node *newNode;

   newNode = (struct Node*)malloc(sizeof(struct Node));

   newNode->data = value;

   if(top == NULL)

      newNode->next = NULL;

   else

      newNode->next = top;

   top = newNode;

   printf("\nInsertion is Success!!!\n");

}

void pop()

{

   if(top == NULL)

      printf("\nStack is Empty!!!\n");

   else{

      struct Node *temp = top;

      printf("\nDeleted element: %d", temp->data);

      top = temp->next;

      free(temp);

   }

}

void display()

{

   if(top == NULL)

      printf("\nStack is Empty!!!\n");

   else{

      struct Node *temp = top;

      while(temp->next != NULL){

                     printf("%d--->",temp->data);

                     temp = temp -> next;

      }

      printf("%d--->NULL",temp->data);

   }

}

Tirthankar Pal

MBA from IIT Kharagpur with GATE, GMAT, IIT Kharagpur Written Test, and Interview

2 year PGDM (E-Business) from Welingkar, Mumbai

4 years of Bachelor of Science (Hons) in Computer Science from the National Institute of Electronics and Information Technology

Google and Hubspot Certification

Brain Bench Certification in C++, VC++, Data Structure and Project Management

10 years of Experience in Software Development out of that 6 years 8 months in Wipro

Selected in Six World Class UK Universities:-

King's College London, Durham University, University of Exeter, University of Sheffield, University of Newcastle, University of Leeds

Data Structures and Algorithms (Link List Problems) - Tirthankar Pal - MBA from IIT Kharagpur, GATE, GMAT, IIT Written Test, Interview were a part of MBA Entrance, B.S. in Computer Science from NIELIT

 (a) Insert a new node after a given node.

          void insert_node(node *new_node, node *old_node)

          {

               temp = NULL;

               temp = old_node;

               old_node->next = new_node;

               new_node->next = temp;

           }

(b) Delete last node.

        

                                    #include <iostream>

                                    using namespace std;

                                     /* Link list node */

                                    struct Node {

                                                  int data;

                                                  struct Node* next;

                                     };

 

                                    /* Function to remove the last node 

                                        of the linked list */

                              Node* removeLastNode(struct Node* head)

                                    {

                                             if (head == NULL)

                                              return NULL;

 

                                             if (head->next == NULL) {

                                             delete head;

                                             return NULL;

                                              }

 

                                              // Find the second last node

                                              Node* second_last = head;

                                              while (second_last->next->next != NULL)

                                                     second_last = second_last->next;

 

                                             // Delete last node

                                                      delete (second_last->next);

 

                                              // Change next of second last

                                                         second_last->next = NULL;

 

                                     return head;

                                }   

 

(c) Count the number of elements in the list

      int count = 0;

      while(curr != NULL)

      {

          count++;

           curr = curr->next;

     }

     printf(count);

Tirthankar Pal

MBA from IIT Kharagpur with GATE, GMAT, IIT Kharagpur Written Test, and Interview

2 year PGDM (E-Business) from Welingkar, Mumbai

4 years of Bachelor of Science (Hons) in Computer Science from the National Institute of Electronics and Information Technology

Google and Hubspot Certification

Brain Bench Certification in C++, VC++, Data Structure and Project Management

10 years of Experience in Software Development out of that 6 years 8 months in Wipro

Selected in Six World Class UK Universities:-

King's College London, Durham University, University of Exeter, University of Sheffield, University of Newcastle, University of Leeds

 

Data Structures and Algorithms (Polynomials as Link List) - Tirthankar Pal - MBA from IIT Kharagpur, GATE, GMAT, IIT Written Test, Interview were a part of MBA Entrance, B.S. in Computer Science from NIELIT

 5x3+4x2+3x+2

POLY->(5,3)->(4,2)->(3,1)->(2,0)->NULL

To understand this concept better let's first brush up all the basic contents that are required.

Linked list is a data structure that stores each element as an object in a node of the list. every note contains two parts data and links to the next node.

Polynomial is a mathematical expression that consists of variables and coefficients. for example x^2 - 4x + 7

In the Polynomial linked list, the coefficients and exponents of the polynomial are defined as the data node of the list.

For adding two polynomials that are stored as a linked list. We need to add the coefficients of variables with the same power. In a linked list node contains 3 members, coefficient value link to the next node.

A linked list that is used to store Polynomial looks like −

Polynomial : 4x⁷ + 12x² + 45

This is how a linked list represented polynomial looks like.

Adding two polynomials that are represented by a linked list. We check values at the exponent value of the node. For the same values of exponent, we will add the coefficients.

Example,

Input :

p1= 13x8 + 7x5 + 32x2 + 54

p2= 3x12 + 17x5 + 3x3 + 98

Output : 3x12 + 13x8 + 24x5 + 3x3 + 32x2 + 152

Explanation −
For all power, we will check for the coefficients of the exponents that have
the same value of exponents and add them. The return the final polynomial.

Algorithm

Input − polynomial p1 and p2 represented as a linked list.

Step 1: loop around all values of linked list and follow step 2& 3.

Step 2: if the value of a node’s exponent. is greater copy this node to 

result node and head towards the next node.

Step 3: if the values of both node’s exponent is same add the coefficients

and then copy the added value with node to the result.

Step 4: Print the resultant node.

Tirthankar Pal
MBA from IIT Kharagpur with GATE, GMAT, IIT Kharagpur Written Test, and Interview
2 year PGDM (E-Business) from Welingkar, Mumbai
4 years of Bachelor of Science (Hons) in Computer Science from the National Institute of Electronics and Information Technology
Google and Hubspot Certification
Brain Bench Certification in C++, VC++, Data Structure and Project Management
10 years of Experience in Software Development out of that 6 years 8 months in Wipro
Selected in Six World Class UK Universities:-
King's College London, Durham University, University of Exeter, University of Sheffield, University of Newcastle, University of Leeds

Data Structures and Algorithms (Asymptotic Analysis of Algorithms) - Tirthankar Pal - MBA from IIT Kharagpur, GATE, GMAT, IIT Written Test, Interview were a part of MBA Entrance, B.S. in Computer Science from NIELIT

Asymptotic analysis of an algorithm refers to defining the mathematical boundation/framing of its run-time performance. Using asymptotic analysis, we can very well conclude the best case, average case, and worst case scenario of an algorithm.

Asymptotic analysis is input bound i.e., if there's no input to the algorithm, it is concluded to work in a constant time. Other than the "input" all other factors are considered constant.

Asymptotic analysis refers to computing the running time of any operation in mathematical units of computation. For example, the running time of one operation is computed as f(n) and may be for another operation it is computed as g(n²). This means the first operation running time will increase linearly with the increase in n and the running time of the second operation will increase exponentially when n increases. Similarly, the running time of both operations will be nearly the same if n is significantly small.

Usually, the time required by an algorithm falls under three types −

·         Best Case − Minimum time required for program execution.

·         Average Case − Average time required for program execution.

·         Worst Case − Maximum time required for program execution.

Asymptotic Notations

Following are the commonly used asymptotic notations to calculate the running time complexity of an algorithm.

·         Ο Notation

·         Ω Notation

·         θ Notation

Big Oh Notation, Ο

The notation Ο(n) is the formal way to express the upper bound of an algorithm's running time. It measures the worst case time complexity or the longest amount of time an algorithm can possibly take to complete.

For example, for a function f(n)

Ο(f(n)) = { g(n) : there exists c > 0 and n₀ such that f(n) ≤ c.g(n) for all n > n₀. }

Omega Notation, Ω

The notation Ω(n) is the formal way to express the lower bound of an algorithm's running time. It measures the best case time complexity or the best amount of time an algorithm can possibly take to complete.

For example, for a function f(n)

Ω(f(n)) ≥ { g(n) : there exists c > 0 and n₀ such that g(n) ≤ c.f(n) for all n > n₀. }

Theta Notation, θ

The notation θ(n) is the formal way to express both the lower bound and the upper bound of an algorithm's running time. It is represented as follows −

θ(f(n)) = { g(n) if and only if g(n) =  Ο(f(n)) and g(n) = Ω(f(n)) for all n > n₀. }

Common Asymptotic Notations

Following is a list of some common asymptotic notations −

constant	−	Ο(1)
logarithmic	−	Ο(log n)
linear	−	Ο(n)
n log n	−	Ο(n log n)
quadratic	−	Ο(n2)
cubic	−	Ο(n3)
polynomial	−	nΟ(1)
exponential	−	2Ο(n)

Tirthankar Pal

MBA from IIT Kharagpur with GATE, GMAT, IIT Kharagpur Written Test, and Interview

2 year PGDM (E-Business) from Welingkar, Mumbai

4 years of Bachelor of Science (Hons) in Computer Science from the National Institute of Electronics and Information Technology

Google and Hubspot Certification

Brain Bench Certification in C++, VC++, Data Structure and Project Management

10 years of Experience in Software Development out of that 6 years 8 months in Wipro

Selected in Six World Class UK Universities:-

King's College London, Durham University, University of Exeter, University of Sheffield, University of Newcastle, University of Leeds