The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
Email or Username
Password
Remember
Login
Register

I forgot my password
Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Prev
Blogs
New Blog
Exams
Cormen Edition 3 Exercise 22.1 Question 1 (Page No. 592)
0
votes
37
views
Given an adjacencylist representation of a directed graph, how long does it take to compute the outdegree of every vertex ? How long does it take to compute the indegrees ?
cormen
algorithms
graphalgorithms
descriptive
asked
Apr 7, 2019
in
Algorithms
by
akash.dinkar12

37
views
answer
comment
Please
log in
or
register
to add a comment.
Please
log in
or
register
to answer this question.
1
Answer
0
votes
To compute the out degree each vertex we would need $O(V+E)$.
To compute the in degree we have to scan through adjacency lists and count how many times each vertex has appeared. This is $O(V+E)$
answered
Apr 8, 2019
by
Vineet Kumar 1
comment
Please
log in
or
register
to add a comment.
← Prev.
Next →
← Prev. Qn. in Sub.
Next Qn. in Sub. →
Related questions
0
votes
0
answers
1
Cormen Edition 3 Exercise 22.1 Question 3 (Page No. 592)
The transpose of a directed graph $G=(V,E)$ is the graph $G^T=(V,E^T)$, where $E^T=\{(v,u) \in V * V :(u,v) \in E \ \}$ .Thus ,$G^T$ is $G$ with all its edges reversed . Describe ... algorithms for computing $G^T$ from $G$,for both the adjacency list and adjacency matrix representations of $G$. Analyze the running times of your algorithms.
asked
Apr 7, 2019
in
Algorithms
by
akash.dinkar12

41
views
cormen
algorithms
graphalgorithms
descriptive
0
votes
1
answer
2
Cormen Edition 3 Exercise 22.1 Question 2 (Page No. 592)
Give an adjacencylist representation for a complete binary tree on $7$ vertices. Give an equivalent adjacencymatrix representation. Assume that vertices are numbered from $1\ to\ 7$ as in a binary heap.
asked
Apr 7, 2019
in
Algorithms
by
akash.dinkar12

41
views
cormen
algorithms
graphalgorithms
descriptive
0
votes
0
answers
3
Cormen Edition 3 Exercise 22.1 Question 8 (Page No. 593)
Suppose that instead of a linked list, each array entry $adj[u]$ is a hash table containing the vertices $v$ for which $(u,v) \in E$. If all edge lookups are equally likely, what is the expected ... alternate data structure for each edge list that solves these problems. Does your alternative have disadvantages compared to the hash table ?
asked
Apr 7, 2019
in
Algorithms
by
akash.dinkar12

52
views
cormen
algorithms
graphalgorithms
descriptive
0
votes
0
answers
4
Cormen Edition 3 Exercise 22.1 Question 6 (Page No. 593)
Most graph algorithms that take an adjacencymatrix representation as input require time $\Omega(V^2)$,but there are some exceptions. Show how to determine whether a directed graph $G$ contains a universal link $$ a vertex with indegree $V1$ and outdegree $0$ in time $O(V)$ , given an adjacency matrix for $G$.
asked
Apr 7, 2019
in
Algorithms
by
akash.dinkar12

51
views
cormen
algorithms
graphalgorithms
descriptive
Quick search syntax
tags
tag:apple
author
user:martin
title
title:apple
content
content:apple
exclude
tag:apple
force match
+apple
views
views:100
score
score:10
answers
answers:2
is accepted
isaccepted:true
is closed
isclosed:true
Recent Posts
IISc CDS Interview Experience, 2020
IITD MS CSE (Systems) Experience
IIT Bombay M.Tech. (RA)  Interview Experience
Interview Experience for MS(R)IIT Delhi (School of Information Technology)
PGEE 2020 (CSE) Experience
Subjects
All categories
General Aptitude
2k
Engineering Mathematics
8.3k
Digital Logic
2.9k
Programming and DS
5k
Algorithms
4.4k
Theory of Computation
6.2k
Compiler Design
2.2k
Operating System
4.6k
Databases
4.2k
CO and Architecture
3.4k
Computer Networks
4.2k
Non GATE
1.2k
Others
1.5k
Admissions
595
Exam Queries
562
Tier 1 Placement Questions
23
Job Queries
71
Projects
19
Unknown Category
1k
Recent Blog Comments
Thank brother !! Bookmarked it :)
Check out goxul.github.io, it has all the...
congratulation brother ! Can you please tell me...
I got selected for this, in case someone lands up...
After the written exam and at the time of...
Network Sites
GO Mechanical
GO Electrical
GO Electronics
GO Civil
CSE Doubts
52,375
questions
60,586
answers
202,005
comments
95,409
users