Downloaded from tunotes.

in
1)Refer notes

2) Write definition for big o notation

3

Applications, Advantages and Disadvantages of Stack

A stack is a linear data structure in which the insertion of a new element and removal
of an existing element takes place at the same end represented as the top of the stack.
Applications of Stacks:
• Function calls: Stacks are used to keep track of the return addresses of function
calls, allowing the program to return to the correct location after a function has
finished executing.
• Recursion: Stacks are used to store the local variables and return addresses of
recursive function calls, allowing the program to keep track of the current state of
the recursion.
• Expression evaluation: Stacks are used to evaluate expressions in postfix notation
(Reverse Polish Notation).
• Syntax parsing: Stacks are used to check the validity of syntax in programming
languages and other formal languages.
• Memory management: Stacks are used to allocate and manage memory in some
operating systems and programming languages.

.
Advantages of Stacks:
• Simplicity: Stacks are a simple and easy-to-understand data structure, making them
suitable for a wide range of applications.
• Efficiency: Push and pop operations on a stack can be performed in constant
time (O(1)), providing efficient access to data.
• Last-in, First-out (LIFO): Stacks follow the LIFO principle, ensuring that the last
element added to the stack is the first one removed. This behavior is useful in many
scenarios, such as function calls and expression evaluation.
• Limited memory usage: Stacks only need to store the elements that have been
pushed onto them, making them memory-efficient compared to other data structures.
•
Disadvantages of Stacks:
• Limited access: Elements in a stack can only be accessed from the top, making it
difficult to retrieve or modify elements in the middle of the stack.
• Potential for overflow: If more elements are pushed onto a stack than it can hold,
an overflow error will occur, resulting in a loss of data.
• Not suitable for random access: Stacks do not allow for random access to
elements, making them unsuitable for applications where elements need to be
accessed in a specific order.
• Limited capacity: Stacks have a fixed capacity, which can be a limitation if the
number of elements that need to be stored is unknown or highly variable.

4) Refer notes

5) Dynamic Memory Allocation

The process of allocating memory to the variables during execution of the program or at
run time is known as dynamic memory allocation
int arr[100];
When this statement is executed, consecutive space for 100 integers is allocated. It is not
uncommon that we may be using only 10% or 20% of the allocated space, thereby wasting
rest of the space. To overcome this problem and to utilize the memory efficiently, C
language provides a mechanism of dynamically allocating memory so that only the amount
of memory that is actually required is reserved. We reserve space only at the run time for
the variables that are actually required. Dynamic memory allocation gives best performance
in situations in which we do not know memory requirements in advance
Memory allocation/de-allocation functions
Function Task

malloc() Allocates memory and returns a pointer to the first byte of allocated space
 calloc() Allocates space for an array of elements, initializes them to zero and returns a pointer to
the memory
free() Frees previously allocated memory
realloc() Alters the size of previously allocated memory

Advantages of Dynamic Memory allocation

• This allocation method has no memory wastage.
• The memory allocation is done at run time.
• Memory size can be changed based on the requirements of the dynamic memory allocation.
• If memory is not required, it can be freed.

6 Algorithm to print the number of nodes in a linked list

Step 1: [INITIALIZE] SET count=0
Step 2: [INITIALIZE] SET PTR = START
Step 3: Repeat Steps 4 and 5 while PTR != NULL
Step 4: SET count = count+1
Step 5: SET PTR = PTR NEXT
[END OF LOOP]
Step 6: Write Count
Step 7: EXIT

7
8
Difference between Full and Complete Binary Tree
A binary tree is a type of data structure where each node can only have two offspring at most
named as “left” and “right” child.

Complete Binary Tree:

A binary tree is said to be a complete binary tree if all its levels, except possibly the last level,
have the maximum number of possible nodes, and all the nodes in the last level appear as far
left as possible.

• Node C has just one child therefore, it is

not a Full binary tree.
• Node C also has a right child but no left child, therefore it is also not a Complete binary
tree.

9
BINARY HEAPS
A binary heap is a complete binary tree in which every node satisfies the heap property
which states that:
If B is a child of A, then key(A) ≥ key(B)
This implies that elements at every node will be either greater than or equal to the element
at its left and right child. Thus, the root node has the highest key value in the heap. Such a
heap is commonly known as a max-heap. Alternatively, elements at every node will be
either less than or equal to the element at its left and right child. Thus, the root has the
lowest key value. Such a heap is called a min-heap
10

Hashing refers to the process of generating a fixed-size output from an input of variable size
using the mathematical formulas known as hash functions. This technique determines an index
or location for the storage of an item in a data structure.

