Unit 1
[Link] is Data Structure ? Explain classification of it.
Ans:
1. Linear Data Structure: Data structure in which data elements are
arranged sequentially or linearly, where each element is attached to its
previous and next adjacent elements, is called a linear data structure.
Example: Array, Stack, Queue, Linked List, etc.
2. Static Data Structure: Static data structure has a fixed memory size. It
is easier to access the elements in a static data structure.
Example: array.
Array is a linear data structure that stores a collection of elements of
the same data type. Elements are allocated contiguous memory,
allowing for constant-time access. Each element has a
unique index number.
3. Dynamic Data Structure: In dynamic data structure, the size is not
fixed. It can be randomly updated during the runtime which may be
considered efficient concerning the memory (space) complexity of the
code.
Example: Queue, Stack, etc.
1). Stack is a linear data structure that follows the Last In, First Out
(LIFO) principle. Stacks play an important role in managing function
calls, memory, and are widely used in algorithms, web development,
and systems like compilers and browsers.
2). Queue is a linear data structure that follows the First In, First Out
(FIFO) principle. Queues play an important role in managing tasks or
data in order, scheduling and message handling systems
3).Linked list is a linear data structure that stores data in nodes, which
are connected by pointers. Unlike arrays, nodes of linked lists are not
stored in contiguous memory locations and can only be accessed
sequentially, starting from the head of list.
4. Non-Linear Data Structure: Data structures where data elements are
not placed sequentially or linearly are called non-linear data structures.
In a non-linear data structure, we can’t traverse all the elements in a
single run only.
Examples: Trees and Graphs.
1).Tree is a non-linear, hierarchical data structure consisting of
nodes connected by edges, with a top node called the root and nodes
having child nodes. It is widely used in file
systems, databases, decision-making algorithms, etc.
2). Graph is a non-linear data structure consisting of a finite set
of vertices(or nodes) and a set of edges(or links)that connect a pair of
nodes. Graphs are widely used to represent relationships between
entities.
Q.2. What are the Characteristics of an Algorithm?
Ans:
Clear and Unambiguous: The algorithm should be unambiguous.
Each of its steps should be clear in all aspects and must lead to only
one meaning.
Well-Defined Inputs: If an algorithm says to take inputs, it should be
well-defined inputs. It may or may not take input.
Well-Defined Outputs: The algorithm must clearly define what output
will be yielded and it should be well-defined as well. It should produce
at least 1 output.
Finite-ness: The algorithm must be finite, i.e. it should terminate after
a finite time.
Feasible: The algorithm must be simple, generic, and practical, such
that it can be executed with the available resources. It must not contain
some future technology or anything.
Language Independent: The Algorithm designed must be language-
independent, i.e. it must be just plain instructions that can be
implemented in any language, and yet the output will be the same, as
expected.
Input: An algorithm has zero or more inputs. Each that contains a
fundamental operator must accept zero or more inputs.
Output: An algorithm produces at least one output. Every instruction
that contains a fundamental operator must accept zero or more inputs.
Definiteness: All instructions in an algorithm must be unambiguous,
precise, and easy to interpret. By referring to any of the instructions in
an algorithm one can clearly understand what is to be done. Every
fundamental operator in instruction must be defined without any
ambiguity.
Finiteness: An algorithm must terminate after a finite number of steps
in all test cases. Every instruction which contains a fundamental
operator must be terminated within a finite amount of time. Infinite
loops or recursive functions without base conditions do not possess
finiteness.
Effectiveness: An algorithm must be developed by using very basic,
simple, and feasible operations so that one can trace it out by using
just paper and pencil.
[Link] Between Primitive and Non-Primitive Data Structures
Q.4 Define Abstract Data Types
Ans:
An Abstract Data Type (ADT) is a conceptual model that defines a
set of operations and behaviors for a data structure, without
specifying how these operations are implemented or how data is
organized in memory.
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 provides an implementation-
independent view.
Examples: List ADT, Stack ADT, Queue ADT
[Link] is sparse matrix ? Explain the representation of it.
A sparse matrix is a matrix that contains a large number of zero elements compared to the total
number of elements. In other words, it has very few non-zero elements. Sparse matrices are
commonly used in scientific computing, optimization problems, and graph algorithms, where storing
all elements in a traditional 2D array would be inefficient in terms of memory and computation.
Representation of Sparse Matrix
Since storing a sparse matrix in a normal 2D array wastes memory, we use efficient data
structures to store only the non-zero elements. There are three standard representations:
1. Triplet Representation (Coordinate List Representation)
This representation stores only the non-zero elements along with their row and column
indices in a compact form.
Each non-zero element is stored as a triplet (row, column, value) in a separate structure.
Uses an array of size (non-zero elements × 3).
Efficient for simple traversal but inefficient for modification.
2. Compressed Sparse Row (CSR) Representation
CSR is one of the most widely used representations, especially in libraries like SciPy and
Eigen. It stores only the non-zero values, their column indices, and an additional array for
row pointers.
Storage Arrays in CSR Format:
1. Values → Stores all non-zero elements.
2. Column Index → Stores the column number of each non-zero element.
3. Row Pointer → Stores the index where each row starts in the values array.
CSR Representation:
Values Array: [3, 4, 5, 6]
Column Indices: [2, 0, 3, 1]
Row Pointers: [0, 1, 3, 3, 4]
Efficient for matrix-vector multiplication.
Saves memory and supports fast row-wise access.
3. Linked List Representation
Instead of using arrays, we can use a linked list where each node contains:
Row index
Column index
Value
Pointer to next non-zero element
This representation is flexible but has higher memory overhead due to pointer storage.
Q.6. Explain double hashing in data structure with its advantages and
disadvantages.
Ans: Double Hashing is a collision resolution technique used in open addressing for hash
tables. It uses two hash functions to determine the probing sequence, reducing clustering and
improving efficiency.
In double hashing, if a collision occurs at index h1(key), we use a second hash function
h2(key) to determine the next probe position.
Formula for Double Hashing:
Index = (h1(key) + i × h2(key) ) % TableSize
Where:
h1(key) → Primary hash function
h2(key) → Secondary hash function (must not be 0)
i → Probe count (0,1,2,...)
Example of Double Hashing
Given Data:
Hash Table Size = 7
h1(key) = key % 7
h2(key) = 1 + (key % 5)
Insert Elements: [49, 63, 56, 52]
1. 49 → h1(49) = 49 % 7 = 0 (Inserted at index 0)
2. 63 → h1(63) = 63 % 7 = 0 (Collision!)
o h2(63) = 1 + (63 % 5) = 1 + 3 = 4
o New index: (0 + 1 × 4) % 7 = 4 (Inserted at index 4)
3. 56 → h1(56) = 56 % 7 = 0 (Collision!)
o h2(56) = 1 + (56 % 5) = 1 + 1 = 2
o New index: (0 + 1 × 2) % 7 = 2 (Inserted at index 2)
4. 52 → h1(52) = 52 % 7 = 3 (Inserted at index 3)
Advantages of Double Hashing
1. Avoids Clustering: Unlike linear or quadratic probing, double hashing spreads data more
evenly, reducing long chains of collisions.
2. Better Performance: Since it avoids clustering, searching and inserting elements take fewer
steps.
3. Efficient Space Usage: It doesn't need extra memory like separate chaining (which uses
linked lists).
4. Works Well for Large Data Sets: Even when the table is filling up, double hashing still
performs better than other probing techniques.
Disadvantages of Double Hashing
1. Slower Than Other Methods: It requires two hash function calculations for every operation,
making it slightly slower than linear probing.
2. Risk of Infinite Loops: If the second hash function isn’t chosen carefully, it can create cycles,
making insertion impossible.
3. More Complex to Implement: Choosing the right hash functions is tricky. A poor choice can
lead to bad performance.
4. Performance Drops with High Load Factor: As the table fills up, finding an empty slot takes
longer, making operations slower.