# IGNOU MMTE-002 Solved Assignment 2024 | M.Sc. MACS

Solved By – Narendra Kr. Sharma – M.Sc (Mathematics Honors) – Delhi University

365.00

Access via our Android App Only

Details For MMTE-002 Solved Assignment

## IGNOU MMTE-002 Assignment Question Paper 2024

mmte-002-solved-assignment-2024-b772e899-b2ce-40f7-8686-2afea878ebb1

# mmte-002-solved-assignment-2024-b772e899-b2ce-40f7-8686-2afea878ebb1

MMTE-002 Solved Assignment 2024
1. a) The maximum subsequence sum problem is defined as follows: If ${a}_{1},{a}_{2},\dots ,{a}_{n}$${a}_{1},{a}_{2},\dots ,{a}_{n}$a_(1),a_(2),dots,a_(n)a_1, a_2, \ldots, a_n${a}_{1},{a}_{2},\dots ,{a}_{n}$ are in $\mathbf{Z}$$\mathbf{Z}$Z\mathbf{Z}$\mathbf{Z}$, find the maximum value $\sum _{k=i}^{j}{a}_{i}$$\sum _{k=i}^{j} {a}_{i}$sum_(k=i)^(j)a_(i)\sum_{k=i}^j a_i$\sum _{k=i}^{j}{a}_{i}$, for all $\mathrm{i},\mathrm{j},1\le i\le j\le n$$\mathrm{i},\mathrm{j},1\le i\le j\le n$i,j,1 <= i <= j <= n\mathrm{i}, \mathrm{j}, 1 \leq i \leq j \leq n$\mathrm{i},\mathrm{j},1\le i\le j\le n$. We assume that the answer is 0 if all the ${a}_{i}$${a}_{i}$a_(i)a_i${a}_{i}$ are negative or if the sum is empty. The following algorithm finds a solution to the problem. Here, we assume that ${a}_{i}\text{}\mathrm{s}$${a}_{i}\text{}\mathrm{s}$a_(i)sa_i \mathrm{~s}${a}_{i}\text{}\mathrm{s}$ are stored in the array $\mathrm{A}$$\mathrm{A}$A\mathrm{A}$\mathrm{A}$.
State precisely a loop invariant for the for loop in line 2-8. Prove that your loop invariant holds and hence conclude that the algorithm works.
b) Analyse the algorithm and find an upper bound for the run time of the above algorithm.
2) a) With the help of an example, explain the following:
i) Algorithm.
ii) Input and output for an algorithm.
iii) Running time of an algorithm.
b) Using Fig. 7.1 in page 147 of the book as the model, illustrate the operation of PARTITION on the array $A=\left\{7,6,9,8,17,12,5,11,13,14,12\right\}$$A=\left\{7,6,9,8,17,12,5,11,13,14,12\right\}$A={7,6,9,8,17,12,5,11,13,14,12}A=\{7,6,9,8,17,12,5,11,13,14,12\}$A=\left\{7,6,9,8,17,12,5,11,13,14,12\right\}$
3)
a) For the set of keys $\left\{3,7,9,4,6,8,12\right\}$$\left\{3,7,9,4,6,8,12\right\}${3,7,9,4,6,8,12}\{3,7,9,4,6,8,12\}$\left\{3,7,9,4,6,8,12\right\}$ draw binary search trees of height $2,3,4,5$$2,3,4,5$2,3,4,52,3,4,5$2,3,4,5$ and 6.
b) Using Fig. 6.3 in page 134 of the book as a model, illustrate the operation of BUILD-MAX-HEAP on the array $A=\left\{6,7,4,9,13,11,8,12,5\right\}$$A=\left\{6,7,4,9,13,11,8,12,5\right\}$A={6,7,4,9,13,11,8,12,5}A=\{6,7,4,9,13,11,8,12,5\}$A=\left\{6,7,4,9,13,11,8,12,5\right\}$.
1. a) Show the results of inserting the keys
$Q,S,F,K,H,L,F,T,V,P,M,R,N,W,A$$Q,S,F,K,H,L,F,T,V,P,M,R,N,W,A$Q,S,F,K,H,L,F,T,V,P,M,R,N,W,AQ, S, F, K, H, L, F, T, V, P, M, R, N, W, A$Q,S,F,K,H,L,F,T,V,P,M,R,N,W,A$
in order into an empty B-tree with minimum degree 2. Only draw the configurations of the tree just before some node must split, and also draw the final configuration.
b) Suppose the Connected-Components is run on the undirected graph $G=\left(V,E\right)$$G=\left(V,E\right)$G=(V,E)G=(V, E)$G=\left(V,E\right)$, where $V=\left\{1,2,3,4,5,6,7,8,9\right\}$$V=\left\{1,2,3,4,5,6,7,8,9\right\}$V={1,2,3,4,5,6,7,8,9}V=\{1,2,3,4,5,6,7,8,9\}$V=\left\{1,2,3,4,5,6,7,8,9\right\}$ and the edges in $E\left(V\right)=\left\{{e}_{1}=\left(1,3\right),{e}_{2}=\left(2,5\right),{e}_{3}=\left(3,6\right),{e}_{4}=$$E\left(V\right)=\left\{{e}_{1}=\left(1,3\right),{e}_{2}=\left(2,5\right),{e}_{3}=\left(3,6\right),{e}_{4}=\right\$E(V)={e_(1)=(1,3),e_(2)=(2,5),e_(3)=(3,6),e_(4)=:}E(V)=\left\{e_1=(1,3), e_2=(2,5), e_3=(3,6), e_4=\right.$E\left(V\right)=\left\{{e}_{1}=\left(1,3\right),{e}_{2}=\left(2,5\right),{e}_{3}=\left(3,6\right),{e}_{4}=$ $\left(5,8\right),{e}_{5}=\left(5,9\right),{e}_{6}=\left(6,9\right),{e}_{7}=\left(4,7\right),{e}_{8}=\left(3,8\right)\right\}$$\left(5,8\right),{e}_{5}=\left(5,9\right),{e}_{6}=\left(6,9\right),{e}_{7}=\left(4,7\right),{e}_{8}=\left(3,8\right)}${:(5,8),e_(5)=(5,9),e_(6)=(6,9),e_(7)=(4,7),e_(8)=(3,8)}\left.(5,8), e_5=(5,9), e_6=(6,9), e_7=(4,7), e_8=(3,8)\right\}$\left(5,8\right),{e}_{5}=\left(5,9\right),{e}_{6}=\left(6,9\right),{e}_{7}=\left(4,7\right),{e}_{8}=\left(3,8\right)\right\}$ are processed in the order $\left\{{e}_{1},{e}_{2},{e}_{3},{e}_{4},{e}_{6},{e}_{5},{e}_{7},{e}_{8}\right\}$$\left\{{e}_{1},{e}_{2},{e}_{3},{e}_{4},{e}_{6},{e}_{5},{e}_{7},{e}_{8}\right\}${e_(1),e_(2),e_(3),e_(4),e_(6),e_(5),e_(7),e_(8)}\left\{e_1, e_2, e_3, e_4, e_6, e_5, e_7, e_8\right\}$\left\{{e}_{1},{e}_{2},{e}_{3},{e}_{4},{e}_{6},{e}_{5},{e}_{7},{e}_{8}\right\}$. List the vertices in each connected component after each iteration of lines $3-5$$3-5$3-53-5$3-5$ in the CONNECTED-COMPONENTS.
5) a) Show how mergesort sorts the array $A=\left\{7,9,4,12,8,6,10,5\right\}$$A=\left\{7,9,4,12,8,6,10,5\right\}$A={7,9,4,12,8,6,10,5}A=\{7,9,4,12,8,6,10,5\}$A=\left\{7,9,4,12,8,6,10,5\right\}$
b) For the following set of points, describe how the CLOSEST-PAIR algorithm finds a closest pair of points:
$\left(3,2\right),\left(2,1\right),\left(2,3\right),\left(1,2\right),\left(3,1\right),\left(2,2\right),\left(1,3\right),\left(3,-1\right),\left(5,-2\right)$$\left(3,2\right),\left(2,1\right),\left(2,3\right),\left(1,2\right),\left(3,1\right),\left(2,2\right),\left(1,3\right),\left(3,-1\right),\left(5,-2\right)$(3,2),(2,1),(2,3),(1,2),(3,1),(2,2),(1,3),(3,-1),(5,-2)(3,2),(2,1),(2,3),(1,2),(3,1),(2,2),(1,3),(3,-1),(5,-2)$\left(3,2\right),\left(2,1\right),\left(2,3\right),\left(1,2\right),\left(3,1\right),\left(2,2\right),\left(1,3\right),\left(3,-1\right),\left(5,-2\right)$
c) Find an optimal parenthesisation of a matrix chain product whose sequence of dimensions is $\left(3,5,7,3,4\right)$$\left(3,5,7,3,4\right)$(3,5,7,3,4)(3,5,7,3,4)$\left(3,5,7,3,4\right)$.
6) a) In the Coin changing problem, we have to give change for $n$$n$nn$n$ rupees using the least number of coins of a given set of denominations. It is clear that we cannot give change for any $\mathbit{n}$$\mathbit{n}$n\boldsymbol{n}$\mathbit{n}$ for all set of denominations. For example, trivially, we cannot give change for ₹. 3, if no 1,2 or 3 rupees coins do not exist or not included in the allowed denominations. If the set of denominations include 1 ₹., then we can always give change, so that there is a way of changing $\mathrm{n}₹$$\mathrm{n}₹$n₹\mathrm{n} ₹$\mathrm{n}₹$. for any $\mathrm{n}$$\mathrm{n}$n\mathrm{n}$\mathrm{n}$. We can use greedy approach to find the optimal solutions for many set of denominations. Show that, however, there are set of denominations for which we cannot find the optimal solution by greedy approach. You should include $1₹$$1₹$1₹1 ₹$1₹$. in your denominations so that a solution always exists for the problem.
b) Determine an LCS of $\left(1,0,1,1,0,0,1,0,1\right)$$\left(1,0,1,1,0,0,1,0,1\right)$(1,0,1,1,0,0,1,0,1)(1,0,1,1,0,0,1,0,1)$\left(1,0,1,1,0,0,1,0,1\right)$ and $\left(0,0,1,0,1,1,0,1,0\right)$$\left(0,0,1,0,1,1,0,1,0\right)$(0,0,1,0,1,1,0,1,0)(0,0,1,0,1,1,0,1,0)$\left(0,0,1,0,1,1,0,1,0\right)$.
7) a) Show the $d$$d$dd$d$ and $\pi$$\pi$pi\pi$\pi$ values that result from running breadth-first search on the graph given in Fig. 1 using vertex 4 as the source.
b) Use Kruskal’s algorithm to find a minimal spanning tree in the graph given in Fig. 2.
c) Use Dijkstra’s algorithm to find the shortest paths in the graph given in Fig. 3 with 𝑎 as the
source vertex.
1. a) Show the comparisons the naive string matcher makes for the pattern 𝑃 = 0100 with 01100010010100100.
b) When working modulo $q=17$$q=17$q=17q=17$q=17$, how many spurious hits does the Rabin-Karp matcher encounter in the text $T=29103292566473$$T=29103292566473$T=29103292566473T=29103292566473$T=29103292566473$ when looking for the pattern 22?
c) Compute the values $\left(d,x,y\right)$$\left(d,x,y\right)$(d,x,y)(d, x, y)$\left(d,x,y\right)$ that the call ExTENDEd-EuCLID $\left(10117,11591\right)$$\left(10117,11591\right)$(10117,11591)(10117,11591)$\left(10117,11591\right)$ returns.
9) a) Find all the solutions of the equation $6x\equiv 4\left(mod114\right)$$6x\equiv 4\left(mod114\right)$6x-=4(mod 114)6 x \equiv 4(\bmod 114)$6x\equiv 4\left(mod114\right)$.
b) Let $\left\{\left(-1,-5\right),\left(0,-4\right),\left(1,-1\right)\right\}$$\left\{\left(-1,-5\right),\left(0,-4\right),\left(1,-1\right)\right\}${(-1,-5),(0,-4),(1,-1)}\{(-1,-5),(0,-4),(1,-1)\}$\left\{\left(-1,-5\right),\left(0,-4\right),\left(1,-1\right)\right\}$ and $\left\{\left(-1,14\right),\left(0,7\right),\left(1,4\right)\right\}$$\left\{\left(-1,14\right),\left(0,7\right),\left(1,4\right)\right\}${(-1,14),(0,7),(1,4)}\{(-1,14),(0,7),(1,4)\}$\left\{\left(-1,14\right),\left(0,7\right),\left(1,4\right)\right\}$ be the point-value representations of two polynomials $f\left(x\right)$$f\left(x\right)$f(x)f(x)$f\left(x\right)$ and $g\left(x\right)$$g\left(x\right)$g(x)g(x)$g\left(x\right)$. Find the point-value representation of $h\left(x\right)=f\left(x\right)+g\left(x\right)$$h\left(x\right)=f\left(x\right)+g\left(x\right)$h(x)=f(x)+g(x)h(x)=f(x)+g(x)$h\left(x\right)=f\left(x\right)+g\left(x\right)$. From the point value representation of $h\left(x\right)$$h\left(x\right)$h(x)h(x)$h\left(x\right)$ find the coefficient representation of $h\left(x\right)$$h\left(x\right)$h(x)h(x)$h\left(x\right)$.
c) Compute the DFT of the vector $\left(-1,3,1,-1\right)$$\left(-1,3,1,-1\right)$(-1,3,1,-1)(-1,3,1,-1)$\left(-1,3,1,-1\right)$.
$$a^2=b^2+c^2-2bc\:Cos\left(A\right)$$

