Week 18 Day 2 - Graph Adjacency Lists

Channel:

Bill Kerney

Subscribers:

2,640

Published on May 13, 2021 1:16:49 AM ● Video Link: https://www.youtube.com/watch?v=TtjtZFlBFII

Duration: 1:39:30

62 views

0

We started off today by showing a common problem when debugging code - that the line that the compiler shows the error on is actually one below the actual problem line. In this case, it was extra tricky due to one #include messing up the next #include, making it look like a system header was broken, when all it was was the student's header file missing a close parenthesis.


Our main topic for today was graphs, again. I first showed a general method for traversing a graph, which works as follows (you start with the node you want to begin with on the to_process list). "to_process" is a min heap, sorted by the distance each vertex is from the start. "processed" is a hash table, that keeps track of which vertices we've already seen before (this stops infinite loops).
Step 1) Pop the top vertex off of "to_process", and add it to "processed".
Step 2) Add all of the vertices connected to that vertex to the to_process list, unless they are in "processed" or "to_process" already. (Sometimes I just insert them again into to_process and simply discard any duplicates that come out.)
Repeat until the to_process heap is empty.


Easy peasey. And this same algorithm is used in 1001 different contexts and industries. We'll get practice coding it in CSCI 26, for now just understand it at a conceptual level.


We talked a bit about Big-O in relation to space (which is to say RAM usage). Adjacency matrices are rarely used in real life scenarios since they require RAM proportional to the square of the number of vertices. An "Adjacency List" simply has a linked list (or BST or other data structure) for each vertex, making the RAM usage proportional to the number of edges in the graph. For full graphs (where every vertex is connected to every other one) this will also be O(N^2) RAM usage, but for most real life graphs, they are very sparse, which will take the RAM usage down to O(N*M), where M is the average number of edges per vertex. In the case of something like Facebook, M is going to be way less than a billion. So it will be much more RAM friendly.



We then moved on to talking about the homework assignment, which is to implement a quiz show in Java (or I guess C++ if you really want to) using Sockets and Threads. I'm pushing out demo code to you with a working client and server, so all you need to do is make it do a 10 question quiz show (keeping track of points) for three players at the same time. That's the minimum - if you go above and beyond you will get extra credit, such as by:
1) Adding a GUI
2) Allowing multiple lobbies or sessions to go on at one time
3) Players being able to chat with each other
4) ???