Subject : Data Structure and Algorithm

Name : Mubashir Hussain

Roll no : 22-21CS39
Department : Computer System Engineering
Submitted to : Dr.Sammar zai
QI. Write down the algorithm and complexity for deletion.

Ans. Deletion into Linear Array

Algo: Delete (LA, N, ITEM, k)

Here LA is a linear array with N element and K is a Positive integer such that K<=N. This Algorithm
deletes the Kth element from LA.

STEP#1

Start.

STEP#2

Set ITEM:=A[K]

STEP#3

[Initialize counter variable] Set J:=k

STEP#4

[Using Loop] Repeat step 5&6 while J<N-1

STEP#5

[Shifting element ] Set LA[J]:=LA[J+1]

STEP#6

Increment counter Variable [ ] Set J:=J+1

[End of loop]

[Reset size of the Array] Set N:N-1

SETP#8

Stop
TIME COMPLEXITY FOR DELETION ALGORITHM

Deleting from a linear array takes 0(1) time if you know the index, O(n) in the worst case if searching by
value, and O(n) when shifting elements (beginning/middle).

Q2. which Sorting technique is best among Bubble, insertion and selection, and why?

Ans. The best sorting technique among Bubble, Insertion, and Selection sort depends on the specific
scenario and data characteristics. In general:

. Insertion Sort: It has a best-case time complexity of O(n) when the list is already sorted or nearly
sorted. However, its average and worst-case time complexity is O(n^2), making it less efficient for larger
datasets due to the need for multiple comparisons and swaps.

. Selection Sort: This algorithm has a time complexity of O(n^2) in all cases, including the best, average,
and worst-case scenarios. While it's simple to implement and works well for small datasets, it's generally
less efficient compared to Insertion Sort, especially for larger datasets.

Bubble Sort: Similar to Insertion Sort, Bubble Sort also has a best-case time complexity of O(n) when the
list is already sorted. However, its average and worst-case time complexity is O(n^2), which makes it less
efficient compared to both Insertion and Selection sorts, particularly for larger datasets.

So, for small datasets or nearly sorted lists, Insertion Sort tends to perform slightly better due to its
simplicity and lower overhead, as it has a linear best-case time complexity.

Q4. Apply selection sort on any data of your choice.

10

Sorted sub list

Empty

Unsorted sub list

In selection sort we select smallest element from unsorted sub list of array and swap thar element with
starting element in unsorted sub list of array up to the array was sorted.

Sorted sub list

PASS#1

10

Unsorted sub list

PASS#2

Sorted sub list

10

Unsorted sub list

Sorted sub list

PASS#3

10

Unsorted sub list

Sorted sub list

PASS#4

10

Unsorted sub list

Sorted sub list

PASS#5

10

Q5. Apply insertion sort on any data of your choice.

Sorted sub list

10

Unsorted sub list

In insertion Sort we store starting element in we compare element stored in variable to all the elements
in Sorted sub list.

If element of sorted sub list is by one to right and Put Stored element in variable to that space. We
repeated these steps up to the Sorted.

Sorted sub list

PASS#1

Unsorted sub list

10

Unsorted sub list

Sorted sub list

PASS#2
12334
PASS#3

10

Unsorted sub list

PASS#4

Sorted sub list

10
2

Sorted sub list

Unsorted sub list

In this whole process we take one value from unsorted sub list and insert it in sorted sub list so, it is
called insertion sort.

PASS#5

10

Unsorted sub list

Q6. Sort out the letters in your name.

Ans. I apply selection sorting in my name which is given below:

Sorted sub list

Empty

Sorted sub list

Unsorted sub list

PASS#1

Unsorted sub list

Sorted sub list

PASS#2

Unsorted sub list

PASS#3

Sorted sub list

Sorted sub list

Unsorted sub list

PASS#4

: Unsorted sub list

Sorted sub list

PASS#5

Remaining last is only one so it is considered as sorted. Above is the sorting on my name.

Q7. How Linked list is efficient as compared to Array.

Ans.

Here's a breakdown of how linked lists can be

1. Insertions and Deletions:

Linked lists: Highly efficient adjust a few pointers,

only need to
need to be

Arrays: Costly for

shifted to make to the number of

elements

2. Dynamic Size:

needed, allocating memory for new

Resizing an array involves creating a new

can be inefficient for frequent size changes.

3. Data:

Linked lists: Only allocate memory for actual elements, avoiding wasted space for empty or unused
positions.

Arrays: Occupy a contiguous block of memory, even for sparse data with many empty elements,
potentially leading to memory waste.

4. Implementing Certain Data Structures:

: Linked lists: More natural for representing certain data structures like stacks, queues, graphs, and
trees, where elements have logical relationships rather than being ordered. by index.

Arrays: Less suitable for these structures due to their fixed size and sequential access nature.

When to Choose Linked Lists:

Frequent insertions/deletions at any position

Dynamic size requirements that are uncertain or change often

Sparse data where memory efficiency is crucial

Implementing specific data structures like stacks, queues, graphs, or trees

Remember: Arrays still excel in random access (reaching any clement directly by index) and cache
performance (due to contiguous memory blocks). Choose the data structure that best suits your specific
needs based on these performance characteristics and the operations you'll perform most frequently.

