Scribd
Upload
14 views

Algorithm Design-1

Algo design notes

Uploaded by

its.harshitgoel
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
14 views

Algorithm Design-1

Algo design notes

Uploaded by

its.harshitgoel
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 3

1) Decide whether the below statement is True or False.

You must briefly justify your answer to 1+2=3


receive full credit.

f(N) = O(N2), where f(N) is defined to be the running time of the program:

A is an integer array of of size N


count_name_occurrences = 0
for x in A:
for y in A:
product = x * y
if binary_search(A, product):
count_name_occurrences += 1

2 Let A= (aij) be an m x n matrix and B=(bij) be an n x p matrix, both with real entries. For 2+2=4
computing the product matrix C = AB, use the algorithm implied by the definition of the matrix
product:

Find the worst case and average case complexity of this algorithm?
3 Given an array containing the digits 71808294, show how the order of the digits changes during 5+1=6
each step of quicksort (using the array-based quicksort choosing last element as the pivot).Show
the array after each swap. Mention the strategy used.

[7, 1, 8, 0, 8, 2, 9, 4]
[1, 0, 2, 4, 8, 8, 9, 7]
[1, 0, 2, 4, 8, 8, 9, 7]
[1, 0, 2, 4, 8, 8, 9, 7]
[0, 1, 2, 4, 7, 8, 8, 9]
[0, 1, 2, 4, 7, 8, 8, 9]

4 Given items as {value,weight} pairs {{130,40},{70,20},{90,10}}. The capacity of 2+4=6


knapsack=59. Find the maximum value output assuming items to be divisible.
a)290
b)160.25
c)254.25
d) 130.5

5 For the undirected, weighted graph given below, which of the following sequences of edges 4+4=8
represents a correct execution of Prim’s algorithm to construct a Minimum Spanning Tree?

Page 1 of 3
8

(i) (a, b), (d, f), (f, c), (g, i), (d, a), (g, h), (c, e), (f, h)
(ii) (c, e), (c, f), (f, d), (d, a), (a, b), (g, h), (h, f), (g, i)
(iii) (d, f), (f, c), (d, a), (a, b), (c, e), (f, h), (g, h), (g, i)
(iv) (h, g), (g, i), (h, f), (f, c), (f, d), (d, a), (a, b), (c, e)

Justify your answer..Give reasons why an option is correct or incorrect.


Find out the Minimum spanning tree of the graph above using Kruskal’s algorithm

6) 5+1+1
+1=8

Compute shortest paths between all pairs of vertices in the above graph, clearly
showing/explaining all intermediate steps.
Mention the algorithm, time complexity of the algorithm used.
Also specify the design strategy employed.

7 Consider the 3-SAT equation 3+1+2


S = (x ∨ ¬y ∨ z) ∧ (¬x ∨ z) ∧ (¬y ∨ ¬z) =6
Construct a Graph X from the above equation as per Clique problem rules. Identify the
maximum factor k, and possible satisfying assignment for above equation.

8) Below given is the backtracking algorithm idea for N Queens problem 6


“Place the queens one by one in different columns, starting from the leftmost column.
When we place a queen in a column, we check for clashes (no queens attack each other by
being in the same row, column or diagonal) with already placed queens. In the current
column, if we find a row for which there is no clash, we mark this row and column as part
of the solution. If we do not find such a row due to clashes, then we backtrack and return
false.”
Page 2 of 3
In the above process , how do you check for clashes? Complete the below code for the
function to perform the check to place the queen in a column.
The function clashcheck is called when "col" number of queens are already placed
in columns from 0 to col-1

bool clashcheck(int board[N][N], int row, int col)


{
int i, j;
<complete the code>>
return true;
}

Page 3 of 3

You might also like