ASSIGNMENT
1.Define data structure. Give two examples of linear and non-linear data
structures.
-A data structure is a specialized format for organizing, processing, and storing data.
Linear: Array, Linked List
Non-linear: Tree, Graph
2. Differentiate between an array and a linked list.
3. What is time complexity? Express the worst-case time complexity of
linear search.
-Time complexity describes the computational complexity that describes the amount of
time it takes to run an algorithm.
Worst-case time complexity of linear search is: - O(n)
4. What is overflow and underflow in the context of stacks?
- Overflow: Trying to push an element in a full stack.
Underflow: Trying to pop an element from an empty stack.
5. Explain the term space complexity with an example.
- Space complexity refers to the total amount of memory space required by an algorithm.
Example: A function with a fixed number of variables has space complexity O (1).
6. What is a stack? Mention two real-life applications.
A stack is a linear data structure that stores data in LIFO (Last in First Out) order.
APPLICATION: - Two real-life application of a stack data structure is: -
(i)the undo feature in text editors and image editing software.
(ii)and the back button functionality in web browsers.
7. What is the height of a tree? Calculate the height of a BST with 7 nodes.
- Height of a tree: Number of edges on the longest path from root to a leaf.
For a balanced BST with 7 nodes, height = log2(7) = approx. 2.8 => 2 (floor value)
8. How does a queue differ from a circular queue?
-Queue: Elements are added at rear and removed from front. Fixed size wastes memory.
Circular Queue: Last position is connected back to the first, reusing the memory
efficiently.
9. Write the postfix form of the expression: (A + B) * (C - D / E).
Postfix form of the expression: - AB+CD/E-*
10. What is hashing? Define collision in hashing.
Hashing: A technique to convert a range of key values into a range of indexes.
Collision: When two keys hash to the same index.
11. Explain how a circular queue avoids wastage of memory compared to
a linear queue.
-A circular queue connects the last position back to the first, allowing the reuse of
emptied spaces, avoiding unused memory slots.
12. Define a binary tree. Differentiate between a full and complete binary
tree.
it is a hierarchical data structure where each node has at most two children, referred
to as the left and right child
13. Explain dynamic memory allocation in linked lists.
--Dynamic memory allocation in linked list means allocating memory for each node
(data element and a pointer to the next element) during the program's runtime, rather
than at compile time, allowing the list to grow or shrink as needed
14. Write the recursive formula for Fibonacci series and compute fib (5).
-the recursive formula for Fibonacci series is: - F(n) = F(n-1) + F(n-2),
F (0) =0, F (1) =1 , fib (5) = 5*4*3*2*1=120
15. What is binary search? List one condition for its application.
-it is a highly efficient algorithm used to find the position of a target value within a
sorted array or list by repeatedly dividing the search interval in half.
Condition of application is: The list must be sorted.
16. Write the steps to insert a node at the beginning of a singly linked list.
-1. Create new node
2.Point new node's next to head
3.Update head to new node
Algorithm steps: -
function insertAtBeginning (head, data):
newNode = createNode(data) // Create a new node with data
newNode.next = head // Make new node point to the old head
head = newNode // Update the head pointer
return head // Return the updated head
17. Compare divide and conquer and greedy algorithms with examples.
-Divide and Conquer: Break into subproblems (e.g., Merge Sort)
Greedy: Local optimization at each step (e.g., Kruskal's Algorithm)
18. What is recursion? Write a recursive function to compute factorial.
-recursion is a technique for solving problems by breaking them down into smaller,
similar subproblems.
int factorial (int n) {
if (n == 0) return 1;
else return n * factorial(n-1);}
19. Implement a stack using an array (write pseudocode for push and pop
operations).
PUSH Operation: POP Operation:
Initialize the stack: -
function PUSH (element): function POP ():
MAX_SIZE ← 100
if top == MAX_SIZE - 1: if top == -1:
stack ← array of size MAX_SIZE
print "Stack Overflow" print "Stack Underflow"
top ← -1 // stack is empty when top = -1
return return null
top ← top + 1 element ← stack[top]
stack[top] ← element top ← top - 1
return element
20. What is a priority queue? How is it different from a normal queue?
- A priority queue is a type of queue where each element is associated with a priority
and served according to its priority.
The key difference between a priority queue and a normal queue is that a priority queue
prioritizes elements based on their assigned priority, while a normal queue follows a
first in, first out (FIFO) order.
