UNIT=5
Explain Hashing and Collision Resolution. (GTU Style – Long Answer)
Hashing
Hashing is a technique used to store and search data quickly.
In hashing, a key is converted into an index value using a hash function.
This index tells where the data should be stored in memory.
Hashing makes searching faster because data can be found directly.
Definition
Hashing is the process of converting a key into a fixed address (index) using a hash function.
The location where data is stored is called a hash table.
Hash Function
A hash function is a formula used to calculate the index of an element.
General form:
H(key) = key mod table_size
Where:
key = data value
table_size = size of hash table
Example of Hashing
Suppose table size = 10
Keys are:
25, 32, 18, 41
Using hash function:
H(key) = key mod 10
Calculation:
H(25) = 5
H(32) = 2
H(18) = 8
H(41) = 1
So data is stored at these positions.
Advantages of Hashing
1. Fast Searching
Data can be found quickly.
2. Fast Insertion
New data can be added easily.
3. Efficient Memory Use
Stores data at calculated locations.
Disadvantages of Hashing
1. Collision Problem
Two keys may get the same location.
2. Fixed Table Size
Table size is limited.
Collision in Hashing
A collision occurs when two different keys produce the same hash value.
This means both keys want to store at the same location.
Example of Collision
Table size = 10
Keys:
25, 35
Hash function:
H(key) = key mod 10
Calculation:
H(25) = 5
H(35) = 5
Both keys get index 5.
This is called collision.
Collision Resolution
Collision resolution means solving the collision problem.
It decides where to store the second element.
There are mainly two methods:
1. Open Addressing
In this method, if one location is full, another empty location is searched.
Types:
a) Linear Probing
In linear probing, the next position is checked one by one.
Formula:
H(i) = (Hash(key) + i) mod table_size
Example:
If index 5 is full:
Check 6 → 7 → 8 …
Simple and easy.
b) Quadratic Probing
In quadratic probing, positions are checked using square values.
Formula:
H(i) = (Hash(key) + i²) mod table_size
It reduces clustering.
c) Double Hashing
In double hashing, a second hash function is used to find a new position.
Formula:
H(i) = (H1(key) + i × H2(key)) mod table_size
It gives better distribution.
2. Separate Chaining
In this method, a linked list is created at each index.
If collision occurs, the new element is added to the linked list.
Example:
Index 5:
25 → 35 → 45
This stores multiple values at the same index.
Advantages of Collision Resolution
Solves collision problem
Improves searching efficiency
Uses hash table effectively
Disadvantages of Collision Resolution
May increase searching time
Extra memory may be required
More complex than normal hashing
Applications of Hashing
Database indexing
Password storage
Dictionary implementation
Symbol tables
Cache memory
Conclusion
Hashing is a fast technique for storing and searching data. It uses a hash function to find the storage location. Sometimes collisions occur when two keys get the same location. Collision resolution methods like linear probing and separate chaining are used to solve this problem efficiently.
Explain Hash Functions. (GTU Style – Long Answer)
Hash Function
A Hash Function is a mathematical function used in hashing to convert a key into an index value.
This index value tells where the data should be stored in the hash table.
It helps in fast searching, insertion, and deletion.
Definition
A hash function is a function that maps a given key into a fixed-size address in memory.
It generates the position of data in the hash table.
General form:
H(key) = address
Need of Hash Function
Hash function is needed because:
It stores data at a fixed location.
It makes searching faster.
It reduces time complexity.
Without hash function, searching may take more time.
Characteristics of Good Hash Function
A good hash function should have the following properties:
1. Simple to Calculate
The function should be easy and fast.
2. Uniform Distribution
Data should spread evenly in the table.
3. Minimum Collision
Different keys should produce different addresses.
4. Uses Full Table
It should use all memory locations properly.
Types of Hash Functions
There are many types of hash functions.
1. Division Method
This is the simplest and most common method.
The key is divided by table size, and the remainder is used as the index.
Formula:
H(key) = key mod m
Where:
key = data value
m = size of hash table
Example:
Key = 25
Table size = 10
H(25) = 25 mod 10
= 5
So data is stored at index 5.
2. Mid-Square Method
In this method:
Square the key.
Take the middle digits as the index.
Formula:
H(key) = middle digits of (key²)
Example:
Key = 12
12² = 144
Middle digit = 4
So index = 4.
3. Folding Method
In this method:
Divide the key into equal parts.
Add all parts.
Formula:
H(key) = sum of parts
Example:
Key = 12345
Split:
12 + 34 + 5 = 51
So index = 51.
4. Digit Analysis Method
In this method:
Specific digits of the key are selected to form the hash value.
Example:
Key = 987654
Take 2nd and 4th digits:
8 and 6
Hash value = 86.
5. Multiplication Method
In this method:
The key is multiplied by a constant value.
Formula:
H(key) = floor(m × (key × A mod 1))
Where:
m = table size
A = constant (0 < A < 1)
Example:
This method is used for better distribution.
Advantages of Hash Functions
1. Fast Access
Data can be found quickly.
2. Easy Insertion
New records can be added easily.
3. Efficient Searching
Searching time is reduced.
4. Better Memory Use
Uses memory locations properly.
Disadvantages of Hash Functions
1. Collision May Occur
Two keys may get the same index.
2. Fixed Table Size
Table size cannot grow easily.
3. Extra Collision Handling Needed
Special methods are required.
Applications of Hash Functions
Database indexing
Password storage
Cache memory
Symbol tables
File systems
Searching algorithms
Conclusion
Hash functions are important in hashing because they convert keys into memory addresses. They make searching, insertion, and deletion very fast. Different methods like division, folding, and mid-square are used based on requirements. A good hash function reduces collisions and improves performance.
UNIT=2
Explain Storage Structure of Array with Example. (GTU Style – Long Answer)
Storage Structure of Array
An array is a collection of elements of the same data type stored in continuous memory locations.
The storage structure of an array shows how array elements are stored in memory and how their addresses are calculated.
Each element of an array occupies a fixed amount of memory.
Because the elements are stored continuously, they can be accessed directly using the index.
Definition
The storage structure of an array is the method of arranging array elements in sequential memory locations.
It helps in fast access and easy calculation of addresses.
Important Terms
1. Base Address (BA)
The address of the first element of the array is called the Base Address.
Example:
If array starts at memory location 1000, then:
BA = 1000
2. Index
The position number of an element is called index.
Array indexing usually starts from 0.
Example:
A[0], A[1], A[2], A[3]
3. Size of Element (w)
The memory required for one element is called element size.
Example:
If integer takes 2 bytes:
w = 2 bytes
Address Calculation in 1-D Array
Formula:
LOC(A[i]) = BA + (i × w)
Where:
LOC(A[i]) = address of element
BA = base address
i = index number
w = size of one element
Example of 1-D Array
Suppose:
A[5] = {10,20,30,40,50}
Base Address = 1000
Element size = 2 bytes
Find address of A[3]
Formula:
LOC(A[3]) = 1000 + (3 × 2)
= 1000 + 6
= 1006
So address of A[3] is 1006
Memory Representation
A[0] → 1000
A[1] → 1002
A[2] → 1004
A[3] → 1006
A[4] → 1008
This shows continuous storage.
Address Calculation in 2-D Array
A 2-D array can be stored in two ways:
1. Row Major Order
Rows are stored one after another.
Formula:
LOC(A[i][j]) = BA + [(i × n) + j] × w
Where:
n = number of columns
Example:
Array:
2 × 3 array
Base Address = 1000
Element size = 2 bytes
Find A[1][2]
LOC = 1000 + [(1×3)+2]×2
= 1000 + (5×2)
= 1010
2. Column Major Order
Columns are stored one after another.
Formula:
LOC(A[i][j]) = BA + [(j × m) + i] × w
Where:
m = number of rows
Advantages of Array Storage Structure
1. Fast Access
Any element can be accessed directly.
2. Simple Address Calculation
Easy formula.
3. Continuous Memory
Easy to manage.
Disadvantages of Array Storage Structure
1. Fixed Size
Size cannot change easily.
2. Memory Wastage
Unused spaces may remain.
3. Insertion and Deletion Difficult
Shifting may be needed.
Applications of Array
Matrix representation
Searching and sorting
Storing marks of students
Polynomial representation
Database records
Conclusion
The storage structure of an array is important because it shows how data is stored in memory. Since array elements are stored continuously, accessing them becomes fast and easy. Address calculation formulas help to find the location of any element directly.
Explain Stack and its Applications. (GTU Style – 7 Marks)
Stack
A Stack is a linear data structure in which insertion and deletion are performed from only one end.
This end is called TOP.
Stack follows the LIFO (Last In First Out) principle.
This means the element inserted last will be removed first.
It is similar to a stack of plates where the last plate placed on top is removed first.
Definition
A stack is a collection of elements in which all insertions and deletions are done from one side called TOP.
It follows the LIFO rule.
Basic Operations of Stack
The following operations are performed on stack:
1. Push
Push operation is used to insert a new element into the stack.
The new element is added at the TOP.
Example:
Push(10), Push(20), Push(30)
Stack becomes:
TOP → 30
20
10
2. Pop
Pop operation is used to remove the top element from the stack.
The last inserted element is removed first.
Example:
Pop()
Removes 30
Stack becomes:
TOP → 20
10
3. Peek (Top)
Peek operation shows the top element without removing it.
Example:
If stack is:
TOP → 20
10
Peek returns 20
4. IsEmpty
Checks whether the stack is empty or not.
If no elements exist, stack is empty.
5. IsFull
Checks whether the stack is full or not.
Used in array implementation.
Example of Stack
Suppose we insert:
10, 20, 30, 40
After push operations:
TOP → 40
30
20
10
If one pop operation is performed:
TOP → 30
20
10
This shows LIFO.
Representation of Stack
Stack can be represented in two ways:
1. Array Representation
Elements are stored in an array.
Simple and easy.
2. Linked List Representation
Elements are stored as nodes.
Dynamic memory allocation is possible.
Advantages of Stack
1. Easy Insertion and Deletion
Operations are simple.
2. Fast Access to Top Element
Top element is directly available.
3. Useful in Function Calls
Manages function execution.
4. Simple Implementation
Easy to implement.
Disadvantages of Stack
1. Limited Access
Only top element can be accessed.
2. Overflow Problem
Occurs when stack becomes full.
3. Underflow Problem
Occurs when stack is empty and pop is performed.
Applications of Stack
1. Function Calling
Stack stores function calls and returns.
Used in recursion.
Example:
When one function calls another.
2. Expression Evaluation
Used to evaluate expressions like:
(A+B)*C
3. Parenthesis Matching
Checks whether brackets are balanced.
Example:
( ) { } [ ]
4. Undo Operation
Used in text editors.
Example:
Undo typing.
5. Browser History
Stores visited pages.
Back button works using stack.
6. String Reversal
Stack helps reverse strings.
Example:
HELLO → OLLEH
Conclusion
Stack is an important linear data structure that follows the LIFO principle. It allows insertion and deletion from one side only. It is widely used in function calling, expression evaluation, browser history, and many other applications. Its simple structure makes it very useful in programming.
Write Push and Pop Algorithm (GTU Style)
Push Algorithm
The Push operation is used to insert an element into the stack.
Before insertion, it checks whether the stack is full or not.
Algorithm for Push
PUSH(STACK, TOP, ITEM)
Step 1: If TOP = MAX - 1
Print "Stack Overflow"
Stop
Step 2: TOP = TOP + 1
Step 3: STACK[TOP] = ITEM
Step 4: Stop
Explanation
Step 1: Check if stack is full.
Step 2: Increase TOP by 1.
Step 3: Insert the new element at TOP.
Step 4: End.
Example of Push
Suppose stack size = 5
Current stack:
TOP → 30
20
10
Insert 40
After push:
TOP → 40
30
20
10
Pop Algorithm
The Pop operation is used to remove the top element from the stack.
Before deletion, it checks whether the stack is empty or not.
Algorithm for Pop
POP(STACK, TOP)
Step 1: If TOP = -1
Print "Stack Underflow"
Stop
Step 2: ITEM = STACK[TOP]
Step 3: TOP = TOP - 1
Step 4: Return ITEM
Step 5: Stop
Explanation
Step 1: Check if stack is empty.
Step 2: Store top element.
Step 3: Decrease TOP by 1.
Step 4: Return deleted element.
Step 5: End.
Example of Pop
Current stack:
TOP → 40
30
20
10
Perform Pop()
Removed element = 40
After pop:
TOP → 30
20
10
This follows LIFO (Last In First Out) principle.
No comments:
Post a Comment