Tries - CS50 Shorts

No video

Tries - CS50 Shorts

Рет қаралды 72,630

Күн бұрын

***
This is CS50, Harvard University's introduction to the intellectual enterprises of computer science and the art of programming.
***
HOW TO SUBSCRIBE
www.youtube.com...
HOW TO TAKE CS50
edX: cs50.edx.org/
Harvard Extension School: cs50.harvard.e...
Harvard Summer School: cs50.harvard.e...
OpenCourseWare: cs50.harvard.e...
HOW TO JOIN CS50 COMMUNITIES
Discord: / discord
Ed: cs50.harvard.e...
Facebook Group: / cs50
Faceboook Page: / cs50
GitHub: github.com/cs50
Gitter: gitter.im/cs50/x
Instagram: / cs50
LinkedIn Group: / 7437240
LinkedIn Page: / cs50
Reddit: / cs50
Quora: www.quora.com/...
Slack: cs50.edx.org/s...
Snapchat: / cs50
Twitter: / cs50
KZfaq: / cs50
HOW TO FOLLOW DAVID J. MALAN
Facebook: / dmalan
GitHub: github.com/dmalan
Instagram: / davidjmalan
LinkedIn: / malan
Quora: www.quora.com/...
Twitter: / davidjmalan
***
CS50 SHOP
cs50.harvardsh...
***
LICENSE
CC BY-NC-SA 4.0
Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International Public License
creativecommon...
David J. Malan
cs.harvard.edu...
malan@harvard.edu

Пікірлер: 86

@rubabzahber5990 6 жыл бұрын

god bless cs50

@UpperKS 5 жыл бұрын

No kidding

@jasonbellis9128 3 жыл бұрын

Another great vid. But, I also feel using Year as key to lookup schools is an odd example, and causes confusion for many... Not only for collision potential. Also, it's not a real world use case to say "I know Harvard was founded in 1636, so look it up by 1636 and see if Harvard is there". I know - it's just an example with 4 digits for simplicity... It's just easier to comprehend examples with real-world use cases.

@sogarriz Ай бұрын

exactly! as i went thru even i was like what if 1701 was used again for say standford but then the key is exhausted so how do we handle collision? plus this would fail over large data sets according to the example.

@SlowDancer 6 күн бұрын

I was thining of something like a social security number as a key so that the demonstration made more sense to me. Entering it would search retrieve a possible name for example.

@BryceChudomelka 3 жыл бұрын

Doug is great. CS50 is an excellent resource.

@kellingc Жыл бұрын

I've seen this before, but as file structures and using a 2-3-4 method. Your first level has two choices, second level you have three choices; and third level you have four. Same concept, just different amounts of oaths. One thing that popped out at me is your use of ten digits perceisly describes the arm of the Strowger dialer. The only thing not depicted with this example is the relays to find the next available Strowger device, to signal the last digit in the number, and a few other cases. This also shows how using a digit for a single use (like 0 for Opertor or 1 for long distance) takes (10^x)-2 posable lines away. Man, I love computer science. Oh, and how would you handle collisions. Say two schools were founded in 1836? Simular tk a has table?

@jingtao1181 4 жыл бұрын

I’m afraid this video, as with some other videos, contains assumptions that are subtle and may be not known to CS beginners. As some comments have pointed out, what happens if there is a collision of year? Maybe a reemphasis on the original assumption is able to make viewers clear or give a solution to how to solve a collision.

@fdc4810 3 жыл бұрын

Normally such data structure is assumed to have bijective relationships, namely if x != y, then f(x) != f(y). However in the cases where you really want to make a tries such that it contains multiple values, you can always call realloc() at the last step to reallocate the string array size.

@jaaan2914 2 жыл бұрын

@@fdc4810 If x != y, then f(x) != f(y) is necessary but not sufficient for bijectivity. What you're describing is injectivity.

@fdc4810 2 жыл бұрын

@@jaaan2914 The "onto" condition is implicitly assumed here, as the the x and f(x) come in pairs in the example of the data structure in the video (x = year, f(x)=university name), hence each f(x) is defined to be mapped upon.

@quotcode 4 жыл бұрын

Thank u so much sir for this really insightful lecture.

@seanlee566 2 жыл бұрын

