Unit - I (Introduction to data structures)

Q.1 Explain following Data Structures with examples for each.

i) Linear & Non-linear ii) Persistent & Epheneral

Ans:
Examples: Linked List Concatenation
As shown in above fig. We can perform further operations on previous
versions of linked lists after the concatenation.

Example: inserting new element in array, stack, queue after this

operation previous version is updated and we can perform further
operations on the newest version on data structures.

Q. 2 In a matrix of order 5 × 5, having base address 6500, for storing

characters, compute the address of element of stored at 4th row and 3rd

column. (Say if the array is alpha [5][5], then find the address of alpha [4][3]).

Use column-major method.

Q. 3) Define the following terms with example

i) Data

ii) Data Object

iii) Data Type

Answer:
Data Type: The data type is the form of a variable to which a value can be
assigned. It defines that the particular variable will assign the values of the
given data type only. It can hold value but not data. Therefore, it is dataless.

In the case of data types, the value of data is not stored because it only
represents the type of data that can be stored. Data type examples are int, float,
double, etc.

Q.4 ) Write different types of data structures. Give one example of each type.

What is Data Structure:

A data structure is a storage that is used to store and organize data. It
is a way of arranging data on a computer so that it can be accessed and
updated efficiently

Arrays:
An array is a linear data structure and it is a collection of items stored
at contiguous memory locations. The idea is to store multiple items of
the same type together in one place. It allows the processing of a large
amount of data in a relatively short period. The first element of the
array is indexed by a subscript of 0. There are different operations
possible in an array, like Searching, Sorting, Inserting, Traversing,
Reversing, and Deleting.
inked list:
A linked list is a linear data structure in which elements are not stored at
contiguous memory locations. The elements in a linked list are linked
using pointers as shown in the below image:

Types of linked lists:

● Singly-linked list

● Doubly linked list

● Circular linked list

● Doubly circular linked list

Stack:
Stack is a linear data structure that follows a particular order in which the
operations are performed. The order is LIFO(Last in first out). Entering and
retrieving data is possible from only one end. The entering and retrieving
of data is also called push and pop operation in a stack. There are different
operations possible in a stack like reversing a stack using recursion,
Sorting, Deleting the middle element of a stack, etc.

Queue:
Queue is a linear data structure that follows a particular order in which the
operations are performed. The order is First In First Out(FIFO) i.e. the data
item stored first will be accessed first. In this, entering and retrieving data
is not done from only one end. An example of a queue is any queue of
consumers for a resource where the consumer that came first is served
first. Different operations are performed on a Queue like Reversing a
Queue (with or without using recursion), Reversing the first K elements of
a Queue, etc. A few basic operations performed In Queue are enqueue,
dequeue, front, rear, etc.
Tree:
A tree is a non-linear and hierarchical data structure where the elements
are arranged in a tree-like structure. In a tree, the topmost node is called
the root node. Each node contains some data, and data can be of any type.
It consists of a central node, structural nodes, and sub-nodes which are
connected via edges. Different tree data structures allow quicker and
easier access to the data as it is a non-linear data structure. A tree has
various terminologies like Node, Root, Edge, Height of a tree, Degree of a
tree, etc.

Graph:
A graph is a non-linear data structure that consists of vertices (or nodes)
and edges. It consists of a finite set of vertices and set of edges that
connect a pair of nodes. The graph is used to solve the most challenging
and complex programming problems. It has different terminologies which
are Path, Degree, Adjacent vertices, Connected components, etc.

Q. 5) What is the frequency count? Explain its importance in analysis of algorithm.

Find time complexity of an algorithm to find union of two sets of length m & n.
Answer:
Frequency count is a method used to determine the number of times basic
operations are executed in an algorithm. It's a critical aspect of analyzing the
efficiency of an algorithm because it helps estimate the algorithm's time complexity.
By counting how often operations like comparisons, assignments, or other basic
operations occur, we can derive the overall performance characteristics and
scalability of the algorithm.

Time Complexity of Union of Two Sets

