Solve your IGNOU Doubts
Solve your IGNOU Doubts
Question:

3-CNF SAT

See Answer →
Question:

What are NP-Hard and NP-Complete problem? What is the role of reduction? Explain with the help of an example.

See Answer →
Question:

Define P and NP class of Problems with the help of examples. How are P class of problem different from NP class of Problems.

See Answer →
Question:

What are decision problems and Optimisation problems? Differentiate the decision problems and Optimisation problems with the help of at least two problem statements of each

See Answer →
Question:

Consider the following Graph:

Image ignouassignments-ignouacademy-com--p-doubts-57977

Figure 1: Graph for Problem 3(a) and 3(b)

a) Write the Kruskal’s algorithm and Prim’s algorithm to find the minimum cost
spanning tree of the graph given in Figure 1. Show all the steps of computation.
Also, compute the time complexity of both the algorithms.
b) In the Figure 1, find the shortest path from the vertex ‘a’ using Dijkstra’s shortest
path algorithm. Show all the steps of computation. Also, find the time complexity
of the algorithm.
c) What is dynamic programming? What is the principle of Optimality? Use the
dynamic programming approach to find the optimal sequence of chain
multiplication of the following matrices:

Matrix Dimension
A1 5 x 10
A2 10 x 20
A3 20 x 15
A4 15 x 8
A5 8 x 10

d) Make all the possible Binary Search Trees for the key values 25, 50, 75.
e) Explain the Knuth Morris Pratt algorithm for string matching. Use this algorithm
to find a pattern “algo” in the Text “From algae to algorithms”. Show all the steps.
What is the time complexity of this algorithm

See Answer →
Question:

What is the use of Topological sorting? Write and explain the Topological sorting algorithm. Also, compute the time complexity for the topological sorting algorithm.

See Answer →
Question:

Explain the divide and conquer apprach of multiplying two matrices of large size. Also, explain the Strassen’s matric multiplication algorithm. Find the time complexity of both these approaches.

See Answer →
Question:

Expalin the Partition procedure of the Quick Sort algorithm. Use this procedure and quick sort algorithm to sort the following array of size 8: [12, 9, 17, 15, 23, 19, 16, 24]. Compute the worst case and best case complexity of Quick sort algorithm

See Answer →
Question:

What is the purpose of using Huffman Codes? Explain the steps of building a huffman tree. Design the Huffman codes for the following set of characters and their frequencies: a:15, e:19, s:5, d:6, f:4, g:7, h:8, t:10.

See Answer →
Question:

What is a Greedy Approach to Problem-solving? Formulate the fractional Knapsack Problem as an optimisation problem and write a greedy algorithm to solve this problem. Solve the following fractional Knapsack problem using this algorithm. Show all the steps. Suppose there is a knapsack of capacity 15 Kg and 6 items are to packed in it. The weight and profit of the items are as under:

(p1, p2,…, p6) = (3, 2, 4, 5, 1, 6)

(w1, w2,…, w6) = (2, 1, 2, 1, 5, 1)

See Answer →
Question:

What is a recurrence relation? Solve the following recurrence relations using the Master’s method

a. T(n) = 8T\left ( \frac{n}{2} \right ) + n^2

b. T(n) = T\left ( \frac{3n}{4} \right ) + 1

See Answer →
Question:

Write and explain the linear search algorithm and discuss its best and worstcase time complexity. Show the working of the linear search algorithm for the data: 12, 11, 3, 9, 15, 20, 18, 19, 13, 8, 2, 1, 16.

See Answer →
Question:

Explain binary exponentiation for computing the value 519. Write the right-toleft binary exponentiation algorithm and show its working for the exponentiation 519. Also, find the worst-case complexity of this algorithm

See Answer →
Question:

State and explain the theorems for computing the bounds O, Ω and Θ. Apply these theorem to find the O-notation, Ω-notation and Θ-notation for the function: See Answer →

Question:

Using Horner's rule, evaluate the polynomial p(x)= 2x5 -5x4 -3x2+15 at x=2. Analyse the computation time required for polynomial evaluation using Horner’s rule against the Brute force method.

See Answer →
Question:

Differentiate between Polynomial-time and exponential-time algorithms. Give an example of one problem each for these two running times.

See Answer →
Question:

Develop an efficient algorithm to find a list of prime numbers from 100 to 1000

See Answer →
Question:

What is a Mobile Adhoc Network? What are its advantages and disadvantages?

See Answer →
Question:

What is a Virtual Cloud Network? What are its advantages and disadvantages?

See Answer →
Question:

List the features of any two Programming Languages that can be used to develop Mobile Applications.

See Answer →
IGNOU NEWS
Assignment Submission Last Date Extended Till 30 June 2026 Click Here★★★IGNOU June 2026 TEE Date Sheet Released Click Here★★★
Top
📞
Call Support Instant phone assistance
→
🟢
WhatsApp Chat Fast live messaging
→
Email Us Business enquiries & support
→