Video 2-5: §2.5 Symbol tables

0:03 the last part of unit two is about symbol tables and about binary search trees which arguably is the most most useful and most fundamental of all those data structures we covered here and so I think it's it's particularly useful to know about uh it's also just a a beautiful piece of of theory that this works I mean you get used to it so much that maybe it loses all the Marvel and wonder but uh it's Quite a feat that it's possible but let's first talk about the uh the abstract data type that comes with it I asked you this um fun question um let me switch back to it

1:00 briefly so you're uh you're not not young enough or at least old-fashioned enough to have used a physical printed dictionary of course um the reason why I asked about this is how do you find a word in a

1:19 dictionary and we'll come back to that so first of all let's get some some uh terminology straight um uh out of the way so we have symbol tables that's the way I call here and that's the way they're called in the algorithms book the red book that I recommended you to read along for this uh unit if you haven't had this in an undergrad course but there are many other names for the same thing it's important just to know that these are the same okay so symbol table sometimes called dictionary including in Python in Java it's called a map uh it's sometimes also called associative array or key values store is essentially the same often people mean a distributed database instead of something on a local computer but it's uh by the API the same thing so the key thing we can do with this and this is dynamic you can change it over time you can put a a mapping into this into this symbol table where you associate a value V with a key K and in Python you would just write it like this for a dictionary that um is also why it's called associative array sometimes s because it looks by the syntax like an array but the thing you put into the

2:35 square brackets is not a number not an index or an offset but some arbitrary object then if you have a key you can look up what the value is that's associated with this and um simple tables are fundamentally single Valu so every key is associated with one value or maybe no value if it's not uh contained but if you call put several times with the same key it will just overwrite the previous mapping you can also remove a key in its mapping again and you can check whether something contains uh a given key whe the dictionary or symbol table contains a key of course you could also check what get returns and if that says uh I don't have a mapping for that key uh you also get the same answer as for contains that's just to make it more readable as I said it's a fundamental building block for prob I can't imagine a program that doesn't sometime in some way use one of these data structures indirectly at least very fundamental and okay I don't I don't think I know a programming language that doesn't have a library that contains a symbol table in one form or another now there are many esoteric programming languages maybe there is one out there but not if if

3:53 it's in Practical use for real world problems it will have a symbol um it's useful to uh make the distinction between simple tables and mathematical functions because they're in a way very similar both you give a value and then you get a um a mapping you put a key and you get a value out for mathematical function we say also you just put one key in and get another key out so they look a bit similar but the big difference is if we think of mathematical objects we think of them as immutable these are values that don't change if you take the number five and add one it's no longer the same number five it becomes a value six but the five isn't changed whereas uh data structures in computer science and specifically our symol tables we assume that they can change so you can change the mapping of a key so you can think of it as a dynamic function or dynamic mapping if you want just want to get that uh make that clear so it it has the similarity to functions but changing over time is the difference so we have a new abstract data type the symol table how can we implement it what kind of data structures are there to implement

5:11 it now let's look at the simplest possible ways first again we could use an unordered list say a linked list I shouldn't matter that much I can hear me a lot is this is that still loud enough no complaints either way so I'll take it as a yes until someone complains let's take an unordered linked list and uh when we put a new a new value key value mapping in we just stuff it at the end that's fast yep well unordered here just means I don't care about the order uh it's it's in contrast to the other option that will come so what it means is uh I keep you you say put um hello five then I'll just create a new entry in my list that has the key and has the value and it's somehow linked with pointers so if you do another put a Zer then I'll just add another thing at the end of this linked list

6:34 and there's no specific order maintained in the list the newest thing is just at the end that's the way it's meant not it's not sorted it's also not random we don't deliberately randomize it it's just the order in which it is inserted but unordered here stresses the fact that we don't specifically impose an order that's that's all it says so you can't guarantee anything which means put is fast because you just uh put it at the end of your list but if you want to find the mapping for a key the best thing you can do is just go through all the mappings check with each key is this the key that I'm looking up if no you keep going if yes you return the the mapping that you found but actually even H even in that case you have to go through the entire list and check if there's another mapping with the same key because you should return the newest one so there's a second problem lurking this might grow over time even if you just put in the new key so you might need some some cleanup calls and so on I'm not even listing the details here because this is so slow it's not interesting if that's the best we could