To analyze the time complexity of an algorithm that finds the union of two sets of
length m and n, we need to consider a common approach and its complexity. Here,
I'll outline a typical approach and analyze its complexity:

Suppose A is set of m elements and B is set of n elements and C is set where union
on A and B elements are stored.

To copy m elements of A complexity is O(m) and to copy n elements of B complexity

is O(n)

for(i=0;i<m;i++)

{
c[i]=a[i];

for(j=0;j<n;j++)

c[i]=b[j];

i++;

By using to loops we union two sets of elements in C set by complexity O(m+n).

Q. 6) State the advantages of linked list over array.

Answer:

Linked lists and arrays are both fundamental data structures with distinct
advantages and use cases. Here are some key advantages of linked lists over
arrays:

1. Dynamic Size

● Linked List: Can grow or shrink in size dynamically as elements are

added or removed. This flexibility is particularly useful when the number
of elements is not known in advance or changes frequently.
● Array: Typically has a fixed size. Resizing an array usually involves
creating a new array and copying elements, which can be costly in
terms of time and memory.

2. Efficient Insertions/Deletions

● Linked List: Insertion and deletion operations can be performed in

constant time O(1)O(1)O(1) if the position is known (e.g., inserting
before or after a given node). This is because you only need to adjust
pointers without shifting elements.
● Array: Insertion or deletion of elements (except at the end) requires
shifting elements, which can be O(n)O(n)O(n) in the worst case, where
nnn is the number of elements.

3. Memory Utilization
 ● Linked List: Allocates memory dynamically as needed for each node,
which can be more efficient in scenarios with varying amounts of data.
● Array: Allocates a contiguous block of memory, which can lead to
wasted space if the array is not fully utilized, or may require expensive
resizing operations if the array needs to grow beyond its initial capacity.

4. Ease of Implementation for Certain Operations

● Linked List: Some operations, like implementing a stack or queue, can

be more straightforward using a linked list. For example, adding or
removing elements from the front or back of a linked list can be done
efficiently without shifting elements.
● Array: Implementing certain dynamic operations can be cumbersome,
especially when frequent resizing is required.

5. No Fixed Capacity Constraints

● Linked List: Can theoretically grow as large as the system’s memory

allows, as long as there’s sufficient space to allocate nodes.
● Array: Has a maximum capacity determined by the initial size or
allocated space, and resizing involves overhead and potential
performance issues.

Unit- II (Searching and Sorting)

Q. 1) Explain with example difference between linear search & binary search

Linear search and binary search are both algorithms used to find a target
value in a collection of elements. They differ significantly in their approach,
efficiency, and use cases. Here’s an explanation of each with examples to
illustrate the differences:

Linear Search

Linear Search is a straightforward search algorithm that checks each element

in the collection sequentially until it finds the target value or reaches the end
of the collection.

Steps:

1. Start from the first element.

2. Compare each element with the target value.
3. If a match is found, return the index of the target element.
4. If no match is found by the end of the collection, return an indicator that
the target is not present.
Example: Consider a list of integers: [3, 7, 1, 9, 5] and you want to find
the value 9.

● Start: Check the first element 3. It’s not 9.

● Next: Check the second element 7. It’s not 9.
● Next: Check the third element 1. It’s not 9.
● Next: Check the fourth element 9. It matches the target!

Result: The index of 9 is 3.

Time Complexity: O(n) in the worst case, where n is the number of elements.
This is because you might need to check each element in the list.

Binary Search

Binary Search is an efficient search algorithm that requires the collection to be

sorted. It works by repeatedly dividing the search interval in half.

Steps:

1. Start: Begin with the entire collection and find the middle element.
2. Compare: Compare the middle element with the target value.
3. Narrow Down:
○ If the target is equal to the middle element, return the index.
○ If the target is less than the middle element, narrow the search to
the lower half.
○ If the target is greater than the middle element, narrow the search
to the upper half.
4. Repeat: Continue this process until you either find the target or the
interval is empty.

Example: Consider a sorted list of integers: [1, 3, 5, 7, 9] and you want

to find the value 9.

● Start: The entire list is [1, 3, 5, 7, 9]. The middle element is 5.