Man Doug is such a great teacher. But why does the intro have to be so loud and his voice so soft. RIP Headphone users.

@mohammedhamed7466 10 ай бұрын

actually the example David uses in the lecture is more clear than this one, I understood the concept, but where is the code to do so? i still have to look for other resources to find out

@charlielin188 3 жыл бұрын

sir, what if there are two schools founded at the same year? Or should i use hash table instead

@oruchkin 3 жыл бұрын

you can use letters as keys and years as values it will work

@eleos11 4 ай бұрын

Guys I have a question, because I don't quite understand the purpose of these videos. While an intro to "tries" seems really interesting, there isn't any parctice with them. In addition, there aren't any suggestions about freeing the nodes of a try... Am I being reasonable here?

@_dr_ake 4 жыл бұрын

I'm not sure I understand. Wouldn't you get collisions using the year as a key? If so why use that as an example. Can someone clarify for me?

@AllanPichardo 4 жыл бұрын

If the key is the same, then essentially you're replacing an item in your trie. The same would happen in a hash table. In a hash table, a collision is not referring to when you repeat a key. Repeating a key is simply replacing something. A collision in a hash table occurs when, even though the key is different, the hashing function maps it to the same storage location as another existing item. On a trie, if you search for a key like 1750 and 1890, they're never going to collide because you're going first to 1, then branching to 7 then branching to 5 then branching to 0.

@goatdwarfs 4 жыл бұрын

@@AllanPichardo I think the question is referring to what happens if you need to store University A and University B in a trie if they were both founded in 1750? What solutions resolve that collision in a trie data structure?

@AllanPichardo 4 жыл бұрын

@@goatdwarfs Yes, I see. In that case, I would suggest either not using a simple year as the key. Or perhaps, every node can contain, rather than one university name, a collection of universities. You can customize this to fit your specific use case.

@germaniothesmart-alec6056 3 жыл бұрын

I'm not CS guy, but I think its about having a hash-function that cannot collide. In this video the year represent the output of that hashfunction. I am thinking for example of using the ASCII int representation of each char in the string and user that as the key. (use separator character between each int or use fixed length with null padding so you know how the ints are grouped together in order to construct the 'roadmap' correctly) My approach would ofcourse use a lot more memory. Each node would hold an array of at least sizeof(int)*26 if we ignore casing.

@jingtao1181 4 жыл бұрын

In essence, I feel this video makes easy things complicated and complicated things easy. For instance, tries is just a data structure that allows us to store multiplayer of information as long as we make sure that each element has a unique representation. It can have more branches than hash tables and arrays.

@vaibhav3874 4 жыл бұрын

What are you on about? I'm new to CS and this was perfectly clear to me.

@jingtao1181 4 жыл бұрын

@@vaibhav3874 my main question was the university name and university year. University founding years might be the same, but in this video, it was assumed to be different. So that kind of compels to ask what happens when university founding years are different, how can you store the information in tries?

@jingtao1181 4 жыл бұрын

@@vaibhav3874 I don't mean this video series is not good. In fact, they are very helpful. I'm just saying it's confusing for me sometimes.

@r3xtez987 4 жыл бұрын

@@jingtao1181 It's just a simple example to help understand. In the real world you wouldn't use keys which enable collisions so easily

@ns8928 4 жыл бұрын

You should lookup the replies on the comment Michael Neas has putted in this video.

@knightrec869 4 жыл бұрын

Cs50 is best channel on utube.for that student's who r studying.

@itsmikeneas 6 жыл бұрын

What happens if you have a different school founded in 1636 after you've inserted Harvard?

@marjanp 6 жыл бұрын

He says the key (year) is guaranteed to be unique. Otherwise it would overwrite previous value with the new one.

@itsmikeneas 6 жыл бұрын

marjanp okay so in his example he gaurentees uniqueness but in the real world what happens?

@marjanp 6 жыл бұрын

The key has to be unique.

@itsmikeneas 6 жыл бұрын

@marjanp Practically, how are you going to guarantee uniqueness...If you were going to index all the universities by their date founded you will find collisions. University of Pittsburgh - 1787 Franklin & Marshall College - 1787 The larger the data set the more likely a collision. I just wanted to know the common way to deal with situations like this.

