Q1.

- Define different types of Asymptotic notation with brief description. (3 marks)
- Find the time complexity of the following codes (2 marks)

i.

```
void func(int n)
{
int sum = 0;
int product = 1;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
printf("%d , %d\n", i, j);
}
}
}
```

ii.

```
int function(int n)
{
int i = 0;
if (n <= 0)
{
return 0;
}
else
{
i = random(n - 1);
printf("this\n");
return function(i) + function(n - 1 - i);
}
}
```

Q2.

- Convert the following infix expression to postfix using stack. A+(BC-(D/E^F)G)*H (5 marks)
- What is recursion? Write the algorithm to calculate n factorial. (5 marks)
- “Tracking of local variables at run time” is the application of Stack or Queue? Justify your answer. (5 marks)

Q3.

- What is the difference between direct and indirect recursion? (5 marks)
- Why Stack Overflow error occurs in recursion? (5 marks)
- In a circular queue, how do you increment the rear and front of the queue? Write the algorithm. (5 marks)

Q4.

- Write the pseudo code to implement a queue using stack. (5 marks)
- How are linked lists more efficient than arrays? Also mention the drawbacks of linked list (5 marks)
- What would be the asymptotic time complexity to add a node at the end of singly linked list, if the pointer is initially pointing to the head of the list? Analyze your answer. (5 marks)

Q5.

- Write a pseudo code for inserting an element in a doubly linked list at the random position. (6 marks)
- What are the advantages of Circular Queue over normal Queue. (4 marks)
- Write the algorithm that gives recursive solution to Tower of Hanoi problem. What is the number of moves required to solve Tower of Hanoi problem for k disks? (5 marks)