● Compare: 9 is greater than 5, so search the right half: [7, 9].
● New Interval: The new middle element is 7.
● Compare: 9 is greater than 7, so search the right half: [9].
● Final: The middle element is 9. It matches the target!

Result: The index of 9 is 4.

Time Complexity: O(log n) in the worst case, where n is the number of

elements. This is because each comparison halves the search space.
Key Differences

1. Efficiency:
○ Linear Search: Less efficient with a time complexity of O(n). It can
be used on unsorted data.
○ Binary Search: More efficient with a time complexity of O(log n),
but requires sorted data.
2. Use Cases:
○ Linear Search: Suitable for small or unsorted lists, or when
sorting the list is impractical.
○ Binary Search: Suitable for large, sorted lists where quick search
performance is necessary.
3. Preconditions:
○ Linear Search: No special preconditions (works on unsorted
data).
○ Binary Search: Requires that the data be sorted before the search.

Q. 2) Sort following list using bubble sort, show the output of each pass.
10, 5, 4, 18, 17, 1, 2.

Answer:

Bubble sort is a simple sorting algorithm that repeatedly steps through the list,
compares adjacent elements, and swaps them if they are in the wrong order.
The pass through the list is repeated until the list is sorted.

Let's sort the list [10, 5, 4, 18, 17, 1, 2] using bubble sort and show
the output of each pass.

Initial List
[10, 5, 4, 18, 17, 1, 2]

Bubble Sort Steps

Pass 1:

● Compare 10 and 5, swap: [5, 10, 4, 18, 17, 1, 2]

● Compare 10 and 4, swap: [5, 4, 10, 18, 17, 1, 2]
● Compare 10 and 18, no swap: [5, 4, 10, 18, 17, 1, 2]
● Compare 18 and 17, swap: [5, 4, 10, 17, 18, 1, 2]
● Compare 18 and 1, swap: [5, 4, 10, 17, 1, 18, 2]
● Compare 18 and 2, swap: [5, 4, 10, 17, 1, 2, 18]
Pass 2:

● Compare 5 and 4, swap: [4, 5, 10, 17, 1, 2, 18]

● Compare 5 and 10, no swap: [4, 5, 10, 17, 1, 2, 18]
● Compare 10 and 17, no swap: [4, 5, 10, 17, 1, 2, 18]
● Compare 17 and 1, swap: [4, 5, 10, 1, 17, 2, 18]
● Compare 17 and 2, swap: [4, 5, 10, 1, 2, 17, 18]

Pass 3:

● Compare 4 and 5, no swap: [4, 5, 10, 1, 2, 17, 18]

● Compare 5 and 10, no swap: [4, 5, 10, 1, 2, 17, 18]
● Compare 10 and 1, swap: [4, 5, 1, 10, 2, 17, 18]
● Compare 10 and 2, swap: [4, 5, 1, 2, 10, 17, 18]

Pass 4:

● Compare 4 and 5, no swap: [4, 5, 1, 2, 10, 17, 18]

● Compare 5 and 1, swap: [4, 1, 5, 2, 10, 17, 18]
● Compare 5 and 2, swap: [4, 1, 2, 5, 10, 17, 18]

Pass 5:

● Compare 4 and 1, swap: [1, 4, 2, 5, 10, 17, 18]

● Compare 4 and 2, swap: [1, 2, 4, 5, 10, 17, 18]

Pass 6:

● Compare 1 and 2, no swap: [1, 2, 4, 5, 10, 17, 18]

After Pass 6, no swaps are needed, and the list is sorted.

Final Sorted List

csharp
Copy code
[1, 2, 4, 5, 10, 17, 18]

Summary of Each Pass

1. Pass 1: [5, 4, 10, 17, 1, 2, 18]

2. Pass 2: [4, 5, 10, 1, 2, 17, 18]
3. Pass 3: [4, 5, 1, 2, 10, 17, 18]
 4. Pass 4: [4, 1, 2, 5, 10, 17, 18]
5. Pass 5: [1, 4, 2, 5, 10, 17, 18]
6. Pass 6: [1, 2, 4, 5, 10, 17, 18]

