Unit -I
2 marks
1. Define ADT.
2. Give the structure of Queue model.
3. What are the basic operations of Queue ADT?
4. What is Enqueue and Dequeue?
5. Give the applications of Queue.
6. What is the use of stack pointer?
7. What is an array?
8. Define ADT (Abstract Data Type).
9. Swap two adjacent elements by adjusting only the pointers (and not the data) using singly
linked list.
10. Define a queue model.
11. What are the advantages of doubly linked list over singly linked list?
12. Define a graph
13. What is a Queue?
14. What is a circularly linked list?
15. What is linear list?
16. How will you delete a node from a linked list?
17. What is linear pattern search?
18. What is recursive data structure?
19. What is doubly linked list?
Unit 1
part B
1. Explain the implementation of stack using Linked List.
2. Explain Prefix, Infix and postfix expressions with example.
3. Explain the operations and the implementation of list ADT.
4. Give a procedure to convert an infix expression a+b*c+(d*e+f)*g to postfix notation
5. Design and implement an algorithm to search a linear ordered linked list for a given
alphabetic key or name.
6. (a) What is a stack? Write down the procedure for implementing various stack
operations(8)
(b) Explain the various application of stack? (8)
7. (a) Given two sorted lists L1 and L2 write a procedure to compute L1_L2 using only the
basic operations (8)
(b) Write a routine to insert an element in a linked list (8)
8. What is a queue? Write an algorithm to implement queue with example.
Unit 2 and 3
part a
1.Explain Tree concept?
2. What is meant by traversal?
3. What is meant by depth first order?
4. What is In order traversal?
5. What is Pre order traversal?
6. What is Post order traversal?
7. Define Binary tree.
8. What is meant by BST?
9. Define AVL trees.
10. Give example for single rotation and double rotation.
11. Define Hashing.
12. Define Double Hashing.
13. What is meant by Binary Heap?
14. Mention some applications of Priority Queues.
15. Define complete binary tree.
16. How a binary tree is represented using an array? Give an example
17. A full node is a node with two children. Prove that the number of full nodes plus one is
equal to the number of leaves in a non empty binary tree.
18. Define (i) inorder (ii) preorder (iii) postorder traversal of a binary tree.
19. Suppose that we replace the deletion function, which finds, return, and removes the
minimum element in the priority queue, with find min, can both insert and find min be
implemented in constant time?
20. What is an expression tree?
1. Explain the representation of priority queue
2. Compare the various hashing Techniques.
3. List out the steps involved in deleting a node from a binary search tree.
4. What is binary heap?
5. Define Binary search tree.
6. List out the various techniques of hashing
7. Define hash function.
8. Show that maximum number of nodes in a binary tree of height H is 2H+1 – 1.
9. Define hashing.
10. Define AVL tree.
Unit 2and 3
part B
1. Explain the operation and implementation of Binary Heap.
2. Explain the implementation of different Hashing techniques.
3. Give the prefix, infix and postfix expressions corresponding to the tree given in figure.
4. (a) How do you insert an element in a binary search tree? (8)
(b) Show that for the perfect binary tree of height h containing2h+1-1 nodes, the sum of
the heights of the nodes 2h+1 -1-1(h+1). (8)
5. Given input {4371,1323,6173,4199,4344,9679,1989} and a hash function
h(X)=X(mod10), show the resulting:
(a) Separate chaining table (4)
(b) Open addressing hash table using linear probing (4)
(c) Open addressing hash table using quadratic probing (4)
(d) Open addressing hash table with second hash function h2(X) =7-(X mod 7). (4)
6. Explain in detail (i) Single rotation (ii) double rotation of an AVL tree.
7. Explain the efficient implementation of the priority queue ADT
8. Explain how to find a maximum element and minimum element in BST? Explain detail
about Deletion in Binary Search Tree?
1. (a) Construct an expression tree for the expression A+(B-C)*D+(E*F) (8)
(b) Write a function to delete the minimum element from a binary heap (8)
2. Write a program in C to create an empty binary search tree & search for an element X in
it. (16)
3. Explain in detail about Open Addressing (16)
4. Explain in detail insertion into AVL Trees (16)
5. Write a recursive algorithm for binary tree traversal with an example. (16)
6. Write an algorithm for initializing the hash table and insertion in a separate chaining (16)
Unit 4
part A
Define Graph.
2. What is meant by directed graph?
3. Give a diagrammatic representation of an adjacency list representation of a graph.
4. What is meant by topological sort?
5. What is meant by acyclic graph?
6. What is meant by Shortest Path Algorithm?
7. What is meant by Single-Source Shortest path problem?
8. What is meant by Dijkstra’s Algorithm?
9. What is minimum spanning tree?
10. Mention the types of algorithm.
11. Define NP- complete problems
12. What is space requirement of an adjacency list representation of a graph
13. What is topological sort?
14. What is breadth-first search?
15. Define minimum spanning tree
16. Define undirected graph
17. What is depth-first spanning tree
18. What is Bio connectivity?
19. What is Euler Circuit?
20. What is a directed graph?
21. What is meant by ‘Hamiltonian Cycle’?
22. Define (i)indegree (ii)outdegree
1. Explain the topological sort.
2. Define NP hard & NP complete problem.
3. Prove that the number of odd degree vertices in a connected graph should be even.
4. What is an adjacency list? When it is used?
5. What is an activity node of a graph?
6. Define Breadth First Search.
7. Define Depth First Search.
8. Define Minimum Spanning Tree.
9. Define Shortest Path of a graph.
10. Define Biconnectivity.
1. Define Graph.
2. What is meant by directed graph?
3. Give a diagrammatic representation of an adjacency list representation of a graph.
4. What is meant by topological sort?
5. What is meant by acyclic graph?
6. What is meant by Shortest Path Algorithm?
7. What is meant by Single-Source Shortest path problem?
8. What is meant by Dijkstra’s Algorithm?
9. What is minimum spanning tree?
10. Mention the types of algorithm.
11. Define NP- complete problems
12. What is space requirement of an adjacency list representation of a graph
13. What is topological sort?
14. What is breadth-first search?
15. Define minimum spanning tree
16. Define undirected graph
17. What is depth-first spanning tree
18. What is Bi connectivity?
19. What is Euler Circuit?
20. What is a directed graph?
21. What is meant by ‘Hamiltonian Cycle’?
22. Define (i)indegree (ii)outdegree
Unit 4
part B
1. Explain Prim’s & Kruskal‘s Algorithm with am example.
2. Describe Dijkstra’s algorithm with an example.
3. Explain how to find shortest path using Dijkstra’s algorithm with an example.
4. Explain the application of DFS.
5.Find a minimum spanning tree for the graph
using both Prim’s and Kruskal’s algorithms.
6. Explain in detail the simple topological sort pseudo code
7. Write notes on NP-complete problems
1. Formulate an algorithm to find the shortest path using Dijkstra’s algorithm and explain
with example. (16)
2. Explain the minimum spanning tree algorithms with an example. (16)
3. (a) Write short notes on Biconnectivity. (8)
(b) Write an algorithm for Topological Sort of a graph. (8)
4. Write and explain weighted and unweighted shortest path algorithm (16)
5. Explain the various applications of Depth First Search. (16)
1. Explain Prim’s & Kruskal‘s Algorithm with am example.
2. Describe Dijkstra’s algorithm with an example.
3. Explain how to find shortest path using Dijkstra’s algorithm with an example.
4. Explain the application of DFS.
5. Find a minimum spanning tree for the graph
using both Prim’s and Kruskal’s algorithms.
6. Explain in detail the simple topological sort pseudo code
7. Write notes on NP-complete problems
Unit V
part A
1. Define Program
2. Define Algorithm
3. Define Problem Definition Phase
4. What are the problem solving strategies?
5. Define Top Down Design.
6. What is the basic idea behind Divide & Conquer Strategy?
7. Define Program Verification.
8. Define Input & Output Assertion.
9. Define Symbolic Execution
10. Define Verification Condition
11. Define the qualities of good algorithm.
12. Define Computational Complexity.
13. What is O – notation?
14. What is Recursion? Explain with an example.
15. List out the performance measures of an algorithm.
1. Define Algorithm & Notion of algorithm.
2. What is analysis framework?
3. What are the algorithm design techniques?
4. How is an algorithm’s time efficiency measured?
5. Mention any four classes of algorithm efficiency.
6. Define Order of Growth.
7. State the following Terms.
(i) Time Complexity
(ii) Space Complexity
8. What are the various asymptotic Notations?
9. What are the important problem types?
10. Define algorithmic Strategy (or) Algorithmic Technique.
11. What are the various algorithm strategies (or) algorithm Techniques?
12. What are the ways to specify an algorithm?
13. Define Best case Time Complexity .
14. Define Worst case Time Complexity.
15. Define Average case time complexity.
16. What are the Basic Efficiency Classes.
17. Define Asymptotic Notation.
18. How to calculate the GCD value?
1. What is meant by algorithm? What are its measures?
2. Give any four algorithmic techniques.
3. Write an algorithm to find the factorial of a given number?
4. Define the worst case & average case complexities of an algorithm
5. What is divide & conquer strategy?
6. What is dynamic programming?
7. Write at least five qualities & capabilities of a good algorithm
8. Write an algorithm to exchange the values of two variables
9 Write an algorithm to find N factorial (written as n!) where n>=0.
Unit V
part B
1. (a) Explain in detail the types on analysis that can be performed on an algorithm (8)
(b) Write an algorithm to perform matrix multiplication algorithm and analyze the
same (8)
2. Design an algorithm to evaluate the function sin(x) as defined by the infinite series
expansion sin(x) = x/1!-x3/3! +x5/5!-x7/7! +……
3. Write an algorithm to generate and print the first n terms of the Fibonacci series where
n>=1 the first few terms are 0, 1, 1, 2, 3, 5, 8, 13.
4. Design an algorithm that accepts a positive integer and reverse the order of its digits.
5. Explain the Base conversion algorithm to convert a decimal integer to its
corresponding octal representation.
6. Explain in detail about Greedy algorithm with an example(16).
7. Explain in detail about Divide and conquer algorithm with an example also mark the difference between Greedy and divide and conquer algorithm.(16).
8. Describe the backtracking problem using knapsack problem .(16).
Your's friendly,
[MOHANRAM.G],
ADMIN...
0 comments:
Post a Comment