Tries - CS50 Shorts

***

This is CS50, Harvard University's introduction to the intellectual enterprises of computer science and the art of programming.

***

HOW TO SUBSCRIBE

HOW TO TAKE CS50

HOW TO JOIN CS50 COMMUNITIES

HOW TO FOLLOW DAVID J. MALAN

***

CS50 SHOP

***

LICENSE

CC BY-NC-SA 4.0
Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International Public License

David J. Malan

[BryceChudomelka]

Doug is great. CS50 is an excellent resource.

[jasonbellis]

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.

[quotcode]

Thank u so much sir for this really insightful lecture.

[knightrec]

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

[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?

[shashanksharma]

Explained brilliantly ! Thanks for sharing

[klausbrandenburg]

Wait? One Trie is about 10 x 8 Bytes of structs (without the char *) and I need 5 nested instances before I can write "Harvard". So thats 10 ^ 5 x 80 Bytes to store one item?

[mohammedhamed]

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

[jingtao]

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.

[seanlee]

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.

[jingtao]

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.

[eleos]

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?

[oinSquares]

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

[charlielin]

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

[chrischoir]

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

[ABO_GHANIM]

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?

[atrain]

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.

[_dr_ake]

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?

[itsmikeneas]

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

[BOTAimBotz]

I wish the intro music wasn't so loud.