## MMTE-002 Sample Solution 2024

mmte-002-solved-assignment-2024-ss-8e24e610-06c9-4b43-84f6-a5bf6ef5ab5c

# mmte-002-solved-assignment-2024-ss-8e24e610-06c9-4b43-84f6-a5bf6ef5ab5c

MMTE-002 Solved Assignment 2024 SS
1. a) The maximum subsequence sum problem is defined as follows: If ${a}_{1},{a}_{2},\dots ,{a}_{n}$${a}_{1},{a}_{2},\dots ,{a}_{n}$a_(1),a_(2),dots,a_(n)a_1, a_2, \ldots, a_n${a}_{1},{a}_{2},\dots ,{a}_{n}$ are in $\mathbf{Z}$$\mathbf{Z}$Z\mathbf{Z}$\mathbf{Z}$, find the maximum value $\sum _{k=i}^{j}{a}_{i}$$\sum _{k=i}^{j} {a}_{i}$sum_(k=i)^(j)a_(i)\sum_{k=i}^j a_i$\sum _{k=i}^{j}{a}_{i}$, for all $\mathrm{i},\mathrm{j},1\le i\le j\le n$$\mathrm{i},\mathrm{j},1\le i\le j\le n$i,j,1 <= i <= j <= n\mathrm{i}, \mathrm{j}, 1 \leq i \leq j \leq n$\mathrm{i},\mathrm{j},1\le i\le j\le n$. We assume that the answer is 0 if all the ${a}_{i}$${a}_{i}$a_(i)a_i${a}_{i}$ are negative or if the sum is empty. The following algorithm finds a solution to the problem. Here, we assume that ${a}_{i}\text{}\mathrm{s}$${a}_{i}\text{}\mathrm{s}$a_(i)sa_i \mathrm{~s}${a}_{i}\text{}\mathrm{s}$ are stored in the array $\mathrm{A}$$\mathrm{A}$A\mathrm{A}$\mathrm{A}$.
State precisely a loop invariant for the for loop in line 2-8. Prove that your loop invariant holds and hence conclude that the algorithm works.
A loop invariant is a condition that holds true before and after each iteration of the loop. For the given algorithm, a suitable loop invariant for the for loop in lines 2-8 is:
"At the start of each iteration of the loop, MaxSum is the maximum subsequence sum of the subarray $A\left[1..i-1\right]$$A\left[1..i-1\right]$A[1..i-1]A[1..i-1]$A\left[1..i-1\right]$."
This means that before the loop starts (when $i=1$$i=1$i=1i = 1$i=1$) and after each iteration of the loop, MaxSum correctly represents the maximum sum of any subsequence that ends at or before the element $A\left[i-1\right]$$A\left[i-1\right]$A[i-1]A[i-1]$A\left[i-1\right]$.
Proof of Loop Invariant:
1. Initialization (Beginning of the loop, $i=1$$i=1$i=1i = 1$i=1$): Before the first iteration, MaxSum is set to 0, which is correct since we have not encountered any elements of the array and the maximum subsequence sum of an empty array is 0.
2. Maintenance (During the loop): At each iteration, we add $A\left[i\right]$$A\left[i\right]$A[i]A[i]$A\left[i\right]$ to Sum. If Sum becomes greater than MaxSum, we update MaxSum to Sum because we have found a larger subsequence sum ending at $i$$i$ii$i$. If Sum is negative, we set it to 0 since a maximum subsequence sum cannot be negative (as per the problem statement, we take the maximum sum to be 0 in this case). This maintains the loop invariant because MaxSum continues to represent the maximum sum of any subsequence that ends at or before $i$$i$ii$i$.
3. Termination (End of the loop): When the loop terminates (after the final iteration when $i=n$$i=n$i=ni = n$i=n$), the loop invariant tells us that MaxSum holds the maximum subsequence sum of the entire array $A\left[1..n\right]$$A\left[1..n\right]$A[1..n]A[1..n]$A\left[1..n\right]$, because every element has been considered, and MaxSum has been updated accordingly throughout the loop.
Conclusion:
By using the loop invariant, we have shown that at the end of each iteration of the loop, the MaxSum variable holds the maximum subsequence sum for the part of the array processed so far. After the loop terminates, MaxSum will therefore hold the maximum subsequence sum for the entire array. This proves that the algorithm correctly finds the maximum subsequence sum for the array $A$$A$AA$A$.
b) Analyse the algorithm and find an upper bound for the run time of the above algorithm.
To analyze the runtime of the algorithm, let’s examine each part of the code and count the number of operations:
1. Initialization (Line 1): Initializing Sum and MaxSum takes constant time, so this part is $O\left(1\right)$$O\left(1\right)$O(1)O(1)$O\left(1\right)$.
2. For Loop (Lines 2-8):
• The loop iterates $n$$n$nn$n$ times, where $n$$n$nn$n$ is the length of the array $A$$A$AA$A$.
• Inside the loop, updating Sum (Line 4) and the comparison (Line 5) are constant-time operations, so they each take $O\left(1\right)$$O\left(1\right)$O(1)O(1)$O\left(1\right)$ time per iteration.
• Updating MaxSum (Line 6) and resetting Sum (Line 8) are also constant-time operations, executed at most once per iteration, so they also take $O\left(1\right)$$O\left(1\right)$O(1)O(1)$O\left(1\right)$ time per iteration.
Since all operations inside the loop take constant time, the total time for each iteration is $O\left(1\right)$$O\left(1\right)$O(1)O(1)$O\left(1\right)$. Therefore, the total time for the loop is $O\left(n\right)$$O\left(n\right)$O(n)O(n)$O\left(n\right)$, where $n$$n$nn$n$ is the number of iterations.
1. Overall Runtime: Combining the initialization and the loop, the overall runtime of the algorithm is $O\left(1\right)+O\left(n\right)=O\left(n\right)$$O\left(1\right)+O\left(n\right)=O\left(n\right)$O(1)+O(n)=O(n)O(1) + O(n) = O(n)$O\left(1\right)+O\left(n\right)=O\left(n\right)$.
Upper Bound for Runtime:
The upper bound for the runtime of the algorithm is $O\left(n\right)$$O\left(n\right)$O(n)O(n)$O\left(n\right)$, where $n$$n$nn$n$ is the length of the input array $A$$A$AA$A$. This means that the algorithm runs in linear time with respect to the size of the input, making it an efficient solution for finding the maximum subsequence sum in an array.