@marjanp 6 жыл бұрын

It's a bad example. founding year isn't guaranteed unique. You have guaranteed unique keys in real life like SSN, ISBN etc.

@shashanksharma21 6 жыл бұрын

Explained brilliantly ! Thanks for sharing

@VinceAggrippino Жыл бұрын

Your arrows and colorful boxes are pretty but without some related code it does nothing to help me understand how to utilize it.

@ahmedkamal9695 4 жыл бұрын

thanks for CS50 Team

@atrain3793 2 жыл бұрын

This is not the way that Professor Malan described tries in the lecture, so I am confused. In the lecture, he never mentioned anything about key value pairs, but rather that a trie just had a array of the values that needed to be stored, and each index in the array was a letter plus a pointer to the another array.

@nayankumarbarwa4317 2 жыл бұрын

Because, the array's index was the key present there

@not_amanullah 4 ай бұрын

Thanks

@zyadalharbi180 4 жыл бұрын

Thank you. Very helpful.

@chrischoir3594 Жыл бұрын

These CS50 are great videos but you should number them so we know what order to watch them....duh

@thomasmo98 2 жыл бұрын

thanks doug ily!

@nguyenthanhdat93 5 жыл бұрын

It's over-complicated. Trie is a combination of multi-rooted trees. View this video for easier visualization: kzfaq.info/get/bejne/Y9uigdV6prfSfqM.html

@8o8inSquares 6 жыл бұрын

A subbox spam that I am actually happy to see, thanks for all those videos

@GOODBOY-vt1cf 4 жыл бұрын

THANK YOUR Doug Lloyd

@SujaySiddarth 3 жыл бұрын

You miss one word, you wont be able to get through the rest of the video.

@juwenzel1 Жыл бұрын

Unfortunately, this was not a good example for tries 😕

@HAWHAWH 4 жыл бұрын

What happens if you have collision?

@NeelSandellISAWESOME 3 жыл бұрын

Why does he say chaining is more preferable to probing as a collision strategy?

@ABO_GHANIM1 9 ай бұрын

How about if I want to insert another university that founded in 1636? Do I have to insert it in 0 after I reach Harvard, so it make a list?

@rishavjain5087 2 ай бұрын

i thought tree and tries were two different data structures😂😂

@rishavjain5087 2 ай бұрын

they are actually

@RenanBecker 2 жыл бұрын

If I want the number 123 but I dont want to store 12? How do that?

@rasinshort4817 5 жыл бұрын

thanks sir

@NeelSandellISAWESOME 3 жыл бұрын

Why is he saying trie is constant time if it depends on the size of the number?

@lew162 3 жыл бұрын

Because that number is constant. No matter how many new elements you insert into the trie, a particular element will always take the same amount of time to be looked up. This is different from something like a linked list where with each added element you need to iterate over an additional node (in the worst case) so the lookup time grows with the list size.

@NeelSandellISAWESOME 3 жыл бұрын

@@lew162 thank you!

@kalleskit 6 жыл бұрын

Is this related to Bloom filters?

@Evangielis 6 жыл бұрын

They share a use case, though tries are deterministic as an indicator of set membership and bloom filters are not.

@anfield6321 6 жыл бұрын

Maut in cs50 lul...

@enisten Жыл бұрын

The explanations were maddeningly verbose and repetitive in this video.

@krypto7264 6 жыл бұрын

How do you expect someone to understand the rules that you are saying in the beginning of the video if you haven't even mentioned a single example. This video is more appropriate for people who have a basic understanding of the trie data structure. Otherwise the first part of the video will only sound gibbersih.

@Antonio_611 5 жыл бұрын

this is for edX platform where you're supposed to watch the videos in a specific order

@zerosandones701 5 жыл бұрын

and the lecture that proceeds this touches on tries as well

@Dejoblue 6 жыл бұрын

Are you going to regularly spam literally 50 videos? Deciding if I should ubsub. This isn't a petulant inquiry/threat, I genuinely need to know if this is going to be a regular occurrence and disruption for me. Thank you in advance.

@zerosandones701 5 жыл бұрын

Omg, the first world horror!

@totallynothuman4543 4 жыл бұрын

@@zerosandones701 lol