Q8. Write algorithm for linear search in a linked list.

Ans:

Algo: LINEARSEARCH (INFO, LINK, START ITEM, LOC)

This algo finds the location LOC of the node where ITEM first appears in list or set LOC:=NULL

1. Set PTR: START

2. Repeat step 3 while PTR NULL

3. If ITEM-INFO PTR), THEN Set LOC-PTR & Exit

Else:

Set PTR-LINK[PTR] [Now PTR points to next node] [end of step 2 loop)

4.[search unsuccessful?] LOC-NULL

5. exit

Q9.Write algorithm for deletion of node in a linked list

Algo: DEL (INFO, LINK, START, AVAIL, LOC, LOCP)

This algo deletes the node N with location LOC. LOCP is the location of the node which precedes Nor,
when N is first Node, LOCP = NULL

1. IF LOCPNULL, then: Set START LINK [START] [Delete first node]

else:

set LINK [LOCP] LINK (LOC] [Delete node N] [End of if structure)

2. [Return deleted Nde to AVAIL] Set LINK [LOG]-AVAIL Set AVAIL LOC

3. Exit

Q10. Complexity of Insertion and deletion in Linked list

Ans: Insertion:

Average Case: O(1) (constant time)

This is because you only need to update a few pointers to insert a new node, regardless of the list's size.

Worst Case: (1) (still constant time)

Even in the worst case, such as inserting at the beginning, you only need to adjust two pointers (head
and first node).

Deletion:

Average Case: O(1) (constant time)

Similar to insertion, deleting a node involves updating a few pointers, taking constant time on average.

Worst Case: 0(1) (still constant time)

Even in the worst case, such as deleting the head node, you only need to update two pointers (head and
second node).

Key points:

Linked lists excel at insertions and deletions because they don't require shifting elements like arrays do.
 The constant time complexity for both operations makes them ideal for scenarios where frequent
insertions and deletions are expected.

This efficiency is due to their dynamic structure, where elements are linked using pointers rather than
being stored in contiguous memory like arrays.

Q11. Five applications of stack data structure.

Applications of stack:

The application of stack is given below:

1. Expression Evaluation: Stacks are employed in evaluating arithmetic expressions, especially in

converting infix to Postfix or Prefix notation, making it easier to Perform computations.

2. Undo Mechanisms: Many applications use Stacks to implement undo mechanisms. Each action
Performed is Pushed onto the stack, and undoing involves Popping actions off the Stack.

3. Backtracking Algorithms: Backtracking Algorithms are most used by Stack, where decisions need to be
revisited and alternatives explored.

4. Browser History: Stacks can be used to implement the back and used Forward Functionality in web
browsers, managing the use's navigation history

5. Task Scheduling: In operating Systems, Stacks are employed to manage task scheduling and track the
execution of Processes.

Q12. Write the algorithm for traversing of grounded header linked list and circular header linked list.

Algorithm for traversing of Grounded header linked list:

Let's list be a grounded list in memory. This algorithm traverses list applying an operation process to
each node of list.

1. [Initialize pointer variable] Set PTR: START.

2. Repeat steps 3 and 4 while PTR!-NULL.

3. Apply process to INFO[PTR].

4. Set PTR:-LINK[PTR].

5. Exit

Algorithm for traversing of Circular header list:

Let's list be a circular header list in memory. This algorithm traverses list applying an operation Process
to each node of list.

1. [Initialize the pointer variable] Set PTR:-LINK(START).

2. Repeat steps 3 and 4 while PTR! START.

3. Apply process to INFO[PTR].

4. Set PTR: LINK[PTR]

5. Exit

Q13. write down the benefits of header Linked list over Simple linked list.

Benefits of header Linked List

Header linked Lists have a distinct advantage header node. some benefits include.

1. Simplifies Operations:

The header node allows for and Header linked the header node a place the list is empty. 22C5107 is
used a header node.

deletion, as it

2. Empty List Handling:

serves as

3.With as more Linked list operations

separate logic to handle the First node in

List Can or manipulating the be Simpler to

Overall, header Linked lists enhance the clarity and simplicity of Linked list operations, especially when
compared to the complexity that can arise in a Simple Linked List.

Q14. Write down the traversing algorithm for 2-way Linked list in Forward direction.

Algorithm:

1. Set PTR:-START

2. Repeat steps 3 and 4 while PTR!=NULL.

3. Apply Process to INFO[PTR]

4. Set PTR: Fow[PTR].

5. Exist.

Q15. Write down the backward traversing algorithm for a 2-way linked list.

Algorithm:

1. Set PTR-End.

2. Repeat steps 3 and 4 while PTR!=NULL.

3. Apply Process to INFO[]

4. Set PTR Back[PTR].

5. Exist.

Q17. How to evaluate expression using Stack.

Evaluating expressions using a stack is a common technique, especially for arithmetic expressions in infix
notation. Here's a general algorithm to evaluate arithmetic expressions using a stack:

1. Initialize an empty stack to hold operands

2. Iterate through each character in the expression from left to right.

3. If the current character is an operand (a number), push it onto the stack.

4. If the current character is an operator (+), pop the top two operands from the stack, perform the
operation, and push the result back onto the stack.

5. Continue this process until the entire expression is evaluated.

6. At the end, the result will be the only element left on the stack.