Note: This course is a subset of our much longer course 'From 0 to 1: Data Structures & Algorithms' so please don't sign up for both:-)
This is an animated, visual and spatial way to learn data structures and algorithms
Taught by a Stanford-educated ex-Googler.
The graph is a data structure that is used to model a very large number of real world problems. It's also an programming interview favorite. The study of graphs and algorithms associated with graphs forms an entire field of study called graph theory.
Using discussion forums
Please use the discussion forums on this course to engage with other students and to help each other out. Unfortunately, much as we would like to, it is not possible for us at Loonycorn to respond to individual questions from students:-(
We're super small and self-funded with only 2-3 people developing technical video content. Our mission is to make high-quality courses available at super low prices.
The only way to keep our prices this low is to *NOT offer additional technical support over email or in-person*. The truth is, direct support is hugely expensive and just does not scale.
We understand that this is not ideal and that a lot of students might benefit from this additional support. Hiring resources for additional support would make our offering much more expensive, thus defeating our original purpose.
It is a hard trade-off.
Thank you for your patience and understanding!
There are a number of different ways in which graphs can be implemented. However they all follow they same basic graph interface. The graph interface allows building up a graph by adding edges and traversing a graph by giving access to all adjacent vertices of any vertex.
Compare the adjacency matrix, adjacency list and the adjacency set in terms of space and time complexity of common operations
Common traversal methods of trees apply to graphs as well. There is an additional wrinkle with graphs, dealing with cycles and with unconnected graphs. Otherwise the algorithms are exactly the same as those we use to traverse trees.
So far we only deal with unweighted graphs. Graphs whose edges have a weight associated are widely used to model real world problems (traffic, length of path etc).
A greedy algorithm is one which tries to find the local optimum by looking at what is the next best step at every iteration. It does not look at the overall picture. It's best used for optimization problems where the solution is very hard and we want an approximate answer.
Finding the shortest path in a weighted graph is a greedy algorithm.
The implementation of Dijkstra's algorithm in Java.
A weighted graph can have edge weights which are negative. Dealing with negative weights have some quirks which are dealt with using the Bellman Ford algorithm.
If a graph has a negative cycle then it's impossible to find a shortest path as every round of the cycle makes the path shorter!
The minimal spanning tree is used when we want to connect all vertices at the lowest cost, it's not the shortest path from source to destination.
Let's see how we implement Prim's algorithm in Java.
Loonycorn is us, Janani Ravi and Vitthal Srinivasan. Between us, we have studied at Stanford, been admitted to IIM Ahmedabad and have spent years working in tech, in the Bay Area, New York, Singapore and Bangalore.
Janani: 7 years at Google (New York, Singapore); Studied at Stanford; also worked at Flipkart and Microsoft
Vitthal: Also Google (Singapore) and studied at Stanford; Flipkart, Credit Suisse and INSEAD too
We think we might have hit upon a neat way of teaching complicated tech courses in a funny, practical, engaging way, which is why we are so excited to be here on Udemy!
We hope you will try our offerings, and think you'll like them :-)