7:48 do symbol tables wouldn't be a thing the other alternative that we have is using some sorted thing and um I put here again sorted link list to emphasize this uh because um if we want a sorted list but we want to insert something in the middle we can't really use an array we've had this problem last time we discussed it in a bit so you can append to an array using this doubling array trick but you still cannot insert in the middle of an array without moving all the elements so either way we do it either link list or an array will get us linear time worst case for for put even if we know where we want to go because we have some fast way to find it it doesn't help uh if we use a linked list then certainly also get is just as slow as before the sorted didn't really help us there at

8:55 all right sorted here means sorted by key although because it didn't help here at all it doesn't actually matter matter but uh going forward sorted will always mean by keys but I I'll comment on that again so the the strange observation here seems at first sorted this doesn't help us because um just a simple simple way maintain something like an array where you can quickly access Elements by index but also insert in the middle that's already a tricky problem that we haven't really solved so far but we'll see by search trees actually solve

9:39 that yeah that's that's the point um it would help us if we could somehow jump into the middle right I know I know you you all know this so let me let me move ahead there's of course this thing called binary search and I asked you about the physical dictionaries because of that how do you find a word in a dictionary you do something like a a human guided uh binary search I guess no no human does exactly binary search like opening the book in the middle checking if you're to the left or to the right of the current page we do something with the starting starting letters uh but it's not too dissimilar but let's um to be self-contained um let's briefly go through this um more formally so if we have somehow an array of sorted elements and here I'm only listing the keys there is an a second array that Associates the values with those if you want um we'll ignore that for now as in the case of the heaps because it doesn't actually make the data structure more interesting uh so here we have these keys in sorted order let's try to search for some key say as 69 so what binary search would do is uh you jump into the middle that's this m

10:55 index m is basically the middle between l and m somehow rounded if it's if it's between two H so here we would have uh checked 63 and 63 is less than 69 what that means because of the sorted is everything that's left of 63 including 63 itself is excluded if 69 is in the array it is not in the left half because all of those are too small that's the key trick of binary search and then the rest is just uh putting this into a nice recursive algorithm that nails down the remaining range of the array so uh after this we can update L to the position to the right of that then we get a new M so we can again do one comparison with that now that's bigger than 69 so we know the 80 and everything to the right is excluded if 69 is in the array it is not in the right part of this in the right half of the right half so we narrow it down further we do another check 77 still too big so we exclude again these two and then we've narrowed it down to a single value that we can just check and in this case of course we find the 69 that's binary search uh I hope this

12:18 wasn't new for anyone uh I hope also it wasn't too boring for anyone so what we do is in each step we roughly have the remaining in number of elements plusus one because we can't if it's an odd number we can some sometimes not work our way around it uh but if you do if you do the math a bit more careful the number of comparisons so the number of times you have to check something against your key that you're looking for uh is at most log n the number of things you have rounded down plus one okay that's the number of times you have to cut n in half before you're at one by en llarge and then the plus minus ones you have to do the math so that's good that's great actually right log n is very small compared to n and all we previously had had linear time get or put so that's great uh it comes with this restriction or this caveat what we needed to do binary search is being able to jump into the middle of the array and in so far sorted this helped us for this uh but sorted is a problem if you want to insert into this array and it's still an array so so far all we've seen was

13:37 either random axis with an array where we can jump at any position or quick up quick insertions in the middle but then it's a linked list and we can't use random axis as I called it here so Random axis it's maybe a slight misnomer it should be called access Fast Access by index uh but that's why we call ram ram it's the random access memory where you can do accesses by index fast as opposed to old old Magnetic Tape right this also existed uh so it's maybe not the greatest term but it's it's so established that I I kept it what's meant is you can jump to position 17 in one go good everyone with me so we'd like to have this fast search but uh we can't really do it um with in the