CS502 - Fundamentals of Algorithms

Q.2
Solution:
Method 1
0e7322a1-5dce-4ad9-acd1-733be402ae4b-image.png

Method 2
fc8e2c51-4c04-4b4e-9bd0-b2b542a413f2-image.png

a29b0121-e9be-4b74-aea3-d49d9f189d4c-image.png

@Ainhashmi you can choose in categories where you expect.

@zareen said in CS502 GDB 1 Solution and Discussion:

require to find the shortest possible route algorithm

Dijkstra’s algorithm (or Dijkstra’s Shortest Path First algorithm, SPF algorithm) is an algorithm for finding the shortest paths between nodes in a graph, which may represent, for example, road networks. It was conceived by computer scientist Edsger W. Dijkstra in 1956 and published three years later.
Reff

Dijkstra’s algorithm to find the shortest path between a and b. It picks the unvisited vertex with the low distance, calculates the distance through it to each unvisited neighbor, and updates the neighbor’s distance if smaller. Mark visited (set to red) when done with neighbors.
220px-Dijkstra_Animation.gif
Dijkstra’s algorithm

llustration of Dijkstra’s algorithm finding a path from a start node (lower left, red) to a goal node (upper right, green) in a robot motion planning problem. Open nodes represent the “tentative” set (aka set of “unvisited” nodes). Filled nodes are visited ones, with color representing the distance: the greener, the closer. Nodes in all the different directions are explored uniformly, appearing more-or-less as a circular wavefront as Dijkstra’s algorithm uses a heuristic identically equal to 0.
Dijkstras_progress_animation.gif

A demo of Dijkstra’s algorithm based on Euclidean distance. Red lines are the shortest path covering, i.e., connecting u and prev[u]. Blue lines indicate where relaxing happens, i.e., connecting v with a node u in Q, which gives a shorter path from the source to v.
DijkstraDemo.gif

Q.1 Answer
09060a11-e58a-4510-b329-9e0ee2e4ea71-image.png

Q.2 Answer
3cd1afd9-1b1a-40ab-b8e3-96784cc3c253-image.png

Solution:
Question No. 01: The name of the algorithm being used for sorting the given array has given below.
Selection sort
Question No. 02: The Pseudo code for the algorithm used for sorting the given array has given below.

Pseudo code:
1 Selection sort (A)
{
2 For i 1 to A.lenght-1
{
3 imin i
4 for j i+1 to A.length
{
5 If (A[j] < A[imin])
Imin j
}
6 Temp A[i]
7 A[i] A[imin]
8 A[imin] Temp
}
}

Question No. 03: The step by stem analysis of the algorithm designed in question 2 is as follow,

The time taken by each statement (step) is given as follows,

b8c2d4d9-76e3-4841-94a7-e8c1a8202f51-image.png

Selection sort (A) Cost Times

{
For i 1 to A.length-1 |c1 | n
{
imin i--------------------> c2 n-1
for j i+1 to A.length
{ c3 n+n-1+…1=n(n+1)/2
If (A[j] < A[imin])
imin j
}
Temp A[i] c4 n-1
A[i] A[imin] c5 n-1
A[imin] Temp c6 n-1
}
}

Total time T(n) can be calculated as follows,

T(n)= c1n+c2(n-1)+c3(n(n+1)/2)+c4(n-1)+c5(n-1)+c6(n-1)
c1n+c2n-c2+c3 (n2+n/2) +c4n-c4+c5n-c5+c6n-c6 collect the like terms
c3n2/2+ (c1+c2+c3/2+c4+c5+c6) n + (-c2-c4-c5-c6)

This is equivalent to a polynomial an2+bn+c
Therefore T (n) = Big O (n2) by taking the highest order term of the equation.
Note: a, b, c in polynomial represents constants

// Ignoring constant terms

T(n) = O (n2)

@zareen said in CS502 Assignment No. 01 Solution and Discussion:

Question No 02: (Marks: 10)
You are required to calculate (Step by Step) the worst case time complexity T(n) of the algorithm designed in Question No. 01.

Solution:
Question No. 02: The step by stem analysis of the algorithm designed in question 1 is as follow,

The time taken by each statement (step) is given as follows,

Step 1: C1 // Execute only 1 time or Constant Time or O (1)
Step 2: C2 // Execute only 1 time or Constant Time or O (1)
Step 3: n -2 // Execute n -2 times
Step 4: n -2 // Execute n -2 times
Step 5: n – 2 // Execute n -2 times
Step 6: C3 // Execute only 1 time or Constant Time or O (1)
Step 7: C4 // Execute only 1 time or Constant Time or O (1)
Step 8: C5 // Execute only 1 time or Constant Time or O (1)
Step 9: C6 // Execute only 1 time or Constant Time or O (1)

Total time T(n) can be calculated as follows,

T(n) = C1 + C2 + (n -2 ) + (n -2 ) + (n -2 ) + C3 + C4 + C5 + C6
T(n) = C1 + C2 + n -2 + n -2 + n -2 + C3 + C4 + C5 + C6
T(n) = C1 + C2 + n + n + n - 6 + C3 + C4 + C5 + C6
T(n) = 3n + C1 + C2 + C3 + C4 + C5 + C6 -6
T(n) = 3n + (C1 + C2 + C3 + C4 + C5 + C6 -6)
T(n) = 3n + C7 // C7 = (C1 + C2 + C3 + C4 + C5 + C6 -6)
T(n) = n // Ignoring constant terms

Or T(n) = O (n )