Chapter 1 Hashing
1.1 Exercise
The goal of hashing is to produce a search that takes a) O(1) time
b) O(n2) time
Copyright By PowCoder代写 加微信 powcoder
c) O(log n) time
d) O(n log n) time 1.2 Exercise
Consider a hash table of size seven, with starting index zero, and a hash func- tion (3x + 4) mod 7. Assuming the hash table is initially empty, which of the following is the contents of the table when the sequence 1, 3, 8, 10 is inserted into the table using closed hashing? Note that ` ‘ denotes an empty location in the table.
a) 8, , , , , ,10 b) 1,8,10, , , ,3
c) 1, , , , , ,3 d) 1,10,8, , , ,3
1.3 Exercise
A hash table can store a maximum of 10 records, currently there are records in location 1, 3, 4, 7, 8, 9, 10. The probability of a new record going into location 2, with hash functions resolving collisions by linear probing is
CHAPTER 1.
a) 0.1 b) 0.6 c) 0.2 d) 0.5
1.4 Exercise
Which of the following scenarios leads to linear running time for a random search hit in a linear-probing hash table?
a) All keys hash b) All keys hash c) All keys hash d) All keys hash
1.5 Exercise
Given the following input (4322, 1334, 1471, 9679, 1989, 6171, 6173, 4199) and the hash function x mod 10, which of the following statements are true? (GATE CS 2004)
i. 9679, 1989, 4199 hash to the same value ii. 1471, 6171 has to the same value
iii. All elements hash to the same value
iv. Each element hashes to a dierent value
a) i only b) ii only
c) i and ii only d) iii and iv
1.6 Exercise
A hash table of length 10 uses open addressing with hash function h(k) = k mod 10, and linear probing. After inserting 6 values into an empty hash table, the table is as shown below.
to dierent indices
to an even-numbered index
to same index
to dierent even-numbered indices
Which one of the following choices gives a possible order in which the key values could have been inserted in the table?
a) 46,42,34,52,23,33 b) 34,42,23,52,33,46 c) 46,34,42,23,52,33 d) 42,46,33,23,34,52
1.7 Exercise
How many dierent insertion sequences of the key values using the same hash function and linear probing will result in the hash table given in Exercise 1.6 above?
a) 10 b) 20 c) 30 d) 40
4 CHAPTER 1. HASHING
Chapter 2 Disjoint Sets
2.1 Exercise
ArelationRonasetS,denedasx2yifandonlyify2x. Thisisanexample of?
a) reexive relation b) symmetric relation
c) transitive relation d) invalid relation
2.2 Exercise
What is the denition for Ackermann’s function? a) A(1,i)=i+1fori1
b) A(i,j)=i+jforij
c) A(i,j)=i+jfori=j
d) A(1,i)=i+1fori<1
2.3 Exercise
is one of the earliest forms of a self-adjustment strategy used in splay trees, skew heaps.
a) Union by rank
b) Equivalence function
CHAPTER 2.
DISJOINT SETS
c) Dynamic function d) Path compression
2.4 Exercise
What is the value for the number of nodes of rank r? a) N
b) N/2 c) N/2r
2.5 Exercise
In the Union/Find algorithm, the ranks of the nodes on a path will increase monotonically from?
a) leaf to root b) root to node
c) root to leaf
d) left subtree to right subtree
Heaps & HeapSort
3.1 Exercise
On which algorithm is heap sort based on? a) Fibonacci heap
b) Binary tree
c) Priority queue
3.2 Exercise
In what time can a binary heap be built? a) O(N)
b) O(NlogN) c) O(logN)
3.3 Exercise
In a binary max heap containing n numbers, the smallest element can be found in time
b) O(logn)
CHAPTER 3. HEAPS & HEAPSORT
c) O(loglogn) d) O(1)
3.4 Exercise
Consider the following heap after buildheap phase. What will be its correspond- ing array?
26 41 58 31
a) 26,53,41,97,58,59,31 b) 26,31,41,53,58,59,97 c) 26,41,53,97,31,58,59 d) 97,53,59,26,41,58,31
3.5 Exercise
Consider a binary max-heap implemented using an array. Which one of the fol- lowing array represents a binary max-heap?
a) 25,12,16,13,10,8,14 b) 25,12,16,13,10,8,14 c) 25,14,16,13,10,8,12 d) 25,14,12,13,10,8,16
3.6 Exercise
Suppose we are sorting an array of eight integers using heapsort, and we have just nished some heapify (either maxheapify or minheapify) operations. The array now looks like this: 16, 14, 15, 10, 12, 27, 28. How many heapify operations have been performed on root of heap?
c) 3 or 4 d) 5 or 6
3.7 Exercise
Consider a binary min heap containing n elements and every node is having de- gree 2 (i.e. full binary min heap tree). What is the probability of nding the largest element at the last level?
a) 1/2 b) 1
c) 1/n d) 1/2n
10 CHAPTER 3. HEAPS & HEAPSORT
Binary search tree & AVL trees
4.1 Exercise
What is the maximum height of an AVL tree with p nodes? a) p
b) logp c) logp/2
4.2 Exercise
Given an empty AVL tree, how would you construct AVL tree when a set of numbers are given without performing any rotations?
a) just build the tree with the given input
b) nd the median of the set of elements given, make it as root and construct
c) use trial and error
d) use dynamic programming to build the tree
4.3 Exercise
Which of the following is TRUE?
a) b) c) d)
CHAPTER 4. BINARY SEARCH TREE & AVL TREES
The cost of searching an AVL tree is Θ(log n) but that of a binary search tree is O(n)
The cost of searching an AVL tree is Θ(logn) but that of a complete binary tree is Θ(n log n)
The cost of searching a binary search tree is O(log n) but that of an AVL tree is Θ(n)
The cost of searching an AVL tree is Θ(n log n) but that of a binary search tree is O(n)
avltree leftrotation(avltreenode z):
avltreenode w = x=left x=left = w=right
w=right = x
x=height = max(Height(x=left),Height(x=right))+1
w=height = max(missing)+1 return w
4.4 Exercise
The worst case running time to search for an element in a balanced in a binary search tree with n 2n elements is
a) Θ(nlogn) b) Θ(n2n)
d) Θ(logn)
4.5 Exercise
Consider the below left-left rotation pseudo code where the node contains value pointers to left, right child nodes and a height value and Height() function returns height value stored at a particular node.
What is missing?
a) Height(w-left), x-height b) Height(w-right), x-height c) Height(w-left), x
d) Height(w-left)
Red Black trees
5.1 Exercise
What are the operations that could be performed in O(log n) time complexity by red-black tree?
a) insertion, deletion, nding predecessor, successor b) only insertion
c) only nding predecessor, successor d) for sorting
5.2 Exercise
Why do we impose restrictions like • root property is black
• every leaf is black
• children of red node are black • all leaves have same black
a) to get logarithm time complexity b) to get linear time complexity
c) to get exponential time complexity d) to get constant time complexity
14 CHAPTER 5. RED BLACK TREES
5.3 Exercise
Which of the following is an application of Red-black trees and why? a) used to store strings eciently
b) used to store integers eciently
c) can be used in process schedulers, maps, sets
d) for ecient sorting
5.4 Exercise
When it would be optimal to prefer Red-black trees over AVL trees? a) when there are more insertions or deletions
b) when more search is needed
c) when tree must be balanced
d) when log(nodes) time complexity is needed 5.5 Exercise
What is the below pseudo code trying to do, where pt is a node pointer and root pointer?
redblack(Node root , Node pt) :
if (root==NULL) return pt
if (pt.data < root.data)
root.left = redblack(root.left , pt);
root . left . parent = root
else if (pt.data > root.data) f
root.right = redblackt(root.right , pt) root . right . parent = root
return root
a) insert a new node b) delete a node
c) search a node
d) count the number of nodes
Algorithm Paradigms
6.1 Exercise
If a problem can be solved by combining optimal solutions to non-overlapping problems, the strategy is called
a) Dynamic programming b) Greedy
c) Divide and conquer d) Recursion
6.2 Exercise
What problem is not example of paradigm Divide and Conquer? a) Mergesort
b) Prim’s algorithm
c) Strassen’s algorithm
6.3 Exercise
Match the following with respect to algorithm paradigms:
CHAPTER 6. ALGORITHM PARADIGMS
• Merge sort
• Human coding
• Optimal polygon triangulation • Subset sum problem
i. Dynamic Programming ii. Greedy approach
iii. Divide and conquer iv. Back tracking
a) iiiiiiiv b) iiiiviii c) iiiiiiiv d) iiiiiiiv
6.4 Exercise
function fun(int n)
else return 2*fun(n+1);
print ( fun (2) )
Select the wrong statement from the following given options.
a) Dynamic programming is applicable when subproblems are not indepen- dent.
b) Divide and conquer algorithm does more work than necessary repeatedly solving the common subproblems
c) Dynamic programming solves each problem exactly once and saves the result into a table.
d) Longest path problem has optimal substructure property.
6.5 Exercise
Predict output of following pseudo code:
d) Runtime Error
Divide and Conquer
7.1 Exercise
What is complexity of T(n), if
T (n) = 2 T (n/2) + c n, T (1) = a = const
a) T(n) = O(n2)
b) T(n) = O(nlogn)
c) T(n)=O(nloglogn) d) T(n) = O(n)
7.2 Exercise
What does the below pseudo compute?
int x, y, m, n;
input: x, y;
/* x > 0 and y > 0 */
m=x;n=y; while (m != n)
m=m=n; else :
n = n = m;
print (n) ;
a) x + y using repeated subtraction
b) x mod y using repeated subtraction
18 CHAPTER 7. DIVIDE AND CONQUER
c) the greatest common divisor of x and y d) the least common multiple of x and y
7.3 Exercise
Consider the polynomial p(x) = a0 + a1x + a2x2 + a3x3, where ai 6= 0, for all i. The minimum number of multiplications needed to evaluate p on an input x is:
a) 3 b) 4 c) 6 d) 9
7.4 Exercise
Consider a situation where you don’t have function to calculate power (pow() function in Java) and you need to calculate xn where x can be any number and n is a positive integer. What can be the best possible time complexity of your power function?
b) O(nlogn)
c) O(loglogn) d) O(logn)
7.5 Exercise
Consider the problem of computing min-max in an unsorted array where min and max are minimum and maximum elements of array. Algorithm A1 can com- pute min-max in a1 comparisons without divide and conquer. Algorithm A2 can compute min-max in a2 comparisons by scanning the array linearly. What could be the relation between a1 and a2 considering the worst case scenarios?
a) a1
d) Depends on input
Master Theorem
8.1 Exercise
What is the result of the recurrences which fall under rst case of Master’s the- orem (let the recurrence be given by T(n) = aT (n/b) + f(n) and f(n) = nc)?
a) T(n)=Onlogba b) T(n) = O(nc logn)
c) T(n) = O(f(n)) d) T(n) = O(n2)
8.2 Exercise
What is the result of the recurrences which fall under third case of Master’s the- orem (let the recurrence be given by T(n) = aT(n/b) + f(n) and f(n) = nc)?
a) T(n)=Onlogba b) T(n) = O(nc logn)
c) T(n) = O(f(n)) d) T(n) = O(n2)
8.3 Exercise
Consider the following recurrence: T(n)=2Tpn+1, T(1)=1
Which one of the following is true?
a) T(n)=Θ(loglogn) b) T(n)=Θ(logn)
p c)T(n)=Θ( n)
d) T(n) = Θ(n)
8.4 Exercise
CHAPTER 8.
MASTER THEOREM
When n = 22k for some k 0, the recurrence relation
evaluates to:
8.5 Exercise
2T(n/2) + n,
if n<=3 then T(n)=n
else T(n) = T(n/3) + cn
The running time of an algorithm is represented by the following recurrence re- lation:
Which one of the following represents the time complexity of the algorithm? a) Θ(n)
b) Θ(nlogn) c) Θ(n2)
d) Θ(n2 log n) 8.6 Exercise
Consider the following recurrence:
T(n) = 8T (n − pn)/4 + n2
Which one of the following represents the time complexity of the algorithm?
b) Θ(nlogn)
d) Θ(n2 log n)
22 CHAPTER 8. MASTER THEOREM
procedure NotEfficient (c) x=c
while x > 0 do
y=y+1 x=x=1
The Loop Invariant
9.1 Exercise
Consider the following procedure:
State the loop invariant for the while loop on line 3. a) x
9.2 Exercise
What is the loop invariant for the while loop on line 4 in function gcd?
int gcd(int K, int M) f
int k = K; int m=M;
while (k != m) f if (k>m)
k = k = m; else
c) k mod m d) gcd(k,m)
9.3 Exercise
CHAPTER 9.
THE LOOP INVARIANT
Consider the bubbleSort algorithm.
void bubbleSort ( int arr [ ] )
int n = arr.length;
for (int i = 0; i < n=1; i++)
for (int j = 0; j < n=i=1; j++)
if (arr[j] > arr[j+1]) f
// swap arr[j+1] and arr[j]
int temp = arr[j];
arr[j] = arr[j+1]; arr[j+1] = temp;
int n, rev; rev = 0;
while (n > 0) f
rev = rev*10 + n%10; n = n/10;
At the end of i iteration right most n − i elements are sorted and in place a) True
9.4 Exercise
Consider the following program fragment for reversing the digits in a given in- teger to obtain a new integer. Let n = D1D2 . . . Dm.
The loop invariant condition at the end of the i-th iteration is: a) n = D1D2 …Dm−i and rev = DmDm−1 …Dm−i+1
b) n = Dm−i+1 …Dm−1Dm and rev = Dm−1 …D2D1
c) n 6= rev
d) n = D1D2 …Dm and rev = DmDm−1 …D2D1
for(int i=0; i<10; i++) 9.5 Exercise Consider the following procedure: State the loop invariant for the this cycle. a) j > 0
26 CHAPTER 9. THE LOOP INVARIANT
Chapter 10
Dynamic Programming
10.1 Exercise
Which of the following is (are) property (properties) of a dynamic programming problem?
a) Optimal substructure
b) Overlapping subproblems
c) Greedy approach
d) Both optimal substructure and overlapping subproblems
10.2 Exercise
If a problem can be broken into subproblems which are reused several times,
the problem possesses
a) Overlapping subproblems b) Optimal substructure
c) Memoization
10.3 Exercise
When dynamic programming is applied to a problem, it takes far less time as compared to other methods that don’t take advantage of overlapping subprob- lems.
a) True b) False
10.4 Exercise
CHAPTER 10. DYNAMIC PROGRAMMING
In dynamic programming, the technique of storing the previously calculated val- ues is called
a) Saving value property b) Storing value property
c) Memorization d) Mapping
10.5 Exercise
Which of the following problems is NOT solved using dynamic programming? a) 0/1 knapsack problem
b) Matrix chain multiplication problem
c) Edit distance problem
d) Fractional knapsack problem
10.6 Exercise
When a top-down approach of dynamic programming is applied to a problem, it usually
a) Decreases both, the time complexity and the space complexity
b) Decreases the time complexity and increases the space complexity c) Increases the time complexity and decreases the space complexity
d) Increases both, the time complexity and the space complexity
Chapter 11
Greedy Algorithms
11.1 Exercise
A greedy algorithm can be used to solve all the dynamic programming problems. a) True
11.2 Exercise
What is the objective of the knapsack problem? a) To get maximum total value in the knapsack b) To get minimum total value in the knapsack c) To get maximum weight in the knapsack
d) To get minimum weight in the knapsack
11.3 Exercise
Given items as value,weight pairs {{40, 20}, {30, 10}, {20, 5}}. The capacity of knapsack is 20. Find the maximum value output assuming items to be divisible.
a) 60 b) 80
c) 100 d) 40
30 CHAPTER 11. GREEDY ALGORITHMS
11.4 Exercise
What will be the cost of the code if character ci is at depth di and occurs at frequency fi?
a) b) c) d)
cifi fi di
11.5 Exercise
What is the running time of the Human encoding algorithm? a) O(C)
b) O(logC) c) O(ClogC) d) O(NlogC)
Chapter 12
Answer to all problems
Exercises 1.1, page 1
Answer: a)
Explanation: Time complexity is given by the big oh notation.
Exercises 1.2, page 1
Answer: b)
Explanation: A formula generates the hash, which helps to protect the security of the transmission from unauthorized users.
Exercises 1.3, page 1
Answer: b)
Explanation: Hashing is used to index and retrieve items in a database because it is easier to nd the item using the shortened hashed key than using the original value.
Exercises 1.4, page 2
Answer: c)
Explanation: If all keys hash to the same location then the i-th inserted key would need i lookups to be found. The probability of looking up i-th key is 1/n (since it’s random). If you know some probability it’s trivial to show that such lookups have linear time.
Exercises 1.5, page 2
Answer: c)
Explanation: Using given hash function h(x) = x mod 10
h(9679) = 9679%10 = 9 31
32 CHAPTER 12. ANSWER TO ALL PROBLEMS
h(1989) = 1989%10 = 9 h(4199) = 4199%10 = 9 h(1471) = 1471%10 = 1 h(6171) = 6171%10 = 1
As we can see, 9679, 1989 and 4199 hash to same value 9. Also, 1471 and 6171 hash to same value 1. Therefore, statement (i) and (ii) are correct which match with option c).
Exercises 1.6, page 2
Answer: c)
Explanation: We will check whether sequence given in option a) can lead to hash table given in question. Option a) inserts 46, 42, 34, 52, 23, 33 as:
• For key 46, h(46) is 46%10 = 6. Therefore, 46 is placed at 6th the hash table.
• For key 42, h(42) is 42%10 = 2. Therefore, 42 is placed at 2nd the hash table.
• For key 34, h(34) is 34%10 = 4. Therefore, 34 is placed at 4th the hash table.
• For key 52, h(52) is 52%10 = 2. However, index 2 is occupied Therefore, 52 is placed at 3rd index in the hash table. But in given hash table, 52 is placed at 5th index. Therefore, sequence in option A can’t generate hash table given in question.
In the similar way, we can check for other options as well which leads to answer as c).
Exercises 1.7, page 3
Answer: c)
Explanation: The rst key which is not at the index computed by hash func- tion is 52. It means index 2, 3 and 4 were already occupied and therefore, key 52 is placed at index 5.
The keys 42,23 and 34 are present at index 2,4, and 4 respectively. As these keys are at their correct position, their order of insertion does not matter. These 3 keys can be inserted in 3! = 6 ways. Therefore, the sequence will be any order of (42, 23, 34) followed by 52.
The next key which is not at the index computed by hash function is 33. It means indexes 3 to 6 were already occupied and key 33 is placed at index 7. Therefore, it is the last key to be inserted into hash table.
The key 46 is present at its correct position computed by hash function. Therefore, it can be inserted at any place in the sequence before 33. The sequence excluding 33 has 4 elements 42, 23, 34, 52 which create 5 positions for 46 (3 in-between and 2 corners). Total number of ways is: 6 5 = 30.
Exercises 2.1, page 5
Answer: b)
Explanation: A symmetric property in an equivalence relation is dened as x 2 y if and only if y 2 x.
Exercises 2.2, page 5
Explanation: The Ackermann’s function is dened as A(1, i) = i + 1 for i 1. This form in text grows faster and the inverse is slower.
Exercises 2.3, page 5
Answer: d)
Explanation: Path compression is one of the earliest forms of self-adjustment used in extremely important strategies using theoretical explanations.
Exercises 2.4, page 6
Answer: c)
Explanation: Each node of a rank r is the root of a subtree of at least 2r. Therefore, there are at most N/2r disjoint subtrees.
Exercises 2.5, page 6
Answer: a)
Explanation: One of the lemmas state that, in the Union/Find algorithm, the ranks of the nodes on a path will increase monotonically from leaf to root.
Exercises 3.1, page 7
Answer: c)
Explanation: Heap sort is based on the algorithm of priority queue and it gives the best sorting time.
Exercises 3.2, page 7
Answer: a)
Explanatio
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com