Applications of Hashing
1. Hashing provides constant time search, insert and delete operations on average. This is why
hashing is one of the most used data structure, example problems are, distinct elements,
counting frequencies of items, finding duplicates, etc.
2. Database indexing: Hashing is used to index and retrieve data efficiently in databases and
other data storage systems.
3. Dictionaries : To implement a dictionary so that we can quickly search a word
4. Password storage: Hashing is used to store passwords securely by applying a hash function
to the password and storing the hashed result, rather than the plain text password.
5. Network Routing: Determining the best path for data packets
6. Bloom Filters : Bloom filter is a space optimized and probabilistic version of hashing and
has huge applications like spam filtering, recommendations.
7. Cryptography: Hashing is used in cryptography to generate digital signatures, message
authentication codes (MACs), and key derivation functions.
8. Load balancing: Hashing is used in load-balancing algorithms, such as consistent hashing,
to distribute requests to servers in a network.
9. Blockchain: Hashing is used in blockchain technology, such as the proof-of-work
algorithm, to secure the integrity and consensus of the blockchain.
10. Image processing: Hashing is used in image processing applications, such as perceptual
hashing, to detect and prevent image duplicates and modifications.
11. File comparison: Hashing is used in file comparison algorithms, such as the MD5 and SHA-
1 hash functions, to compare and verify the integrity of files.
12. Fraud detection: Hashing is used in fraud detection and cybersecurity applications, such as
intrusion detection and antivirus software, to detect and prevent malicious activities.
13. Caching: Storing frequently accessed data for faster retrieval. For example browser caches,
we can use URL as keys and find the local storage of the URL.
14. Symbol Tables: Mapping identifiers to their values in programming languages
15. Associative Arrays: Associative arrays are nothing but hash tables only. Commonly SQL
library functions allow you retrieve data as associative arrays so that the retrieved data in
RAM can be quickly searched for a key.

11 (a) and (b) refer notes

12 (a) and (b) refer notes
13 (a) search
13(b) 14(a) and 14(b) refer notes(record)
15(a) refer class notes
15(b) MEMORY ALLOCATION ALGORITHMS:
First Fit In the first fit approach is to allocate the first free partition or hole large enough which
can accommodate the process. It finishes after finding the first suitable free partition.
Advantage Fastest algorithm because it searches as little as possible.
Disadvantage The remaining unused memory areas left after allocation become waste if it is too
smaller. Thus request for larger memory requirement cannot be accomplished.

2. Best Fit The best fit deals with allocating the smallest free partition which meets the
requirement of the requesting process. This algorithm first searches the entire list of free partitions
and considers the smallest hole that is adequate. It then tries to find a hole which is close to actual
process size needed.
Advantage Memory utilization is much better than first fit as it searches the smallest free partition
first available.
Disadvantage It is slower and may even tend to fill up memory with tiny useless holes.
3. Worst fit In worst fit approach is to locate largest available free portion so that the portion left
will be big enough to be useful. It is the reverse of best fit.
Advantage Reduces the rate of production of small gaps.
Disadvantage If a process requiring larger memory arrives at a later stage then it cannot be
accommodated as the largest hole is already split and occupied.

Refer ktu ppts also(Did in class)

16 (a)
Adding two polynomials using Linked List

Given two polynomial numbers represented by a linked list. The task is to add these
lists meaning the coefficients with the same variable powers will be added.
Note: Given polynomials are sorted in decreasing order of power.
Example:
Input:
head1: [[5, 2], [4, 1], [2, 0]]
head2: [[5, 1], [5, 0]]
Output: [[5, 2], [9, 1], [7, 0]]
Explanation:

head1: [[5, 3], [4, 2], [2, 0]]

head2: [[5, 1], [-5, 0]]
Output: [[5, 3], [4, 2], [5, 1], [-3, 0]]
Explanation: head1 can be represented as 5x^3 + 4x^2 + 2 , head2 can be represented as 5x –
5, add both the polynomials to get 5x^3 + 4x^2 + 5x – 3
Advantages of Polynomial Addition using Linked List in C

Performing Polynomial Addition using Linked List has the following

advantages.

• Unlike arrays, linked lists can handle polynomials of any degree.

• Linked Lists can efficiently handle the storage and retrieval of polynomial
coefficients and degrees.
• If we use Linked List, we can also perform Polynomial Addition
recursively.

The Polynomial Addition using Linked List in C also have some

disadvantages which are listed below.

• The performance of Polynomial Addition using a Linked List is slower

than arrays because of the overhead of linked list operations.
• Implementation of Polynomial Addition using Linked List is more
complex.
• Polynomial Addition using Linked List also require more memory
overhead than arrays as they need to store pointers and dynamic memory
allocation.

ALGORITHM:

1. Start the program.

2. Declare the node as link.

3. Allocate memory space for pol1, pol2 and poly.

4. Read pol1 and pol2.

5. Call the function polyadd.

6. Add the co-efficients of poly1 and poly2 having the equal power and store it in poly.

7. If there is no co-efficient having equal power in poly1 and poly2, then add it to poly.

8. Display the poly1, poly2 and poly.

9. Stop the program.

16(b) Refer class notes

