Data Structures and Algorithms

Practice set (with solutions)-Unit 1+ Unit 3

Q1. Write short notes on: -
(i) Data Structures and its types :- The data structure name indicates itself that organizing the
data in memory. The arrangement of data in a sequential manner is known as a linear data
structure. The data structures used for this purpose are Arrays, Linked list, Stacks, and
Queues. In these data structures, one element is connected to only one another element in
a linear form. This data structure does not form a sequence i.e. each item or element is
connected with two or more other items in a non-linear arrangement. The data elements
are not arranged in sequential structure.

(ii) Arrays:- An array is a collection of similar data elements stored at contiguous memory
locations. It is the simplest data structure where each data element can be accessed
directly by only using its index number.For instance, if we want to store the marks scored
by a student in 5 subjects, then there’s no need to define individual variables for each
subject. Rather, we can define an array that will store the data elements at contiguous
memory locations.
(iii) How can the efficiency of an algorithm be calculated :- Efficiency of an algorithm can be

observed with Asymptotic notations. These are the mathematical notations used to

describe the running time of an algorithm when the input tends towards a particular value

or a limiting value. There are mainly three asymptotic notations:

 Big-O notation:- Big-O notation represents the upper bound of the running time of an

algorithm. Thus, it gives the worst-case complexity of an algorithm.

 Omega notation:- Omega notation represents the lower bound of the running time of an

algorithm. Thus, it provides the best case complexity of an algorithm.

 Theta notation:- Theta notation encloses the function from above and below. Since it

represents the upper and the lower bound of the running time of an algorithm, it is used for

analyzing the average-case complexity of an algorithm.

(iv) Time and space complexity of an algorithm :- While analyzing an algorithm, we mostly
consider time complexity and space complexity. Time complexity of an algorithm
quantifies the amount of time taken by an algorithm to run as a function of the length of
the input. Similarly, Space complexity of an algorithm quantifies the amount of space or
memory taken by an algorithm to run as a function of the length of the input. Time and
space complexity depends on lots of things like hardware, operating system, processors,
etc. Order of growth is how the time of execution depends on the length of the input. In
the above example, it is clearly evident that the time of execution quadratically depends
on the length of the array. Order of growth will help to compute the running time with
ease.

(v) Abstract Data types :- Abstract Data type (ADT) is a type (or class) for objects whose
behavior is defined by a set of values and a set of operations. The definition of ADT only
mentions what operations are to be performed but not how these operations will be
implemented. It does not specify how data will be organized in memory and what
algorithms will be used for implementing the operations. It is called “abstract” because it
gives an implementation-independent view. There can be different ways to implement an
ADT, for example, the List ADT can be implemented using arrays, or singly linked list or
doubly linked list. Similarly, stack ADT and Queue ADT can be implemented using
arrays or linked lists.

(vi) Sparce Matrix :- Sparse matrices are those matrices that have the majority of their
elements equal to zero. In other words, the sparse matrix can be defined as the matrix that
has a greater number of zero elements than the non-zero elements. In 2D array
representation of sparse matrix, there are three fields used that are named as -

o Row - It is the index of a row where a non-zero element is located in the matrix.
o Column - It is the index of the column where a non-zero element is located in the matrix.
 o Value - It is the value of the non-zero element that is located at the index (row, column).

(vii) Linked List and its types:- A linked list is a linear collection of data element, called
nodes. Linear order is given by pointers. Each node is divided into two or more parts.
There are4 types of Linked list
 Linear Linked list
 Doubly Linked List
 Circular Linked List
 Header Linked List
(viii) Operations that can be performed on a Linked list.

Q2. Write the algorithm to implement sorting techniques (also write programs using algorithm):-
1.) Bubble sort:- (watch shared videos for better understanding)

begin BubbleSort(list)
for n-1 passes
for all elements of list
if list[i] > list[i+1]
swap(list[i], list[i+1])
end if
end for
return list
end BubbleSort

Example:-

Bubble sort starts with very first two elements, comparing them to check which one is greater.

In this case, value 33 is greater than 14, so it is already in sorted locations. Next, we compare 33 with
27.

We find that 27 is smaller than 33 and these two values must be swapped.

