[go: up one dir, main page]
Scribd
Upload
9 views3 pages

Pdsa Ga4

Uploaded by

hathdede
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
9 views3 pages

Pdsa Ga4

Uploaded by

hathdede
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 3

Graded Assignment 4

Q1) For a directed acyclic graph G with n nodes and m edges, what is the asymptotic complexity of efficient algorithms
for topological sorting of G , using adjacency matrix and adjacency list representations, respectively?

A1) O(n2),O(n+m)

Q2) The total number of edges that a complete undirected graph with n vertices can have is _______

[A complete graph is a simple undirected graph in which every pair of vertices is connected by a unique edge.]

A2) n(n-1)/2

Q3) In the given directed graph, removing one edge e makes it a directed acyclic graph. Which of the following can be
the possible values of e ?

A3)

2 -> 4
4 -> 1
1 -> 2

Q4) Given below is a function for traversing the graph using BFS(breadth-first search). For which of the following graphs
will the function BFS_adjList(vertices, AList) always traverse the complete graph?
A4) Connected undirected graphs.

Q5) Select all the possible topological sorted sequence(s) for the graph given below.

A5)

0, 5, 4, 6, 1, 2, 3
5, 6, 4, 0, 1, 2, 3
6, 0, 5, 4, 1, 2, 3
6, 5, 4, 0, 1, 2, 3

Q6) Which of the following graph can be sorted using topological sort?

A6)

Q7) Consider a directed graph G with 90 edges with the least number of vertices possible. What will be the number of
vertices in graph G

A7) 10

Q8) We want to represent the graph G mentioned in previous question, in memory either as an Adjacency matrix or
Adjacency list. Assume that each cell in the adjacency matrix takes 4 bytes of memory and each edge representation in
the adjacency list occupies 8 bytes of memory(you can ignore all other factors that occupy memory). What will be the
amount of memory required to represent graph G using Adjacency matrix and Adjacency List respectively? (This is follow
up question for question 7)

A8) 400 bytes, 720 bytes

Q9)

I: BFS can be used to find the shortest path between two vertices in an unweighted graph.
II: DFS can be used to find the shortest path between two vertices in an unweighted graph.

Which of the following options is correct?

A9) I is true, II is false.

Q10) An undirected graph G has 17 vertices. The sum of the degrees of all the vertices in G is D. The number of vertices
of even degree in G is K, Which of these values are possible for D and K?

A10) D = 42, K = 9

You might also like