Data Structures and Algorithms in JavaScript Next Steps

Transcript from the "Next Steps" Lesson

[00:00:00]
>> Bianca Gandolfo: So we have gone through a lot this week. We've covered most of the fundamentals that you'll find in an introductory data structures and algorithms class, right? Mostly like the first class of that subject, you know what I mean? So if you think about like a college course, a data structures and algorithms course is gonna be usually two semesters.

[00:00:22] So you'll have the first semester and the second semester. This is kind of like a semester's worth of content of the first introductory lessons, right? So you might have three or four lessons that build on each of these topics, right? So you kinda just took the first hour of each of those topics.

[00:00:41] And there's more to it, however you don't commonly need to go beyond that if you're just studying for interviews. Because most people, honestly, forget that stuff anyway, and your interviewer is a person. So you tend to not have to go beyond that. But if you did, I'm gonna give you some next steps of what are some cool things that you can learn next, once you feel comfortable with the fundamentals we've been covering in this class.

[00:01:10] So these are all sort of building blocks that build, they work together, that underlie how everything works right here. In your computer, on the Internet, that kind of thing. So let's talk about next steps. So the very first day we talked about object-oriented JavaScript, you learned how to create a class in pseudoclassical style.

[00:01:31] So the next thing you might wanna do is learn how to subclass and extend your classes according to other object-oriented patterns. So I would look into that. You can learn how to implement classes in ES6. There's this cool repo that has basically, has most of the data structures and the algorithms that we have done in this class written on ES6.

[00:01:54] And they also have some in regular JavaScript. So you could check that out and see how that compares.
>> Bianca Gandolfo: Awesome, so we learned about time complexity. We were able to estimate, generally estimate, right, how fast our algorithms were. And think about what parts of them were the slow parts, and what parts of them were maybe the first parts.

[00:02:19] Next you can do is to keep learning about computational complexity theory. And you could take a whole class on this, and learn about NP-Complete and all these different ways to estimate how difficult a problem is. The other thing you could do is learn how to calculate time complexity formally, and write out proofs, and things like that.

[00:02:44] Those are more things that you could do with time complexity. Sorting, so we learned elementary sorting, recursive sortings. You can learn a non-comparison sort like Radix sort. I had the video on over lunch about Radix sort. You can learn how to combine different sorts to create new sorts, like Timsort is a combination of insertion sort with merge sort.

[00:03:10] And it's the underlying sort for Python. Most other languages are implementing either merge sort or quick sort or both of them under the hood. So Timsort could be another fun one. Or you could just learn some other sorts cuz they have funny names. Like gnome sort, stooge sort, bogosort.

[00:03:31] These are all kind of just silly sorts that are kinda just silly examples. And all of these run slower than bubble sort, and we already know bubble sort is really slow. Bogosort, actually the other name is stupidsort. So they're just like Bogosort, I think they just have random permutations of each of the input until finally find one that's sorted.

[00:03:54] So you randomly change it, one of them.
>> off screen: [LAUGH]
>> Bianca Gandolfo: And then you check it.
>> off screen: My God!
>> Bianca Gandolfo: And then you randomly change it, and then you check it. And so it's just a funny example.
>> off screen: Well, that's one way to do it.
>> Bianca Gandolfo: Yeah, so no one uses it in practice.

[00:04:07] The next day we talked about linked lists and trees, sort of these general trees. The next steps, you can learn how to do a prefix tree, which is used in auto complete. When you start typing in Google, that's using a prefix tree. You can also use it as a solver for Boggle or Words With Friends or something.

[00:04:25] You can use that for that. If you're lonely you can create a dialogue tree. Which is what we use for when you're interacting with non-player characters in video games and you talk to them and they answer you. That would be a dialogue tree. You can create a scavenger hunt game with your linked list.

[00:04:44] So that your next, you can only access to your next by solving some riddle. It could be a fun game for a linked list. Also obviously, you can bind trees and link lists with a bunch of other algorithms that could be useful.
>> Bianca Gandolfo: Binary search trees. You can balance your binary search trees using a DSW algorithm.

[00:05:05] So you already have your binary search tree. It's created. It's super lopsided. The DSW algorithm will help you balance it. Or If you thought about this ahead of time, you could just create an AVL tree or red-black tree, or a splay tree, which are self balancing. So as you're adding nodes, it's going to keep track of how deep it is and balance.

[00:05:26] And again, a balance tree is a tree that doesn't have a layer that's too deeper than any of the other layers. Does that make sense? The height is not lopsided, so a balanced tree looks like a triangle. A unbalanced tree looks like it has like a little tail somewhere, if you drew it out.

[00:05:54] Another thing, the next step could be comparing a binary tree to binary to a binary heap, and then taking it a step further and doing heap sort. We have exercises for binary heaps and heap sorts in our algorithm class repo, so if you have time, you can check that out.

[00:06:13] For graphs, graphs are amazing, they are applied to a bunch of different things. We learned how to represent them in both an adjacency matrix and adjacency list. And then we talked about how we can explore them [COUGH] either depth first or breath first. Those are the main sort of entry points into graph algorithms.

[00:06:36] You could dive into graph theory and discrete mathematics, if you really wanna be hardcore. You can learn topological sort to figure out dependencies. Like if you're in college and you wanna figure out what classes you need to graduate, in what order, because they all require whatever, all these classes have these different requirements, you can use topological sort for that.

[00:07:01] If you wanna calculate shortest paths between two cities, Dijkstra's algorithm is really famous for that. If you wanna learn how to find minimum splay trees that are central to data mining, you can use Prim's algorithm for that. And these are just sort of the next steps. And there's all kinds of branches that you can go from there, right?

[00:07:27] So once you're starting to find path algorithms, right? Then from Dijkstra's algorithm, which is the most famous one, there's a bunch of different kinds, right? And you can keep going. And if you find yourself in Wikipedia, you can look, you'll say like, pathfinding algorithms, and it'll [SOUND] all these different ones.

[00:07:48] So hash tables. So we ended with hash tables. We made our own little pseudo code hashing functions. We created our own hash tables with different methods on it. Now you can just apply that knowledge, if you want, to how version control works. It uses trees and hashing and all these things all together to make sure that you don't lose your code as you change it.

[00:08:17] It's really exciting. You can get curious about bloom filters and how it's a kind of hash table that we use in caching. Hashing, like I said earlier, is used in security. And you can start by thinking about a hash tree, which combines hashing with a tree. And this is something that's really common in P2P networks.

[00:08:40] Do people do that still, where they download stuff from each other?
>> off screen: Torrents, yeah.
>> Bianca Gandolfo: Yeah, torrents. But torrents are still P2P, though, right? I don't participate in that kind of stuff, so I don't really know.
>> off screen: When I think about P2P networks, I think of like LimeWire or Kazaa.

[00:08:54]
>> Bianca Gandolfo: Yeah that's what I'm thinking.
>> off screen: Or stuff like a specific network, but torrents kinda replaced that. So it works person-to-person, but it's a different-
>> Bianca Gandolfo: It's called something else now.
>> off screen: Protocol, yeah.
>> Bianca Gandolfo: Yeah, got it. Cool, and the other thing you can think about is the complexity of a distributed hash table, which underlies Box, or Dropbox, or Google Drive.

[00:09:19] So that's kind of fun. And then, that's all I got, thank you. That's your next steps.