Good luck on the exam! You got this 😄

I'm so glad you're enjoying the game! And awesome to hear that you made an AI and a weather app 🙂Here's the link to the song (it's Creative Commons license: ccmixter.org/files/tobias_weber/56664)

@@hitarthk Absolutely! But only if you expect relatively few children per node compared to the total alphabet size (as Hash Maps need lots of extra space to maintain the O(1) average case time complexity)

@@niemasd thanks. yes that makes sense. But then I am wondering how this map version of the trie compare against ternary search trees (kzbin.info/www/bejne/mIjEiZeueq2Ul8k&ab_channel=NiemaMoshiri)

@@1090persian Counting them is out of the scope of this video (we just get a binary "yes" or "no", but Pavel Pevzner and Phillip Compeau's "Bioinformatics Algorithms" KZbin videos cover the topic further, including how to get the actual count

Sure! But all hashing related videos I'm showing are assuming all of your hash functions are excellent: they all uniformly distribute hash values across all possible integers. In other words, we're assuming that, if there are M columns in my Count-Min Sketch, the probability that my element maps to any given index is 1/M

@@UwUAroze That does indeed matter; great insight! 😄 Much like how, with a BST, you typically want to optimize the insertion order in some way to make the tree well-balanced, the same logic applies for K-D Trees. There are algorithms for building well-balanced K-D Trees from a given dataset; see here: en.wikipedia.org/wiki/K-d_tree#Construction

@@niemasd oh so it matters from a standpoint of optimising the nns search/etc, but regardless of order it would be able to do the search with the correct answer?

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