Monday, 30 March 2015
ADVANCED DATA STRUCTURES & ALGORITHMS
Question Bank for Units 1, 2 and 3
PART - A
1 Differentiate Recursion and Iteration
2 Write an algorithm for Insertion sort
3 Write an algorithm for Selection sort
4 Write a Recursive algorithm to count the number of nodes in a Binary Tree
5 Write a Recursive algorithm to sum the values of keys in a Binary Tree
6 Define computational problem and Algorithm
7 Define Abstract Data Type with an Example
8 Define Time Complexity and Space Complexity
9 Write an algorithm to find the Maximum among N integers
10 What do you mean by Loop Invariance?
11 Differentiate 'More of Input ' and 'More of output' iterative algorithms with an example for each
12 Write an iterative algorithm to search an element among N sorted elements
13 You are given a graph G. You need to colour the colour the vertices such that no two adjacent
vertices should be coloured
with the same colour. Which traversal is applicable?
14 Write a recursive algorithm to solve Tower of Hanoi Problem
15 What is a Stack Frame?
16 Define Strong Induction.
17 Write an algorithm to find the second smallest number among N numbers without sorting them
18 Write a recursive algorithm to calculate bN, where b and N are positive integers
19 Write an algorithm to print the keys in Binary Search Tree in ascending order
20 Write a Recursive algorithm to find the height of a Binary Tree
21 Write a Recursive algorithm to find the maximum and minimum keys in a Binary Search Tree
22 Write a Recursive algorithm to count the number of leaves in a Binary Tree
23 Write a Recursive algorithm that takes a Binary Tree T as input and returns a copy of T
24 Write an algorithm to search a Key K in a BST
25 Define Optimization problem with 2 examples
26 Write a Generic Algorithm to reach all the nodes from a given source s in a directed Graph G.
27 What is Breadth First Search and Depth First Search?
28 Define Topological Sort.
29 Justify why Dijkstra's algorithm cannot be used in a graph with negative edges
30 What is a Priority Queue?
31 What do you mean by Heap Order Property?
32 List down the elements of Dynamic Programming
33 Differentiate Divide and Conquer and Dynamic Programming
34 Brief Backtracking Technique
35 What is Pruning in Backtracking?
36 Define Satisfiability problem
37 Define Sum of Subsets Problem
38 Define Chromatic Number of a Graph
39 Define Bipartite Graph
40 What do you mean by Tail recursion?
PART B
1 Write a recursive algorithm to find the kth smallest element among N elements.
2 Write an algorithm to sort N keys in descending order using Merge Sort. Write the recurrence
the algorithm and solve it to arrive at Asymptotic Notation.
3 Write an algorithm to sort N keys in ascending order using Quick Sort. Write the recurrence
algorithm and solve it to arrive at Asymptotic Notation for Best case and Worst Case.
4 Write an algorithm to search a key K in a N * N Matrix in which each row column is sorted in
ascending order.
What is the time complexity of your algorithm?
5 Write an algorithm to multiply to long integers M and N. What is the time complexity of your
6 Compare in detail about Strassen Matrix Multiplication with Brute Force Matrix Multiplication.
Sole the recurrence
relation for Strassen Multiplication.
7 Write and Solve Ackermann's Function.
8 Write iterative algorithm to traverse Binary Trees.
9 Write recursive algorithm to traverse Binary Trees.
10 Write an algorithm that returns TRUE if a given Binary Tree is a Binary Search Tree. FALSE
11 Write an algorithm to evaluate a given expression represented a Tree
12 Write an algorithm to swap the left and right children of a given Binary Tree.
13 Write complete HeapSort algorithm.
14 Write Dijkstra's algorithm to calculate Single Source Shortest Path on a directed Graph
15 Write an algorithm for Breadth First Search in a graph G
16 Write a recursive algorithm for Depth First Search on a graph G
17 Write complete Topological Sort algorithm
18 Write a backtracking algorithm to solve N Queen Problem and apply to N = 6
19 Write an algorithm to calculate the Longest Common Subsequence
20 Write an algorithm to parenthesize a chain of N matrices
21 Write Davis Putnam algorithm to solve Satifiability problem
22 Write short notes on P, NP, NP-Complete, and NP-Hard Problems with two examples for each
class of problems
PART - A
1 Differentiate Recursion and Iteration
2 Write an algorithm for Insertion sort
3 Write an algorithm for Selection sort
4 Write a Recursive algorithm to count the number of nodes in a Binary Tree
5 Write a Recursive algorithm to sum the values of keys in a Binary Tree
6 Define computational problem and Algorithm
7 Define Abstract Data Type with an Example
8 Define Time Complexity and Space Complexity
9 Write an algorithm to find the Maximum among N integers
10 What do you mean by Loop Invariance?
11 Differentiate 'More of Input ' and 'More of output' iterative algorithms with an example for each
12 Write an iterative algorithm to search an element among N sorted elements
13 You are given a graph G. You need to colour the colour the vertices such that no two adjacent
vertices should be coloured
with the same colour. Which traversal is applicable?
14 Write a recursive algorithm to solve Tower of Hanoi Problem
15 What is a Stack Frame?
16 Define Strong Induction.
17 Write an algorithm to find the second smallest number among N numbers without sorting them
18 Write a recursive algorithm to calculate bN, where b and N are positive integers
19 Write an algorithm to print the keys in Binary Search Tree in ascending order
20 Write a Recursive algorithm to find the height of a Binary Tree
21 Write a Recursive algorithm to find the maximum and minimum keys in a Binary Search Tree
22 Write a Recursive algorithm to count the number of leaves in a Binary Tree
23 Write a Recursive algorithm that takes a Binary Tree T as input and returns a copy of T
24 Write an algorithm to search a Key K in a BST
25 Define Optimization problem with 2 examples
26 Write a Generic Algorithm to reach all the nodes from a given source s in a directed Graph G.
27 What is Breadth First Search and Depth First Search?
28 Define Topological Sort.
29 Justify why Dijkstra's algorithm cannot be used in a graph with negative edges
30 What is a Priority Queue?
31 What do you mean by Heap Order Property?
32 List down the elements of Dynamic Programming
33 Differentiate Divide and Conquer and Dynamic Programming
34 Brief Backtracking Technique
35 What is Pruning in Backtracking?
36 Define Satisfiability problem
37 Define Sum of Subsets Problem
38 Define Chromatic Number of a Graph
39 Define Bipartite Graph
40 What do you mean by Tail recursion?
PART B
1 Write a recursive algorithm to find the kth smallest element among N elements.
2 Write an algorithm to sort N keys in descending order using Merge Sort. Write the recurrence
the algorithm and solve it to arrive at Asymptotic Notation.
3 Write an algorithm to sort N keys in ascending order using Quick Sort. Write the recurrence
algorithm and solve it to arrive at Asymptotic Notation for Best case and Worst Case.
4 Write an algorithm to search a key K in a N * N Matrix in which each row column is sorted in
ascending order.
What is the time complexity of your algorithm?
5 Write an algorithm to multiply to long integers M and N. What is the time complexity of your
6 Compare in detail about Strassen Matrix Multiplication with Brute Force Matrix Multiplication.
Sole the recurrence
relation for Strassen Multiplication.
7 Write and Solve Ackermann's Function.
8 Write iterative algorithm to traverse Binary Trees.
9 Write recursive algorithm to traverse Binary Trees.
10 Write an algorithm that returns TRUE if a given Binary Tree is a Binary Search Tree. FALSE
11 Write an algorithm to evaluate a given expression represented a Tree
12 Write an algorithm to swap the left and right children of a given Binary Tree.
13 Write complete HeapSort algorithm.
14 Write Dijkstra's algorithm to calculate Single Source Shortest Path on a directed Graph
15 Write an algorithm for Breadth First Search in a graph G
16 Write a recursive algorithm for Depth First Search on a graph G
17 Write complete Topological Sort algorithm
18 Write a backtracking algorithm to solve N Queen Problem and apply to N = 6
19 Write an algorithm to calculate the Longest Common Subsequence
20 Write an algorithm to parenthesize a chain of N matrices
21 Write Davis Putnam algorithm to solve Satifiability problem
22 Write short notes on P, NP, NP-Complete, and NP-Hard Problems with two examples for each
class of problems
Subscribe to:
Posts (Atom)