The new array should look like this −

 Next we compare 33 and 35. We find that both are in already sorted positions.

Then we move to the next two values, 35 and 10.

We know then that 10 is smaller 35. Hence they are not sorted.

We swap these values. We find that we have reached the end of the array. After one iteration, the
array should look like this −

To be precise, we are now showing how an array should look like after each iteration. After the
second iteration, it should look like this −

Notice that after each iteration, at least one value moves at the end.

And when there's no swap required, bubble sorts learns that an array is completely sorted.

2.) Selection sort:- (watch shared videos for better understanding):- The selection sort algorithm sorts
an array by repeatedly finding the minimum element (considering ascending order) from the unsorted
part and putting it at the beginning. Lets consider the following array as an example: arr[] = {64, 25,
12, 22, 11}
First pass:
 For the first position in the sorted array, the whole array is traversed from index 0 to 4
sequentially. The first position where 64 is stored presently, after traversing whole array it
is clear that 11 is the lowest value.

64 25 12 22 11
  Thus, replace 64 with 11. After one iteration 11, which happens to be the least value in
the array, tends to appear in the first position of the sorted list.

11 25 12 22 64

Second Pass:
 For the second position, where 25 is present, again traverse the rest of the array in a
sequential manner.

11 25 12 22 64

 After traversing, we found that 12 is the second lowest value in the array and it should
appear at the second place in the array, thus swap these values.

11 12 25 22 64

Third Pass:
 Now, for third place, where 25 is present again traverse the rest of the array and find the
third least value present in the array.

11 12 25 22 64

 While traversing, 22 came out to be the third least value and it should appear at the third
place in the array, thus swap 22 with element present at third position.

11 12 22 25 64

Fourth pass:
 Similarly, for fourth position traverse the rest of the array and find the fourth least
element in the array As 25 is the 4th lowest value hence, it will place at the fourth
position.

11 12 22 25 64

Fifth Pass:
 At last the largest value present in the array automatically get placed at the last position in
the array.The resulted array is the sorted array.
11 12 22 25 64

procedure selection sort

list : array of items
n : size of list

for i = 1 to n - 1
{
min = i
/* check the element to be minimum */
for j = i+1 to n
if list[j] < list[min] then
min = j;
end if
end for
/* swap the minimum element with the current element*/
 if indexMin != i then
swap list[min] and list[i]
end if
end for
end procedure

(iii) Insertion sort:- (watch shared videos for better understanding)

void insertionSort(int arr[], int n)

{
int i, key, j;
for (i = 1; i < n; i++) {
key = arr[i];
j = i - 1;

/* Move elements of arr[0..i-1], that are

greater than key, to one position ahead
of their current position */
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}

Q3. Diiferentiate between Linear search and Binary search. Write the pseudocode for binary
search.
 Linear search Binary Search

In linear search input data need not to be in In binary search input data need to be in sorted
sorted. order.

It is also called sequential search. It is also called half-interval search.

The time complexity of linear search O(n). The time complexity of binary search O(log n).

Multidimensional array can be used. Only single dimensional array is used.

Linear search performs equality comparisons Binary search performs ordering comparisons

Pseudocode for Binary search

Binary_Search(a, lower_bound, upper_bound, val) // 'a' is the given array, 'lower_bound' is the index
of the first array element, 'upper_bound' is the index of the last array element, 'val' is the value to sear
ch
Step 1: set beg = lower_bound, end = upper_bound, pos = - 1
Step 2: repeat steps 3 and 4 while beg <=end
Step 3: set mid = (beg + end)/2
Step 4: if a[mid] = val
set pos = mid
print pos
go to step 6
else if a[mid] > val
set end = mid - 1
else
set beg = mid + 1
[end of if]
[end of loop]
Step 5: if pos = -1
print "value is not present in the array"
[end of if]
Step 6: exit

Write the code using algorithm and make the dry run for the same

There are two methods to implement the binary search algorithm -

o Iterative method
 o Recursive method

The recursive method of binary search follows the divide and conquer approach.

Q6. Difference between Array and Linked List.

Q7. What is hashing? Give the characteristics of hash function. Explain collision resolution using
hashing techniques.