Recent questions tagged algorithms

Consider the following program that attempts to locate an element $x$ in an array $a[ ]$ using binary search. Assume $N 1$. The program is erroneous. Under what conditio...

Let $G$ be the directed, weighted graph shown in below figureWe are interested in the shortest paths from $A$.Output the sequence of vertices identified by the Dijkstra’s...

A complete, undirected, weighted graph $G$ is given on the vertex $\{0, 1,\dots, n -1\}$ for any fixed ‘n’. Draw the minimum spanning tree of $G$ ifthe weight of the edge...

A two dimensional array $A[1..n][1..n]$ of integers is partially sorted if $\forall i, j\in [1..n-1], A[i][j] < A[i][j+1] \text{ and } A[i][j] < A[i+1][j]$The smallest it...

Quick-sort is run on two inputs shown below to sort in ascending order taking first element as pivot$1, 2, 3, \dots n$$n, n-1, n-2, \dots, 2, 1$Let $C_1$ and $C_2$ be the...

The average number of key comparisons required for a successful search for sequential search on $n$ items is$\dfrac{n}{2}$$\dfrac{n-1}{2}$$\dfrac{n+1}{2}$None of the abov...

The recurrence relation$T(1) = 2$$T(n) = 3T (\frac{n}{4}) +n$has the solution $T(n)$ equal to$O(n)$$O (\log n)$$O\left(n^\frac{3}{4}\right)$ None of the above

Which of the following is false?$100n \log n=O(\frac{n\log n}{100})$$\sqrt{\log n} = O(\log\log n)$If $0 < x < y \text{ then } n^x = O\left(n^y\right)$$2^n \neq O\left(nk...

How many minimum spanning trees does the following graph have? Draw them. (Weights are assigned to edges).

Consider the following sequence of numbers:$$92, 37, 52, 12, 11, 25$$ Use Bubble sort to arrange the sequence in ascending order. Give the sequence at the end of each of ...

Consider the following Pascal function where $A$ and $B$ are non-zero positive integers. What is the value of $\text{GET}(3, 2)$?function GET(A,B:integer): integer; begin...

A language with string manipulation facilities uses the following operationshead(s): first character of a string tail(s): all but exclude the first character of a stringc...

Assume that $X$ and $Y$ are non-zero positive integers. What does the following Pascal program segment do?while X < Y do if X Y then X := X - Y else Y := Y - X; write(X)...

For merging two sorted lists of sizes $m$ and $n$ into a sorted list of size $m+n$, we require comparisons of$O(m)$$O(n)$$O(m+n)$$O(\log m + \log n)$

Merge sort uses:Divide and conquer strategyBacktracking approachHeuristic searchGreedy approach

In the following Pascal program segment, what is the value of X after the execution of the program segment?X := -10; Y := 20; If X Y then if X < 0 then X := abs(X) else ...

An array $A$ contains $n$ integers in locations $A[0], A , \dots A[n-1]$. It is required to shift the elements of the array cyclically to the left by $K$ places, where $1...

What function of $x$, $n$ is computed by this program?Function what(x, n:integer): integer: Var value : integer begin value := 1 if n 0 then begin if n mod 2 =1 then val...

Consider the following two functions:$g_1(n) = \begin{cases} n^3 \text{ for } 0 \leq n \leq 10,000 \\ n^2 \text{ for } n 10,000 \end{cases}$$g_2(n) = \begin{cases} n \te...

Which of the following statements is false?Optimal binary search tree construction can be performed efficiently using dynamic programmingBreadth-first search cannot be us...

Algorithm design technique used in quicksort algorithm is?Dynamic programmingBacktrackingDivide and conquerGreedy method

The recurrence relation that arises in relation with the complexity of binary search is:$T(n) = 2T\left(\frac{n}{2}\right)+k, \text{ k is a constant }$$T(n) = T\left(\fra...

Consider a complete undirected graph with vertex set $\{0, 1, 2, 3, 4\}$. Entry $W_{ij}$ in the matrix $W$ below is the weight of the edge $\{i, j\}$$$W=\begin{pmatrix} 0...

What is the value printed by the following C program?#include<stdio.h int f(int *a, int n) { if (n <= 0) return 0; else if (*a % 2 == 0) return *a+f(a+1, n-1); else retur...

Consider the recursive algorithm given below:procedure bubblesort (n); var i,j: index; temp : item; begin for i:=1 to n-1 do if A[i] A[i+1] then begin temp := A[i]; A[i]...

$\displaystyle \sum_{1\leq k\leq n} O(n)$, where $O(n)$ stands for order $n$ is:$O(n)$$O(n^2)$$O(n^3)$$O(3n^2)$$O(1.5n^2)$

What does the following code do?var a, b: integer; begin a:=a+b; b:=a-b; a:=a-b; end;exchanges $a$ and $b$doubles $a$ and stores in $b$doubles $b$ and stores in $a$leaves...

Consider the following function.Function F(n, m:integer):integer; begin if (n<=0) or (m<=0) then F:=1 else F:F(n-1, m) + F(n-1, m-1); end;Use the recurrence relation $\b...

Consider a graph whose vertices are points in the plane with integer co-ordinates $(x,y)$ such that $1 \leq x \leq n$ and $1 \leq y \leq n$, where $n \geq 2$ is an intege...

Let $T(n)$ be the function defined by $T(1) =1, \: T(n) = 2T (\lfloor \frac{n}{2} \rfloor ) + \sqrt{n}$ for $n \geq 2$.Which of the following statements is true?$T(n) = O...