Dynamic Programming

Let $G(V, E)$ be an undirected, edge-weighted graph with integer weights. The weight of a path is the sum of the weights of the edges in that path. The length of a path is the numb...

Let A be an array containing integer values. The distance of A is defined as the minimum number of elements in A that must be replaced with another integer so that the resulting ar...

Let $A$ be an array containing integer values. The distance of $A$ is defined as the minimum number of elements in $A$ that must be replaced with another integer so that the result...

Define R n to be the maximum amount earned by cutting a rod of length n meters into one or more pieces of integer length and selling them. For i > 0, let p[i] denotes the selling p...

Assume that multiplying a matrix $${G_1}$$ of dimension $$p \times q$$ with another matrix $${G_2}$$ of dimension $$q \times r$$ requires $$pqr$$ scalar multiplications. Computing...

Let $${A_1},\,{A_2},\,{A_3}$$ and $${A_4}$$ be four matrices of dimensions $$10 \times 5,\,5 \times 20,\,20 \times 10,$$ and $$10 \times 5,$$ respectively. The minimum number of sc...

The Floyd-Warshall algorithm for all-pair shortest paths computation is based on

Let $${A_1},{A_2},{A_3},$$ and $${A_4}$$ be four matrices of dimensions $$10 \times 5,\,\,5 \times 20,\,\,20 \times 10,$$ and $$10 \times 5,\,$$ respectively. The minimum number of...

Given below are some algorithms, and some algorithm design paradigms. GROUP 1 GROUP 2 1. Dijkstra's Shortest Path i. Divide and Conquer 2. Floyd-Warshall algorithm to compute all p...

Match the following: List 1 (P) Prim’s algorithm for minimum spanning tree (Q) Floyd-Warshall algorithm for all pairs shortest paths (R) Mergesort (S) Hamiltonian circuit List 2 (i...

Four matrices M 1 , M 2 , M 3 and M 4 of dimensions p $$\times$$ q, q $$\times$$ r, r $$\times$$ s and s $$\times$$ t respectively can be multiplied is several ways with different...

An algorithm to find the length of the longest monotonically increasing sequence of numbers in an array A[0:n−1] is given below. Let L i , denote the length of the longest monotoni...

Four matrices $${M_1},\,\,\,{M_2},\,\,\,{M_3}$$ and $${M_4}$$ of dimensions $$p\,\,x\,\,q,\,\,\,\,\,q\,\,x\,\,e,\,\,\,\,\,r\,\,x\,\,s$$ and $$\,\,\,\,s\,\,x\,\,t$$ respectively can...

A sub-sequence of a given sequence is just the given sequence with some elements (possibly none or all) left out. We are given two sequences X[m] and Y[n] of lengths m and n, respe...

A sub-sequence of a given sequence is just the given sequence with some elements (possibly none or all) left out. We are given two sequences X[m] and Y[n] of lengths m and n, respe...

The subset-sum problem is defined as follows. Given a set of n positive integers, S = {a 1 ,a 2 ,a 3 ,…,a n } and positive integer W, is there a subset of S whose elements sum to W...

Consider the following C functions: int f1(int n){ if(n == 0 || n == 1){ return n; } return (2 * f1(n - 1) + 3 * f1(n - 2)); } int f2(int n){ int i; int X[N], Y[N], Z[N]; X[0] = Y[...

The subset-sum problem is defined as follows. Given a set of n positive integers, S = {a 1 ,a 2 ,a 3 ,…,a n } and positive integer W, is there a subset of S whose elements sum to W...

Consider the following C functions: int f1(int n){ if(n == 0 || n == 1){ return n; } return (2 * f1(n - 1) + 3 * f1(n - 2)); } int f2(int n){ int i; int X[N], Y[N], Z[N]; X[0] = Y[...

Consider the following C - function: double foo(int n){ int i; double sum; if(n == 0) return 1.0; sum = 0.0; for (i = 0; i < n; i++){ sum += foo(i); } return sum; } Suppose we modi...

Let G = (V, E) be a directed graph with n vertices. A path from v i to v j in G is sequence of vertices (v i , v i +1, ……., v j ) such that (v k , v k +1) ∈ E for all k in i throug...

Which one of the following algorithm design techniques is used in finding all pairs of shortest distances in a graph?

Which one of the following statements is false?

Obtain the optimal binary search tree with equal probabilities for the identifier set (a 1 , a 2 , a 3 ) = ( if, stop, while)

Match the pairs in the following: List - I (a) Straseen's matrix multiplication algorithm (b) Kruskal's minimum spanning tree algorithm (c) Bioconnected components algorithm (d) Fl...