Group – “A”
Brief Answer Questions.
Attempts ant four questions.
1. Why are data structure important?
Ans: Here are several reasons why data structures are important:
- Organization of Data
- Efficient Data Retrieval and Modification
- Optimized Resource Utilization
- Scalability and Performance
- Code Clarity and Maintainability
2. Create a class to represent a node in singly linked list.
Ans: A class representing a node in a singly linked list:
public class ListNode {
public int val;
public ListNode next;
public ListNode(int val) {
this.val = val;
this.next = null;
}
}
3. What are the applications of stack.
Ans: Some common applications of stacks include:
- Function Calls
- Expression Evaluation
- Undo Mechanisms
- Backtracking Algorithms
- Undo/Redo Operations
- Syntax Parsing
4. Write a recursive method to find nth term of Fibonacci sequence.
Ans: Here is a recursive method to find nth term of Fibonacci sequence:
public class Fibonacci {
public static void main(String[] args) {
int n = 10; // Change this to the desired nth term
int result = fibonacci(n);
System.out.println("The " + n + "th term of the Fibonacci sequence is: " + result);
}
public static int fibonacci(int n) {
if (n <= 1) {
return n;
} else {
return fibonacci(n - 1) + fibonacci(n - 2);
}
}
}
5. Define skip list.
Ans: A skip list is a data structure that allows for efficient searching, insertion, and deletion operations in a sorted sequence of elements. It is a probabilistic data structure that uses multiple linked lists with different “levels” to achieve fast search times.
Group – “B”
Short Answer questions:
Attempts any two questions.
6. Write java methods for push and pop operation of stack using array.
Ans: Below are Java methods for implementing push and pop operations on a stack using an array:
public class ArrayStack {
private int maxSize;
private int[] stackArray;
private int top;
// Constructor to initialize the stack
public ArrayStack(int size) {
this.maxSize = size;
this.stackArray = new int[maxSize];
this.top = -1; // Initialize top to -1 as stack is empty
}
// Method to push an element onto the stack
public void push(int value) {
if (isFull()) {
System.out.println("Stack is full. Cannot push element " + value);
return;
}
stackArray[++top] = value;
System.out.println("Pushed " + value + " onto the stack.");
}
// Method to pop an element from the stack
public int pop() {
if (isEmpty()) {
System.out.println("Stack is empty. Cannot pop element.");
return -1; // Return a sentinel value indicating failure
}
int poppedElement = stackArray[top--];
System.out.println("Popped " + poppedElement + " from the stack.");
return poppedElement;
}
// Method to check if the stack is empty
public boolean isEmpty() {
return (top == -1);
}
// Method to check if the stack is full
public boolean isFull() {
return (top == maxSize - 1);
}
public static void main(String[] args) {
ArrayStack stack = new ArrayStack(5); // Create a stack with size 5
// Push some elements onto the stack
stack.push(10);
stack.push(20);
stack.push(30);
stack.push(40);
stack.push(50);
stack.push(60); // This will exceed the stack size
// Pop elements from the stack
stack.pop();
stack.pop();
stack.pop();
stack.pop();
stack.pop();
stack.pop(); // This will try to pop from an empty stack
}
}
7. Write a java method to insert a node at the end of DLL.
Ans: Here’s a Java method to insert a node at the end of a Doubly Linked List (DLL):
class Node {
int data;
Node prev, next;
public Node(int data) {
this.data = data;
this.prev = null;
this.next = null;
}
}
class DoublyLinkedList {
Node head;
// Method to insert a node at the end of the DLL
public void insertAtEnd(int data) {
Node newNode = new Node(data);
if (head == null) {
head = newNode;
return;
}
Node current = head;
while (current.next != null) {
current = current.next;
}
current.next = newNode;
newNode.prev = current;
}
// Method to display the DLL
public void display() {
Node current = head;
while (current != null) {
System.out.print(current.data + " ");
current = current.next;
}
System.out.println();
}
}
public class Main {
public static void main(String[] args) {
DoublyLinkedList dll = new DoublyLinkedList();
dll.insertAtEnd(1);
dll.insertAtEnd(2);
dll.insertAtEnd(3);
dll.display(); // Output: 1 2 3
}
}
8. Convert the infix expression to postfix: (( A-X +(B*C+Y)) / ( D-E))
Ans: To convert the given infix expression to postfix notation, we’ll use the shunting-yard algorithm, which is a common method for parsing mathematical expressions. Here’s how it works:
- Initialize an empty stack for operators and an empty list for the output.
- Scan the infix expression from left to right.
- If the current token is an operand, add it to the output.
- If the current token is a left parenthesis, push it onto the stack.
- If the current token is a right parenthesis, pop operators from the stack and add them to the output until a left parenthesis is encountered. Discard the left parenthesis.
- If the current token is an operator, pop operators from the stack and add them to the output if they have higher precedence than the current operator (or equal precedence if the current operator is left-associative). Then, push the current operator onto the stack.
- After scanning the entire expression, pop any remaining operators from the stack and add them to the output.
Let’s apply this algorithm to the given infix expression: ((A-X+(B*C+Y))/(D-E))
- Infix expression: ((A-X+(B*C+Y))/(D-E))
- Postfix expression: (Empty)
Now, let’s go through each token in the infix expression and apply the shunting-yard algorithm:
- ( : Push “(” onto the stack.
- ( : Push “(” onto the stack.
- A : Add “A” to the output.
- : Push “-” onto the stack.
- X : Add “X” to the output.
- : Pop “-” from the stack and add it to the output. Push “+” onto the stack.
- ( : Push “(” onto the stack.
- B : Add “B” to the output.
- : Push “*” onto the stack.
- C : Add “C” to the output.
- : Pop “*” from the stack and add it to the output. Push “+” onto the stack.
- Y : Add “Y” to the output.
- ) : Pop “+” from the stack and add it to the output. Pop “(” from the stack and discard it.
- ) : Pop “+” from the stack and add it to the output. Pop “(” from the stack and discard it.
- / : Push “/” onto the stack.
- ( : Push “(” onto the stack.
- D : Add “D” to the output.
- : Push “-” onto the stack.
- E : Add “E” to the output.
- ) : Pop “-” from the stack and add it to the output. Pop “(” from the stack and discard it.
- End of expression: Pop “/” from the stack and add it to the output.
So, the postfix expression is: A X – B C * Y + D E – /
Therefore, the infix expression ((A-X+(B*C+Y))/(D-E)) in postfix notation is: A X – B C * Y + D E – /
Group – “c”
Long Answer Questions:
Attempts any two questions.
9. Write java methods to implement enqueue and dequeue in circular queue.
Ans: Below are Java methods to implement enqueue and dequeue operations in a circular queue:
public class CircularQueue {
private int[] queue;
private int front, rear, size, capacity;
public CircularQueue(int capacity) {
this.capacity = capacity;
queue = new int[capacity];
front = rear = -1;
size = 0;
}
// Method to enqueue an element into the circular queue
public void enqueue(int item) {
if (isFull()) {
System.out.println("Queue is full. Cannot enqueue.");
return;
}
if (isEmpty()) {
front = rear = 0;
} else {
rear = (rear + 1) % capacity;
}
queue[rear] = item;
size++;
System.out.println(item + " enqueued to the queue");
}
// Method to dequeue an element from the circular queue
public int dequeue() {
if (isEmpty()) {
System.out.println("Queue is empty. Cannot dequeue.");
return -1; // Returning a default value, assuming -1 indicates error
}
int item = queue[front];
if (front == rear) {
front = rear = -1;
} else {
front = (front + 1) % capacity;
}
size--;
System.out.println(item + " dequeued from the queue");
return item;
}
// Method to check if the circular queue is empty
public boolean isEmpty() {
return size == 0;
}
// Method to check if the circular queue is full
public boolean isFull() {
return size == capacity;
}
// Method to display the elements of the circular queue
public void display() {
if (isEmpty()) {
System.out.println("Queue is empty");
return;
}
int i = front;
do {
System.out.print(queue[i] + " ");
i = (i + 1) % capacity;
} while (i != (rear + 1) % capacity);
System.out.println();
}
public static void main(String[] args) {
CircularQueue cq = new CircularQueue(5);
cq.enqueue(1);
cq.enqueue(2);
cq.enqueue(3);
cq.enqueue(4);
cq.enqueue(5);
cq.display();
cq.dequeue();
cq.dequeue();
cq.display();
cq.enqueue(6);
cq.enqueue(7);
cq.display();
cq.dequeue();
cq.dequeue();
cq.dequeue();
cq.dequeue();
cq.dequeue(); // Trying to dequeue from an empty queue
}
}
10. What is TOH problem? Write a recursive algorithm or java method to implement it.
Ans: The Tower of Hanoi (TOH) problem is a classic problem in computer science and mathematics. It consists of three rods and a number of disks of different sizes, which can slide onto any rod. The puzzle starts with the disks stacked in ascending order of size on one rod, with the smallest disk at the top, making a conical shape. The objective of the puzzle is to move the entire stack to another rod, obeying the following rules:
- Only one disk can be moved at a time.
- Each move consists of taking the top disk from one of the stacks and placing it on top of another stack.
- No disk may be placed on top of a smaller disk.
Here’s a recursive Java method to solve the Tower of Hanoi problem:
public class TowerOfHanoi {
public static void main(String[] args) {
int n = 3; // Number of disks
towerOfHanoi(n, 'A', 'C', 'B');
}
// Recursive method to solve Tower of Hanoi problem
public static void towerOfHanoi(int n, char fromRod, char toRod, char auxRod) {
if (n == 1) {
System.out.println("Move disk 1 from rod " + fromRod + " to rod " + toRod);
return;
}
towerOfHanoi(n - 1, fromRod, auxRod, toRod);
System.out.println("Move disk " + n + " from rod " + fromRod + " to rod " + toRod);
towerOfHanoi(n - 1, auxRod, toRod, fromRod);
}
}
11. Define computational complexity of algorithm. What are the different methods to represent computational complexities of algorithms?
Ans: The computational complexity of an algorithm refers to the measure of the amount of computational resources required by the algorithm to solve a particular problem instance. It is often expressed in terms of time complexity and space complexity.
- Time Complexity: This measures the amount of time an algorithm takes to complete as a function of the size of the input. Time complexity is typically expressed using big O notation, which provides an upper bound on the growth rate of the algorithm’s running time. Common time complexities include O(1) (constant time), O(log n) (logarithmic time), O(n) (linear time), O(n log n) (linearithmic time), O(n^2) (quadratic time), O(2^n) (exponential time), etc.
- Space Complexity: This measures the amount of memory space an algorithm requires as a function of the size of the input. Like time complexity, space complexity is also expressed using big O notation. It indicates how the space required by the algorithm grows with the size of the input. Common space complexities include O(1) (constant space), O(n) (linear space), O(n^2) (quadratic space), etc.
- Best Case, Worst Case, and Average Case Complexity: Algorithms may behave differently depending on the input they receive. The best-case complexity represents the minimum amount of resources required when the algorithm receives the most favorable input. The worst-case complexity represents the maximum amount of resources required when the algorithm receives the least favorable input. The average-case complexity represents the expected amount of resources required when the algorithm receives inputs randomly distributed.
- Amortized Complexity: In some cases, an algorithm might have occasional expensive operations, but these are balanced out by many inexpensive operations. Amortized complexity considers the average cost per operation over a sequence of operations.
- Big Omega (Ω) and Big Theta (Θ) Notations: While big O notation provides an upper bound on the growth rate of an algorithm, big Omega notation provides a lower bound, indicating the best-case scenario. Big Theta notation, on the other hand, provides a tight bound, indicating both the upper and lower bounds, implying that the growth rate is asymptotically tight.
- Other Notations: Apart from big O, Omega, and Theta, there are other notations used to represent complexities, such as small o (little o) notation, which represents an upper bound that is not tight, and small omega (little omega) notation, which represents a lower bound that is not tight.
Group – “D”
Comprehensive Questions:
Attempts the question.
12. Define queue. List its applications. Write a java program to implement queue with singly linked list. Create necessary classes with requirement methods.
Ans: A queue is a linear data structure that follows the First-In-First-Out (FIFO) principle, where elements are inserted at the rear (enqueue) and removed from the front (dequeue). In a queue, elements are processed in the order they were added.
Applications of queues include:
- Job scheduling: Queues are used in operating systems to schedule tasks or processes in the order they were submitted.
- Breadth-first search (BFS): Queues are utilized in graph traversal algorithms like BFS to visit nodes in the order of their distance from the starting node.
- Print spooling: In computer systems, queues are used to manage printing tasks, ensuring that print jobs are processed in the order they were requested.
- Buffer management: Queues are used in network and operating systems to manage buffers for data transmission, ensuring that data is transmitted in the correct order.
- Resource allocation: Queues are employed in systems where resources need to be allocated fairly among competing processes or users.
Here’s a Java program to implement a queue using a singly linked list:
class Node {
int data;
Node next;
public Node(int data) {
this.data = data;
this.next = null;
}
}
class Queue {
private Node front;
private Node rear;
public Queue() {
this.front = null;
this.rear = null;
}
public boolean isEmpty() {
return front == null;
}
public void enqueue(int data) {
Node newNode = new Node(data);
if (isEmpty()) {
front = newNode;
rear = newNode;
} else {
rear.next = newNode;
rear = newNode;
}
}
public int dequeue() {
if (isEmpty()) {
throw new IllegalStateException("Queue is empty");
}
int removedData = front.data;
if (front == rear) {
front = null;
rear = null;
} else {
front = front.next;
}
return removedData;
}
public int peek() {
if (isEmpty()) {
throw new IllegalStateException("Queue is empty");
}
return front.data;
}
}
public class Main {
public static void main(String[] args) {
Queue queue = new Queue();
queue.enqueue(10);
queue.enqueue(20);
queue.enqueue(30);
System.out.println("Front element: " + queue.peek());
System.out.println("Dequeued element: " + queue.dequeue());
System.out.println("Dequeued element: " + queue.dequeue());
System.out.println("Front element after dequeuing: " + queue.peek());
}
}