The list is fully sorted after 6 passes, which corresponds to the length of the
list minus one.

Q. 3) Write the time complexities of the following sorting algorithms.

i) Insertion sort ii) Shell sort

Answer:

i) Insertion Sort

Insertion Sort is a simple and intuitive sorting algorithm that builds the final
sorted array one item at a time. It is efficient for small data sets or nearly
sorted data but can be less efficient for larger lists.

● Best Case Time Complexity: O(n)

○ Occurs when the list is already sorted. Each element only needs
to be compared once with its predecessor.
● Average Case Time Complexity: O(n^2)
○ Occurs with random order data. Each element, on average,
requires comparisons and shifts for half of the already sorted
elements.
● Worst Case Time Complexity: O(n^2)
○ Occurs when the list is sorted in reverse order. Every element
requires comparisons and shifts for all previously sorted
elements.
● Space Complexity: O(1)
○ Insertion sort is an in-place sorting algorithm, meaning it requires
a constant amount of additional space beyond the input list.

ii) Shell Sort

Shell Sort is an improvement on Insertion Sort that allows the exchange of

items that are far apart. It first sorts elements at a specific gap, reducing the
gap over time until the list is sorted with a final Insertion Sort pass.

● Best Case Time Complexity:

○ The best case time complexity can vary significantly depending
on the gap sequence used. For some sequences,
○ it can be O(nlog n). For the original sequence proposed by Shell,
it can be O(n \log^2 n).
● Average Case Time Complexity:
 ○ For common gap sequences like the Shell's original sequence, the
average case time complexity is generally O(n^{3/2}).
● Worst Case Time Complexity:
○ For the original sequence proposed by Shell, the worst case time
complexity is O(n^2).
○ Space Complexity: O(1)
○ Like Insertion Sort, Shell Sort is an in-place sorting algorithm, so
it requires a constant amount of extra space.

Q. 4) Enlist and explain characteristics of sorting algorithms

Answer:

Sorting algorithms vary in terms of time complexity, stability,

adaptability, and memory usage. Understanding these
characteristics is crucial for selecting the right algorithm for a
specific task:

1. Time Complexity: Sorting algorithms have different time

complexities. Some algorithms, like Bubble Sort and
Selection Sort, have O(n^2) time complexity, making them
inefficient for large datasets. In contrast, Merge Sort and
Quick Sort have an average-case time complexity of O(n
log n), making them suitable for larger datasets.
2. Stability: Stability refers to the ability of an algorithm to
preserve the relative order of equal elements. Stable
sorting algorithms ensure that elements with the same
key value remain in the same order as they appeared in
the original list.
3. Adaptability: Adaptive sorting algorithms perform better
on partially sorted data. For example, Insertion Sort is
adaptive, as it becomes more efficient as the input data
becomes closer to being sorted.
4. Memory Usage: Sorting algorithms can be categorized as
in-place or not in-place. In-place algorithms use a constant
amount of additional memory, making them memory-efficient,
while others may require additional memory for temporary
storage.

Real-World Applications

Sorting algorithms are utilized in various domains and

applications:

1. Databases: Sorting plays a critical role in database

management systems for indexing and querying data
efficiently.
2. Search Algorithms: Sorting algorithms are used as a
preprocessing step in many search algorithms, such as
binary search and interpolation search.
3. Multimedia Applications: Sorting algorithms help
organize and retrieve multimedia data, such as images,
audio, and video files.
4. E-commerce: Online marketplaces rely on sorting
algorithms to display search results, products, and
reviews in a user-friendly and efficient manner.
5. Social Media: Social media platforms use sorting
algorithms to display posts, comments, and messages in
a chronological or relevance-based order

Q. 5) Sort the following list using merge sort 4 38, 27, 43, 3, 9, 82, 11, 10

Answer: following shows how the merge sort and merge function
call gets called:
Step 1: Divide

First, we divide the list into two halves until we have individual
elements:

1. Initial list: 4,38,27,43,3,9,82,114, 38, 27, 43, 3, 9, 82,

