SEO for Desklib: Title, Meta Title, Meta Description, Slug, Summary, Subject, Course Code, Course Name, College/University

This document contains solutions to questions related to algorithms, graph theory, and summation. It also includes an analysis of the time complexity of the algorithms.

Contents
Question 1.............................................................................................................................................1
Question 1.a......................................................................................................................................1
Question 1.b.....................................................................................................................................1
Question 2.............................................................................................................................................1
Question 2.a......................................................................................................................................1
Question 2.b.....................................................................................................................................2
Question 2.C.....................................................................................................................................3
Question 3.............................................................................................................................................3
Question 3.a......................................................................................................................................3
Question 3.b.....................................................................................................................................4
Question 4.............................................................................................................................................4
Question 4.a......................................................................................................................................4
Question 4.b.....................................................................................................................................5

Question 1
Question 1.a
Algorithm MatrixMult (A[n][n], B[n][n], C[n][n])
for i = 0 to n-1
for j = 0 to n-1
sum = 0
for k = 0 to n-1 sum = sum + A[i][k] * B[k][j]
C[i][j] = sum
Question 1.b
T (n)=∑
i=0
n−1
❑∑
j=0
n−1
∑
k=0
n−1
2=2 n3 = O(n3))
Question 2
Question 2.a
Euler path
Euler path is a path and that uses every edge of a graph exactly once that is called as
Euler Path. In this path start and ends with different vertices.
Euler Circuit
The Euler circuit based on the Euler path. The Euler circuit is a circuit and that uses
every edge of a graph exactly once that is called as the Euler circuit. This circuit start and
ends with the same vertex.

Question 2.b
Graph
A- 2, B- 2, C-2 , D- 1, E-3
Euler path: D-E-B-A-C-E
A
C
B
E D

Question 2.C
Remove the d path from this bridge and it makes the Euler ciruit.because it start an ends with
same vertex.
Euler circuit: A-B-E-C-A
Question 3
Question 3.a
Solution
The ith term in the summation is : si = (-1)i+1 X2i-1 / (2i-1)!
A
C
B
E

(−x2 )
Then si = (2i − 2)(2i −1) si−1 for i >1with s1 =x
s = x; sum = s; y = -x*x; // 2 float arithmetic operations for i = 2 to n
m = 2*i; a = (m -2)*(m-1); // These do not contain float arithmetic
s = y/a * s; sum = sum + s; //3 float arithmetic operations
Question 3.b
The ith term in the summation is : si = (-1)i+1 X2i-1 / (2i-1)!
Then si =(-x2)/(2i − 2)(2i −1) si−1 for i >1with s1 = x
s = x;
sum = s;
y = -x*x for i = 2 to n
s = y/a * s;
sum = sum + s;
Hence T(n) = 3(n-1) + 2 float arithmetic operations.
Question 4
Question 4.a
Algorithm
int F(A,n)
S = 0;
for i = 0 to n-2
for j = i+1 to n-1

if (Ai > Aj) S++
return S
Question 4.b
Analysis
n−2 n−1 n−2 n−1
T( n ) = ∑ ∑1 = ∑( n − i − 1 ) = ∑i = n( n − 1 ) / 2 = O( n 2 )
i =0 j=i+1 i=0 i=1