Dhruv BadayaMay 261 minIn the following two-ply game tree, the terminal nodes show the utility values computed by the utility function. Use the Minimax algorithm to compute the utility values for other nodes in the given...
Dhruv BadayaMay 261 minWrite a context-free grammar that can accept the sentence: "Ram hit the ball".
Dhruv BadayaMay 261 minGiven an array A of n integers, you need to find the maximum sum of any contiguous subarray. For instance, the maximum sum of any contiguous subarray in the array -1, 2, 3, -2, 5, -6, 7, -8 is 9...
Dhruv BadayaMay 261 minSuppose we perform a sequence of stack operations on a stack whose size never exceeds k. After every k operations, we make a copy of the entire stack for backup purposes. Show that the cost of n st...
Dhruv BadayaMay 261 minWhat is the minimum number of leaves in the decision tree for a comparison sort? Use this observation to derive a lower bound on the number of comparisons performed by a comparison sort in the wors...
Dhruv BadayaMay 261 minWhat is the smallest possible depth of a leaf in a decision tree for a comparison sort? Name a sorting technique to which this smallest depth would correspond.
Dhruv BadayaMay 261 minLet G = (V,E) be a directed unweighted graph. Given two vertices s and t in V, what is the time required to determine if there exists at least one s-t path in G? Can we use the DFS algorithm to fin...
Dhruv BadayaMay 262 minA student was asked to sort a list of n numbers in decreasing order. The student writes an algorithm that works iteratively as follows. In every iteration, the following two steps are done...
Dhruv BadayaMay 261 minFor each of the following sorting algorithms, merge sort and insertion sort, discuss whether or not it is (i) stable and (ii) in-place
Dhruv BadayaMay 262 minConsider the scheduling problem wherein you are given a single resource and a set of requests having deadlines. A request is said to be late be late if it misses the deadline. Your goal is to minim...
Dhruv BadayaMay 261 minShow that in any subtree of a max-heap, the root of the subtree contains the largest value occurring anywhere in that subtree.
Dhruv BadayaMay 261 minWe are given a weighted graph G in which edge weights are not necessarily distinct. Can graph G have more than one minimum spanning tree (MST)? If yes, give an example, else justify.
Dhruv BadayaMay 261 minWhy is the worst-case running time for bucket sort θ(n²)? What changes would you make to the algorithm so that its worst-case running time becomes O(nlgn)?
Dhruv BadayaMay 251 minSpecify whether the above graph is bipartite or not. If yes, give the partition, else justify.
Dhruv BadayaMay 251 minLet G be a tree graph. Further, let A and B be the trees produced by performing BFS and DFS respectively on G. Can A and B be different trees? Why or why not?
Dhruv BadayaMay 251 minHow many topological orderings does the following graph have? Specify all of them.
Dhruv BadayaMay 251 minCan dynamic programming be applied to all optimization problems? Why or why not?
Dhruv BadayaMay 251 minWill the greedy strategy with the greedy parameter being value per unit weight of the items yield an optimal solution for the 0-1 knapsack problem? Justify.
Dhruv BadayaMay 251 minA team of explorers is visiting the Sahara desert. Due to the extreme heat, they need to stay hydrated and have brought n bottles of different sizes to carry water. After travelling a few kilometre...
Dhruv BadayaMay 251 minDiscuss the running time of the following snippet of code: count=0 for (i=l, i<=n, i++) for (j=1, j<=n, j=2*j) count++