17(a)

Binary Search Tree

A Binary Search Tree (or BST) is a data structure used in computer science for
organizing and storing data in a sorted manner. Each node in a Binary Search Tree has
at most two children, a left child and a right child, with the left child containing values
 less than the parent node and the right child containing values greater than the parent
node. This hierarchical structure allows for efficient searching, insertion,
and deletion operations on the data stored in the tree.

Algorithm to search for a given value in a binary search tree

SearchElement (TREE, VAL)

Step 1: IF TREE DATA = VAL OR TREE = NULL
Return TREE
ELSE
IF VAL < TREE DATA
Return searchElement(TREE LEFT, VAL)
ELSE
Return searchElement(TREE RIGHT, VAL)
[END OF IF]
[END OF IF]
Step 2: END

Algorithm to insert a given value in a binary search tree

Insert (TREE, VAL)

Step 1: IF TREE = NULL
Allocate memory for TREE
SET TREE DATA = VAL
SET TREE LEFT = TREE RIGHT = NULL
ELSE
IF VAL < TREE DATA
Insert(TREE LEFT, VAL)
ELSE
Insert(TREE RIGHT, VAL)
[END OF IF]
[END OF IF]
Step 2: END

Explanation requied (Refer pdf)

Extra
Comparison Between B Trees and B+ Trees
Table 11.1 shows the comparison between B trees and B+ trees.
Table 11.1 Comparison between B trees and to B+ trees
B Tree B+ Tree
1. Search keys are not repeated 1. Stores redundant search key
2. Data is stored in internal or leaf nodes 2. Data is stored only in leaf nodes
3. Searching takes more time as data may
be found in a leaf or non-leaf node
 3. Searching data is very easy as the
data can be found in leaf nodes only
4. Deletion of non-leaf nodes is very complicated 4. Deletion is very simple because data
will be in the leaf node
5. Leaf nodes cannot be stored using linked lists 5. Leaf node data are ordered
using sequential linked lists
6. The structure and operations are complicated 6. The structure and operations are
Simple

17(b)

Graph and its representations

A Graph is a non-linear data structure consisting of vertices and edges. The vertices are
sometimes also referred to as nodes and the edges are lines or arcs that connect any two nodes
in the graph. More formally a Graph is composed of a set of vertices( V ) and a set of
edges( E ). The graph is denoted by G(V, E).
Representations of Graph
Here are the two most common ways to represent a graph : For simplicity, we are going to
consider only unweighted graphs in this post.
1. Adjacency Matrix
2. Adjacency List
Adjacency Matrix Representation
An adjacency matrix is a way of representing a graph as a matrix of boolean (0’s and 1’s)
Let’s assume there are n vertices in the graph So, create a 2D matrix adjMat[n][n] having
dimension n x n.
• If there is an edge from vertex i to j, mark adjMat[i][j] as 1.
• If there is no edge from vertex i to j, mark adjMat[i][j] as 0.

Representation of Directed Graph as Adjacency list:

The below directed graph has 3 vertices. So, an array of list will be created of size 3, where
each indices represent the vertices. Now, vertex 0 has no neighbours. For vertex 1, it has two
neighbour (i.e, 0 and 2) So, insert vertices 0 and 2 at indices 1 of array. Similarly, for vertex 2,
insert its neighbours in array of list.

18(a)
Refer record
18(b)

Degree of a node It is equal to the number of children that a node has. The degree of a leaf node is
zero. For example, in the ree, degree of node 4 is 2, degree of node 5 is zero and degree
of node 7 is 1.

Different question but same method to follow

• Create a binary search tree using the following data elements:

45, 39, 56, 12, 34, 78, 32, 10, 89, 54, 67, 81

Height of a tree It is the total number of nodes on the path from the root node
to the deepest node in the tree. A tree with only a root node has a height of 1.

19(a) Refer Record

19(b) and 20(a)
(Refer pdf and class notes given)

20 (b)

Difference Between Insertion Sort and Selection Sort

Gradually creates a sorted

Finds the minimum (or maximum) element
section at the beginning of the
Basic Idea from the unsorted section and places it at the
list, inserting each new item in its
end of the sorted section.
proper place in this section.
Generally more efficient than Less efficient, especially for large lists, as it
Efficiency selection sort, especially for always performs O(n) comparisons for each
small lists or partially sorted lists. pass.
O(n) (when the list is already O(n^2), regardless of the initial order of the
Best Case
sorted) elements.
Worst O(n^2) (when the list is sorted in O(n^2), regardless of the initial order of the
Case reverse order) elements.

Stable (does not change the Not stable by default (can be made stable
Stability
relative order of equal elements) with some modifications)

Auxiliary
O(1) (in-place) O(1) (in-place)
Space

Better for datasets where the

Suitable for scenarios where swapping cost is
Suitability array is either small or elements
high, as it makes minimal number of swaps.
are already partially sorted.