Simply click “Install” to download and install the app, and then follow the instructions to purchase the required assignment solution. Currently, the app is only available for Android devices. We are working on making the app available for iOS in the future, but it is not currently available for iOS devices.

Yes, It is Complete Solution, a comprehensive solution to the assignments for IGNOU. Valid from January 1, 2023 to December 31, 2023.

Yes, the Complete Solution is aligned with the IGNOU requirements and has been solved accordingly.

Yes, the Complete Solution is guaranteed to be error-free.The solutions are thoroughly researched and verified by subject matter experts to ensure their accuracy.

As of now, you have access to the Complete Solution for a period of 6 months after the date of purchase, which is sufficient to complete the assignment. However, we can extend the access period upon request. You can access the solution anytime through our app.

The app provides complete solutions for all assignment questions. If you still need help, you can contact the support team for assistance at Whatsapp +91-9958288900

No, access to the educational materials is limited to one device only, where you have first logged in. Logging in on multiple devices is not allowed and may result in the revocation of access to the educational materials.

Payments can be made through various secure online payment methods available in the app.Your payment information is protected with industry-standard security measures to ensure its confidentiality and safety. You will receive a receipt for your payment through email or within the app, depending on your preference.

The instructions for formatting your assignments are detailed in the Assignment Booklet, which includes details on paper size, margins, precision, and submission requirements. It is important to strictly follow these instructions to facilitate evaluation and avoid delays.

$$c=a\:cos\:B+b\:cos\:A$$

## Terms and Conditions

• The educational materials provided in the app are the sole property of the app owner and are protected by copyright laws.
• Reproduction, distribution, or sale of the educational materials without prior written consent from the app owner is strictly prohibited and may result in legal consequences.
• Any attempt to modify, alter, or use the educational materials for commercial purposes is strictly prohibited.
• The app owner reserves the right to revoke access to the educational materials at any time without notice for any violation of these terms and conditions.
• The app owner is not responsible for any damages or losses resulting from the use of the educational materials.
• The app owner reserves the right to modify these terms and conditions at any time without notice.
• By accessing and using the app, you agree to abide by these terms and conditions.
• Access to the educational materials is limited to one device only. Logging in to the app on multiple devices is not allowed and may result in the revocation of access to the educational materials.

Our educational materials are solely available on our website and application only. Users and students can report the dealing or selling of the copied version of our educational materials by any third party at our email address (abstract4math@gmail.com) or mobile no. (+91-9958288900).

In return, such users/students can expect free our educational materials/assignments and other benefits as a bonafide gesture which will be completely dependent upon our discretion.

Scroll to Top
Scroll to Top