1)Determine an LCS of {1,0,0,1,0,1,0,1} and {0,1,0,1,1,0,1,1,0}.
2)Give an algorithm to find the Longest common subsequence of sequences with lengths m,n respectively and also analyze their time complexities.
3)Give an algorithm to find the Longest common string of strings with lengths m,n respectively and also analyse their time complexities.
4)Give an O(n^2) time algorithm to find the longest monotonically increasing subsequence of a sequence of n numbers.
5)Give an O(n^2) time algorithm to find the longest monotonically increasing subsequence of a sequence of n numbers.
6)What is the difference between longest common subsequence and longest common substring
7)State few applications of Dynamic Programming.
Showing posts with label Data structure. Show all posts
Showing posts with label Data structure. Show all posts
Sunday, March 7, 2010
Stscks Queues and Linked lists
1)Explain how to implement two stacks in one array A[1,...,n] in such a way that neither stack overflows unless the total number of elements in both stacks together is n. The run time of PUSH and POP is O(1).
2)Explain how to implement a queue using two stacks. Analyse the running time of the queue operations.
3)Explain how to implement a stack using two queues. Analyse the running time of the stack operations.
4)Write four O(1)-time procedures to insert elements into and delete elements from both ends of a deque constructed from an array.
5)Implement a stack using a singly linked list L. The run time of PUSH and POP should be O(1).
6)Implement a queue using a singly linked list L. The run time of ENQUEUE and DEQUE should be O(1).
7)Can the dynamic-set operation INSERT be implemented on a singly linked list in O(1) time? What about DELETE?
8)Implement the dictionary operations INSERT,DELETE and SEARCH using singly linked,circular lists.What are the running times of the procedures?
9)Give a THETA(n)-time nonrecursive procedure that reverses a singly linked list of n elements. The procedure should use no more than constant storage beyond that needed for the list itself.
10)Write the operations of INSERT, DELETE and SEARCH in a linked list.Also, how do we reverse a linked list?
2)Explain how to implement a queue using two stacks. Analyse the running time of the queue operations.
3)Explain how to implement a stack using two queues. Analyse the running time of the stack operations.
4)Write four O(1)-time procedures to insert elements into and delete elements from both ends of a deque constructed from an array.
5)Implement a stack using a singly linked list L. The run time of PUSH and POP should be O(1).
6)Implement a queue using a singly linked list L. The run time of ENQUEUE and DEQUE should be O(1).
7)Can the dynamic-set operation INSERT be implemented on a singly linked list in O(1) time? What about DELETE?
8)Implement the dictionary operations INSERT,DELETE and SEARCH using singly linked,circular lists.What are the running times of the procedures?
9)Give a THETA(n)-time nonrecursive procedure that reverses a singly linked list of n elements. The procedure should use no more than constant storage beyond that needed for the list itself.
10)Write the operations of INSERT, DELETE and SEARCH in a linked list.Also, how do we reverse a linked list?
Counting Radix and Bubble sort
1)Illustrate the operation of Counting-Sort on the array A={6,0,2,0,1,3,4,6,1,3,2}
2)Illustrate the operation of Radix-Sort on the following list of English words: COW,DOG,SEA,RUG,ROW,MOB,RAT,BAT,BAR,EAR,TAR,DIG,BIG,TEA,NOW,FOX}.
3)Illustrate the operation of Bucket Sort on the array A={.81,.09,.13,.61,.43,.23,.98,.60,.75,.41}.
4)Explain how to sort n integers in the range 0 to n^2-1 in O(n) time.
5)Which of the following sorting algorithms are stable: insertion sort,merge sort,heapsort and quicksort? Give a simple scheme that makes any sorting algorithm stable. How much additional time and space does the scheme take?
6)What is the worst-case running time for the bucket-sort algorithm? What simple change to the algorithm preserves its linear expected running time and makes its worst-case running time O(nlgn)?
7)Describe an algorithm that, given n integers in the range 0 to k,preprocesses its input and then answers any query about how many of the n integers fall into a range [a...b] in O(1) time.The algorithm should use THETA(n+k) preprocessing time.
8)When are Radix and Bucket sorts used?
2)Illustrate the operation of Radix-Sort on the following list of English words: COW,DOG,SEA,RUG,ROW,MOB,RAT,BAT,BAR,EAR,TAR,DIG,BIG,TEA,NOW,FOX}.
3)Illustrate the operation of Bucket Sort on the array A={.81,.09,.13,.61,.43,.23,.98,.60,.75,.41}.
4)Explain how to sort n integers in the range 0 to n^2-1 in O(n) time.
5)Which of the following sorting algorithms are stable: insertion sort,merge sort,heapsort and quicksort? Give a simple scheme that makes any sorting algorithm stable. How much additional time and space does the scheme take?
6)What is the worst-case running time for the bucket-sort algorithm? What simple change to the algorithm preserves its linear expected running time and makes its worst-case running time O(nlgn)?
7)Describe an algorithm that, given n integers in the range 0 to k,preprocesses its input and then answers any query about how many of the n integers fall into a range [a...b] in O(1) time.The algorithm should use THETA(n+k) preprocessing time.
8)When are Radix and Bucket sorts used?
Hash Table
1)What is the expected time to search for an element in a hash table?
2)What is the worst case time for searching a element using hash table.
3)Demonstrate the insertion of the keys 5,28,19,15,20,33,12,17,10 into a hash table with collisions resolved by chaining.Let the table have 9 slots,and let the hash function be h(k)=k mod 9.
4)Suppose we use a hash function to hash m distinct keys into an array T of length m.Assuming simple uniform hashing,what is the expected number of collisions?
5)Suggest how storage for elements can be allocated and deallocated within the hash table itself by linking all unused slots into a free list.Assume that one slot can store a flag and either one element plus a pointer or two pointers.Does the free list need to be doublt linked,or does a singly linked free list suffice?
6)Suppose we wish to search a linked list of length n,where each element contains a key k along with a hash value h(k).Each key is a long character string.How might we take advantage of the hash values when searching the list for an element with a given key?
2)What is the worst case time for searching a element using hash table.
3)Demonstrate the insertion of the keys 5,28,19,15,20,33,12,17,10 into a hash table with collisions resolved by chaining.Let the table have 9 slots,and let the hash function be h(k)=k mod 9.
4)Suppose we use a hash function to hash m distinct keys into an array T of length m.Assuming simple uniform hashing,what is the expected number of collisions?
5)Suggest how storage for elements can be allocated and deallocated within the hash table itself by linking all unused slots into a free list.Assume that one slot can store a flag and either one element plus a pointer or two pointers.Does the free list need to be doublt linked,or does a singly linked free list suffice?
6)Suppose we wish to search a linked list of length n,where each element contains a key k along with a hash value h(k).Each key is a long character string.How might we take advantage of the hash values when searching the list for an element with a given key?
Saturday, March 6, 2010
Trees Revisited
)What are splay trees?How are they different from normal trees?
2)What are the key operations which characterize splay trees?
3)How are AVL rotations different from the operations performed in splay trees?
4)Show that if all the nodes in a splay tree are accessed sequentially,then the total access time is O(N),regardless of the initial tree?
5)Given 2 binary trees T1 and T2 with same set of nodes,show how you can transform one in to the other?
6)Give an algorithm to transform a binary tree T1 into another binary tree T2?
7)Give an algorithm to find all the elements between 2 keys K1 and K2 with K1<=K2
in a binary search tree T?
8)How do you convert the parent-child tree to a child-sibling tree(assume the tree is a binary tree)?
9)Two binary trees T1 and T2 are isomorphic if T1 can be transformed into T2 swapping left and right children of the nodes in T1.Give an algorithm to report whether 2 given binary trees are isomorphic.
10)Analyze the complexity of the above algorithm and report whether there exists a linear solution to it?
2)What are the key operations which characterize splay trees?
3)How are AVL rotations different from the operations performed in splay trees?
4)Show that if all the nodes in a splay tree are accessed sequentially,then the total access time is O(N),regardless of the initial tree?
5)Given 2 binary trees T1 and T2 with same set of nodes,show how you can transform one in to the other?
6)Give an algorithm to transform a binary tree T1 into another binary tree T2?
7)Give an algorithm to find all the elements between 2 keys K1 and K2 with K1<=K2
in a binary search tree T?
8)How do you convert the parent-child tree to a child-sibling tree(assume the tree is a binary tree)?
9)Two binary trees T1 and T2 are isomorphic if T1 can be transformed into T2 swapping left and right children of the nodes in T1.Give an algorithm to report whether 2 given binary trees are isomorphic.
10)Analyze the complexity of the above algorithm and report whether there exists a linear solution to it?
Subscribe to:
Posts (Atom)