Woops, thank you for catching that! I archived a lot of my teaching-related files from past quarters, and I forgot that the lecture slides for this course were being linked in the KZbin descriptions. I am away from my computer at the moment, but I'll repost them soon, and I'll follow up in another reply to this comment when I do

Okay, I just updated the links to all of the lecture slides in this playlist, so it should work now! Please feel free to comment again on any of them if the link seems broken. Thanks again for catching this 🙂

@@niemasd thanks a lot for sharing

@@InsocialDev Essentially! I would personally slightly adjust it and say that an Abstract Data Type is an abstraction of a container, and that we can use Data Structures to *implement* ADTs. In other words, I would start with the abstract (the ADT essentially just defines what operations *should exist*, without any details about how they work or how fast they are), and then transition to the concrete (the Data Structure then defines *how* the operations will work, and as a result, how fast they will be). But both ways of thinking are essentially equivalent 😄

@@niemasd Thanks for the correction🥰

@@InsocialDev Thank you for watching the video! 😄

Great insight! Yes, in practice, it is common to use an array-based structure (e.g. an Array List) as the separation chain, but it's ultimately up to the implementation

LOL I've been super into console hacking since middle school! Been doing this a loooong time 😂 Good luck with the final!!

Yes, that is the worst case scenario for a Treap (keys and priorities are both sorted), which results in O(n) time complexity just like the BST worst case. You'll how Treaps are useful (and how this worst case scenario becomes unlikely in practical uses) in the Randomized Search Tree video

It continues in the next video in the playlist... kzbin.info/aero/PLM_KIlU0WoXmkV4QB1Dg8PtJaHTdWHwRS&si=ZZkCLwbNvCIhDwdF

I'm not sure I understand your question; can you clarify? New nodes are inserted as red nodes, so if the new red node has a black parent, no need to do anything: it's already valid

Great question! BWT was originally not intended for this task (it was originally intended for data compression), and the original BWT paper can be found here: www.eecs.harvard.edu/~michaelm/CS222/burrows-wheeler.pdf *To my knowledge*, this is the first paper that applies BWT to the "match a bunch of short strings to a single long string" problem in Bioinformatics: doi.org/10.1186%2Fgb-2009-10-3-r25 Also, *to my knowledge*, this is the first paper that applies BWT to genomic data: doi.org/10.1089/cmb.2005.12.943

Thank you! I wrote a guide about my workflow here (I use a Paint-like drawing tool, and I use OBS to capture the drawing canvas): github.com/niemasd/teaching/blob/master/Tutorials/VideosKhanAcademy.md

right? we are standing on the shoulders of giants

Precisely! Red-Black Trees are still guaranteed to have O(log n) height in the worst case, but they don't necessarily maintain the balance factor requirements that an AVL Tree does

I prove it in the "Notes/Corrections" in the video description

The traversal itself is not O(V + E). Imagine you have a complete graph with V-1 nodes (so (V-1)(V-2)/2 edges), and you have a single additional node on its own unattached. BFS starting at that single additional node will finish instantly because it has no outgoing edges. BFS traversal starting from a single vertex is bounded by the edges you are able to traverse, not the number of vertices (there are many vertices you may possibly never be able to encounter if there are no edges connecting to them). The O(V) term comes from initialization (or if you chose to perform repeated BFS traversals to force yourself to explore the whole graph). A single BFS traversal starting from a single node is O(E)

Oh, just realized which video this is in response to LOL so not sure if it was just a meme comment 😂 But figured I'd respond just in case!

Excellent question! This is actually described in the next video of the series. Specifically, we will be able to catch those cases via "dictionary links": kzbin.info/www/bejne/hXeuqYp8mtySgpI

You could use a prefix array as well! We're looking for occurrences of the short string as a substring of the long stream, and using a suffix array exploits the fact that, if a string x appears as a substring of string y, then there must exist a suffix of y that begins with x. If we were to use a prefix array instead, we would exploit the fact that, if a string x appears as a substring of string y, then there must exist a prefix of y that *ends* with x. In other words, we would essentially do our binary search backwards. Another way to think about it is that using a prefix array would be equivalent to reversing the long string and the short strings and using a suffix array