Your browser does not seem to support JavaScript. As a result, your viewing experience will be diminished, and you have been placed in read-only mode.

Please download a browser that supports JavaScript, or enable it if it's disabled (i.e. NoScript).

What is generally true of Adjacency List and Adjacency Matrix representations of graphs?

CS502 - Fundamentals of Algorithms

294

M
moaaz Cyberian's Gold last edited by moaaz

In graph theory and computer science, an adjacency list is a collection of unordered lists used to represent a finite graph. Each list describes the set of neighbors of a vertex in the graph. This is one of several commonly used representations of graphs for use in computer programs.
Discussion is right way to get Solution of the every assignment, Quiz and GDB.
We are always here to discuss and Guideline, Please Don't visit Cyberian only for Solution.
Cyberian Team always happy to facilitate to provide the idea solution. Please don't hesitate to contact us!
NOTE: Don't copy or replicating idea solutions.

How to Get Earning from Cyberian

Quiz Copy Solution
Mid and Final Past Papers
Live Chat

For instructions on how to use this Cyberian discussion board
M 1 Reply Last reply
Reply Quote 0
M
moaaz Cyberian's Gold @moaaz last edited by
@moaaz said in What is generally true of Adjacency List and Adjacency Matrix representations of graphs?:
- Lists require less space than matrices but take longer to find the weight of an edge (v1,v2)
Discussion is right way to get Solution of the every assignment, Quiz and GDB.
We are always here to discuss and Guideline, Please Don't visit Cyberian only for Solution.
Cyberian Team always happy to facilitate to provide the idea solution. Please don't hesitate to contact us!
NOTE: Don't copy or replicating idea solutions.

How to Get Earning from Cyberian

Quiz Copy Solution
Mid and Final Past Papers
Live Chat

For instructions on how to use this Cyberian discussion board
1 Reply Last reply
Reply Quote 0

SOLVED CS502 GDB 1 Solution and Discussion
CS502 - Fundamentals of Algorithms • cs502 gdb 1 solution discussion fall 2019 • • zareen

2

0
Votes

2
Posts

374
Views

@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
SOLVED CS502 Assignment No. 01 Solution and Discussion
CS502 - Fundamentals of Algorithms • cs502 assignment 1 solution discussion fall 2019 • • zareen

9

1
Votes

9
Posts

142
Views

@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 )
CS502 Assignment 3 Solution and Discussion
CS502 - Fundamentals of Algorithms • cs502 assignment 3 solution discussion fall 2019 • • zareen

7

0
Votes

7
Posts

736
Views

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

Q.2 Answer
3cd1afd9-1b1a-40ab-b8e3-96784cc3c253-image.png
SOLVED CS502 Assignment No. 02 Solution and Discussion
CS502 - Fundamentals of Algorithms • cs502 assignment 2 solution discussion fall 2019 • • zareen

6

0
Votes

6
Posts

198
Views

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)
M

CS502 Handouts
CS502 - Fundamentals of Algorithms • handouts cs502 cs502 handouts vu handouts fundamentals of algorithms • • moaaz

1

0
Votes

1
Posts

51
Views

No one has replied
M

CS502 Quiz 2 Solution and Discussion
CS502 - Fundamentals of Algorithms • cs502 quiz 2 solution discussion fall 2019 • • moaaz

15

0
Votes

15
Posts

2577
Views

@Ainhashmi you can choose in categories where you expect.
M

The Huffman algorithm finds for?
CS502 - Fundamentals of Algorithms • cs502 huffman algorithm huffman algorithm finds for huffman algorithm • • moaaz

2

0
Votes

2
Posts

41
Views

M

@moaaz said in The Huffman algorithm finds for?:

Optimal

