Algorithms Course - Graph Theory Tutorial from a Google Engineer
video description
Date: 2022-03-14
Related videos
Comments and reviews: 10
KaWiz
great video, very easy to follow!
just wanted to say, at 49:08 where having separate x,y,z queues is suggested in order to avoid using a coordinate wrapper like struct coord - int x,y,z - that has to be packed/unpacked - keeping everything in one queue will preserve memory locality (sequential accesses in the same area of memory, likely in the same cache read), while having to access 3 different queues every iteration will likely be a performance hit as they cause cache misses (which, even if they're contiguous, would be inevitable above a certain number of vertices), and quite possibly be worse than packing/unpacking a structure depending on how the compiler optimizes that
as an alternative, if you want your queues to just be primitives without any packing, just push x,y,z sequentially onto the same queue, and dequeue them 3 at a time as well. it's not any more complex than managing 3 queues at once, avoids packing, and most importantly doesn't require both allocating and accessing multiple data structures. the choice of having 3 queues just to avoid using a wrapper is pretty baffling!
reply
great video, very easy to follow!
just wanted to say, at 49:08 where having separate x,y,z queues is suggested in order to avoid using a coordinate wrapper like struct coord - int x,y,z - that has to be packed/unpacked - keeping everything in one queue will preserve memory locality (sequential accesses in the same area of memory, likely in the same cache read), while having to access 3 different queues every iteration will likely be a performance hit as they cause cache misses (which, even if they're contiguous, would be inevitable above a certain number of vertices), and quite possibly be worse than packing/unpacking a structure depending on how the compiler optimizes that
as an alternative, if you want your queues to just be primitives without any packing, just push x,y,z sequentially onto the same queue, and dequeue them 3 at a time as well. it's not any more complex than managing 3 queues at once, avoids packing, and most importantly doesn't require both allocating and accessing multiple data structures. the choice of having 3 queues just to avoid using a wrapper is pretty baffling!
reply
Rodion
At 39:30 the reconstructPath function of BFS algorithm is shown and explained. Is the -at != null- actually needed at every iteration? if -s- and -e- are connected, then -prev[e]- is not null and for any node between e and s, -no- -prev[node]- on the path back from e to s is null. If e belongs to a different cluster of nodes, that is disconnected from s, then -prev[e]- would be null. As i see it, only a one-time check-if(prev[e] != null) return [];- at the start of the function is needed. What am i missing here?
reply
At 39:30 the reconstructPath function of BFS algorithm is shown and explained. Is the -at != null- actually needed at every iteration? if -s- and -e- are connected, then -prev[e]- is not null and for any node between e and s, -no- -prev[node]- on the path back from e to s is null. If e belongs to a different cluster of nodes, that is disconnected from s, then -prev[e]- would be null. As i see it, only a one-time check-if(prev[e] != null) return [];- at the start of the function is needed. What am i missing here?
reply
Madhukiran
-2:49:00 : Articulation points
This can be further improved
after dfs recursive call back :
if ids[at] > low[to]
- low[at] = min(low[at], low[to]); -
else
- isArts[at] = true; -
any node's low link value can not be greater than it's id value. So, if -to- node's low link value is >= node's id, it implies that node's low link value can not be reduced further
reply
-2:49:00 : Articulation points
This can be further improved
after dfs recursive call back :
if ids[at] > low[to]
- low[at] = min(low[at], low[to]); -
else
- isArts[at] = true; -
any node's low link value can not be greater than it's id value. So, if -to- node's low link value is >= node's id, it implies that node's low link value can not be reduced further
reply
Matt
Wow, what a resourceful and comprehensive video. I actually came across it while searching for videos of Sugiyama Layout algorithm for Layered Graph Drawing. The video does cover a lot bot doesn't seem to include that topic. Does anyone know other good videos walking through this algorithm?
reply
Wow, what a resourceful and comprehensive video. I actually came across it while searching for videos of Sugiyama Layout algorithm for Layered Graph Drawing. The video does cover a lot bot doesn't seem to include that topic. Does anyone know other good videos walking through this algorithm?
reply
Adeeb
While implementing the solve() function for TSP problem, we are running an extra inner loop for each value of next to select the ending node represented by e. Won't this jump up the power of n, inside the overall time complexity, from 2 to 3?
reply
While implementing the solve() function for TSP problem, we are running an extra inner loop for each value of next to select the ending node represented by e. Won't this jump up the power of n, inside the overall time complexity, from 2 to 3?
reply
Dabbo
you gotta love it when extremely well-informed programmers take their time to teach you a bunch of super fascinating mathematics for hours for NO COST. Thastd how you know a passionate programmer from a money chaser
reply
you gotta love it when extremely well-informed programmers take their time to teach you a bunch of super fascinating mathematics for hours for NO COST. Thastd how you know a passionate programmer from a money chaser
reply
Scary
Can someone help me give the direct link for the source code of everything discussed in this amazing video?
It will be really helpful. It won't take much time, but I can learn so much from that.
reply
Can someone help me give the direct link for the source code of everything discussed in this amazing video?
It will be really helpful. It won't take much time, but I can learn so much from that.
reply
Chimera
error in the code at 28 min. 'neighbours = graph[at]' would resolve to -cannot resolve property of undefined- as graph was never defined. It should read 'neighbours = g[at]'
reply
error in the code at 28 min. 'neighbours = graph[at]' would resolve to -cannot resolve property of undefined- as graph was never defined. It should read 'neighbours = g[at]'
reply
Jonathan
I think that the algorithm for articulation points is incorrect. It doesn't seem to account for start nodes in cycles that don't have any other outgoing edges
reply
I think that the algorithm for articulation points is incorrect. It doesn't seem to account for start nodes in cycles that don't have any other outgoing edges
reply
JOE
11:04 it is not V-2 work to enumerate the edges of an adjacency matrix it takes V-4 work since the matrix takes up V-2 -space- and the enumeration takes V-2 -time-
reply
11:04 it is not V-2 work to enumerate the edges of an adjacency matrix it takes V-4 work since the matrix takes up V-2 -space- and the enumeration takes V-2 -time-
reply
Add a review, comment
Other channel videos