114,38,27,43,3,9,82,11
○ Divide into: 4,38,27,434, 38, 27, 434,38,27,43 and
3,9,82,113, 9, 82, 113,9,82,11
2. Divide 4,38,27,434, 38, 27, 434,38,27,43:
○ Divide into: 4,384, 384,38 and 27,4327, 4327,43
3. Divide 4,384, 384,38:
○ Divide into: 444 and 383838
4. Divide 27,4327, 4327,43:
○ Divide into: 272727 and 434343
5. Divide 3,9,82,113, 9, 82, 113,9,82,11:
○ Divide into: 3,93, 93,9 and 82,1182, 1182,11
6. Divide 3,93, 93,9:
○ Divide into: 333 and 999
 7. Divide 82,1182, 1182,11:
○ Divide into: 828282 and 111111

Step 2: Conquer

Next, sort the individual elements (which are already sorted by

themselves) and merge them back together:

1. Merge 444 and 383838:

○ Result: 4,384, 384,38
2. Merge 272727 and 434343:
○ Result: 27,4327, 4327,43
3. Merge 333 and 999:
○ Result: 3,93, 93,9
4. Merge 828282 and 111111:
○ Result: 11,8211, 8211,82
5. Merge 4,384, 384,38 and 27,4327, 4327,43:
○ Merge 444 and 27,4327, 4327,43: Result 4,27,434, 27,
434,27,43
○ Merge 383838 into 4,27,434, 27, 434,27,43: Result
4,27,38,434, 27, 38, 434,27,38,43
6. Merge 3,93, 93,9 and 11,8211, 8211,82:
○ Merge 333 and 11,8211, 8211,82: Result 3,11,823, 11,
823,11,82
○ Merge 999 into 3,11,823, 11, 823,11,82: Result
3,9,11,823, 9, 11, 823,9,11,82
7. Merge 4,27,38,434, 27, 38, 434,27,38,43 and 3,9,11,823, 9,
11, 823,9,11,82:
○ Start with 333: Result 333
○ Continue with 444: Result 3,43, 43,4
○ Continue with 999: Result 3,4,93, 4, 93,4,9
○ Continue with 111111: Result 3,4,9,113, 4, 9, 113,4,9,11
○ Continue with 272727: Result 3,4,9,11,273, 4, 9, 11,
273,4,9,11,27
 ○ Continue with 383838: Result 3,4,9,11,27,383, 4, 9, 11,
27, 383,4,9,11,27,38
○ Continue with 434343: Result 3,4,9,11,27,38,433, 4, 9,
11, 27, 38, 433,4,9,11,27,38,43
○ Finally, add 828282: Result 3,4,9,11,27,38,43,823, 4, 9,
11, 27, 38, 43, 823,4,9,11,27,38,43,82

Final Sorted List

3,4,9,11,27,38,43,823, 4, 9, 11, 27, 38, 43, 823,4,9,11,27,38,43,82

Q. 6) Write pseudo code for fibonacci search.

Answer:
Function FibonacciSearch(array, target):
n = length of array
fibM2 = 0 // Fibonacci(i-2)
fibM1 = 1 // Fibonacci(i-1)
fibM = fibM1 + fibM2 // Fibonacci(i)

// Find the smallest Fibonacci number greater than or equal to n

while (fibM < n):
fibM2 = fibM1
fibM1 = fibM
fibM = fibM1 + fibM2

// Mark the eliminated range from the front

offset = -1

while (fibM > 1):

// Calculate the index to compare
i = min(offset + fibM2, n-1)

// Compare target with the element at index i

if (array[i] < target):
// Target is in the right subarray
fibM = fibM1
fibM1 = fibM2
fibM2 = fibM - fibM1
offset = i
 else if (array[i] > target):
// Target is in the left subarray
fibM = fibM2
fibM1 = fibM1 - fibM2
fibM2 = fibM - fibM1

else:
// Target found
return i

// Compare the last element with target

if (fibM1 and offset + 1 < n and array[offset + 1] == target):
return offset + 1

// Target not found

return -1