If optimal is measured by average code word length, Huffman’s algorithm gives optimal codes, and the redundancy can be measured as the difference between the average code word length and Shannon’s entropy. If the objective function is replaced by an exponentially weighted average, then a simple modification of Huffman’s algorithm gives optimal codes. The redundancy can now be measured as the difference between this new average and Renyi’s generalization of Shannon’s entropy. By decreasing some of the codeword lengths in a Shannon code, the upper bound on the redundancy given in the standard proof of the noiseless source coding theorem is improved. The lower bound is improved by randomizing between codeword lengths, allowing linear programming techniques to be used on an integer programming problem. These bounds are shown to be asymptotically equal, providing a new proof of Kricevski’s results on the redundancy of Huffman codes. These results are generalized to the Renyi case and are related to Gallager’s bound on the redundancy of Huffman codes.
UNSOLVED CS502 Quiz 1 Solution and Discussion
CS502 - Fundamentals of Algorithms • cs502 quiz 1 solution discussion fall 2019 • • zareen

1

0
Votes

1
Posts

128
Views

No one has replied

100% Off on Your FEE Join US! Ask Me How?

If you want to know how you can join us and get 100% Discount on your FEE ask Cyberian in Chat Room!

solution1255 discussion1206 fall 2019813 assignment 1433 assignment 2297 spring 2020265 gdb 1248 assignment 382 crw10174 spring 201955

| |

Live Chat

1 / 1

What is generally true of Adjacency List and Adjacency Matrix representations of graphs?

SOLVED CS502 GDB 1 Solution and Discussion CS502 - Fundamentals of Algorithms • cs502 gdb 1 solution discussion fall 2019 • • zareen

SOLVED CS502 Assignment No. 01 Solution and Discussion CS502 - Fundamentals of Algorithms • cs502 assignment 1 solution discussion fall 2019 • • zareen

CS502 Assignment 3 Solution and Discussion CS502 - Fundamentals of Algorithms • cs502 assignment 3 solution discussion fall 2019 • • zareen

SOLVED CS502 Assignment No. 02 Solution and Discussion CS502 - Fundamentals of Algorithms • cs502 assignment 2 solution discussion fall 2019 • • zareen

CS502 Handouts CS502 - Fundamentals of Algorithms • handouts cs502 cs502 handouts vu handouts fundamentals of algorithms • • moaaz

CS502 Quiz 2 Solution and Discussion CS502 - Fundamentals of Algorithms • cs502 quiz 2 solution discussion fall 2019 • • moaaz

The Huffman algorithm finds for? CS502 - Fundamentals of Algorithms • cs502 huffman algorithm huffman algorithm finds for huffman algorithm • • moaaz

UNSOLVED CS502 Quiz 1 Solution and Discussion CS502 - Fundamentals of Algorithms • cs502 quiz 1 solution discussion fall 2019 • • zareen

100% Off on Your FEE Join US! Ask Me How?

SOLVED CS502 GDB 1 Solution and Discussion
CS502 - Fundamentals of Algorithms • cs502 gdb 1 solution discussion fall 2019 • • zareen

SOLVED CS502 Assignment No. 01 Solution and Discussion
CS502 - Fundamentals of Algorithms • cs502 assignment 1 solution discussion fall 2019 • • zareen

CS502 Assignment 3 Solution and Discussion
CS502 - Fundamentals of Algorithms • cs502 assignment 3 solution discussion fall 2019 • • zareen

SOLVED CS502 Assignment No. 02 Solution and Discussion
CS502 - Fundamentals of Algorithms • cs502 assignment 2 solution discussion fall 2019 • • zareen

CS502 Handouts
CS502 - Fundamentals of Algorithms • handouts cs502 cs502 handouts vu handouts fundamentals of algorithms • • moaaz

CS502 Quiz 2 Solution and Discussion
CS502 - Fundamentals of Algorithms • cs502 quiz 2 solution discussion fall 2019 • • moaaz

The Huffman algorithm finds for?
CS502 - Fundamentals of Algorithms • cs502 huffman algorithm huffman algorithm finds for huffman algorithm • • moaaz

UNSOLVED CS502 Quiz 1 Solution and Discussion
CS502 - Fundamentals of Algorithms • cs502 quiz 1 solution discussion fall 2019 • • zareen