Video 2-1: §2.1 ADTs, Stacks and Queues

0:00 <Untitled Chapter 1>

0:04 so welcome back to com526 efficient algorithms uh in unit 2 we'll talk about some fundamental data structures that will be a recap for all of you who have seen some undergraduate level algorithms and data structures class but some of these are just so beautiful I don't want to not talk about them in case some of you have not seen them and will also build on some of them a little bit later on so it's it's worthwhile going through this I want to point out that this normally fills half a semester or so of lectures if you do this at the normal speed in undergrad courses so we'll we'll have to race through this fairly quickly over the course of this and next week uh there's much more information in the the red book algorithms fourth edition and in other books and there's nice lecture videos on this topic so if you haven't seen all of this before I think you you might um you might need a little extra time preparing this on your own and there's this ample good resources for that I don't think you can really grasp that material in the time I presented here if you've never seen it before I apologize on the other hand two-thirds of you have seen it before

1:15 and so I'll try to not uh spend too much time on it but maybe give you a a few you know perspective and angles that um are not always taught in undergraduate courses uh you'll be my you'll be my judge then

1:34 Learning Outcomes

1:35 so the learning outcomes for this are first of all something that also the the prerequisite survey touched upon I want you to have an understanding of what an abstract data type is and what implementations or data structures are there's a few really fundamental abstract data types that you just should be able to talk in terms of that's the computer science vocabulary we'll look at a few concrete implementations um I think for these that's not so important for now because you will see what these are as we go along and the hope is that you get the the gist of how they work foreign the unit has quite a few different subsections I'll try to have one video per subsection so to not make the videos too long many small sections but let's get started it's not long ago but let's recap the Machine model

2:13 Outline

2:25 Recap: The Random Access Machine

2:39 the slides are always on the website they're not always on the website H is in advance but I'll try to be a good boy I think this one should be on on the website now or at least some slightly outdated version of it uh so that's that's a new slide I added because I felt after one or two weeks sometimes this Fades so we're working on the random access machine however uh we'll have to assume a few other things a little operating system working on this what the machine can do right away is basic pseudo code so simple python constructs will just assume that they have the natural meanings uh then we assume that we can create arrays so contiguous pieces of memory filled with identical sized pieces of data but only if we know the size in advance that's the basic assumption that I think all memory management systems I know of uh make you can ask for a piece of memory if you tell me how big it is and then usually it's hard to change that size afterwards you can you can get a new one if you need more

3:53 um and a Twist on that is you can create instances of a class so if you say I have a class with several Fields that's essentially saying I need an array to cover all those fields or a contiguous piece of memory to cover those fields so in a way the two on a low level look the same um but we'll use different pseudocode for convenience

4:14 a little caveat here is that python abstracts some of this away there are no real arrays in Python full stop just doesn't exist um everything in Python is a list which has a variable size so you don't have this problem that you have to know the size in advance python does this under the hood for you and we'll talk briefly about how it does that so uh what this means for us we can basically assume we're writing python code but when you analyze it not everything you can write in Python in a single instruction or even a single line takes constant time some of the things that python offers for you as a convenient thing is actually really slow and that's something to keep in mind uh especially if you're building data structures on top of that you need to you need to be able to pierce through the abstraction and see what's behind to understand how fast or slow it is

5:18 Abstract Data Types

5:18 let's start um with Adam and Eve with the basics and um so that's that's the first important definition for today what is an abstract data type or ADT that's the thing that occurred in the in the prior knowledge survey

5:36 an abstract data type is a fairly uh conceptual thing it's a list of operations which tells you what should happen if you execute these operations but it doesn't tell you much more it doesn't tell you how fast it is it doesn't tell you how you're supposed to do it it doesn't tell you how the data these operations work on are stored all of that is contrasted with data structures these are concrete implementations often abstract data type or maybe several abstract data types and data structures do have to specify exactly how things are represented what are the algorithms you use to implement the operations and as a consequence data structures have concrete performance they have running time for the operations they have space cost whereas an abstract data type doesn't have that because it can be implemented in different ways if you want an analogy from programming then abstract data types are closest to Something in Java called interfaces or abstract-based classes in Python so there is a notion of of this in Python but I think it's one of the least used features in Python I know of uh and I'm not even sure if this is taught in the intro to programming the fund programming fundamentals module but it exists so in case you're in

6:59 Python expert you can map it to that if not think of it as the description of a class with names of the functions and that's it no implementations everything is just pass that's the closest I think I can I can say and well for for data structures that's easier it's just classes usually so um data structures are in a way quite conveniently mapped to object-oriented programming you don't have to do it that way but it's a very nice correspondence

7:42 why do we bother about this why don't we just do data structures the code that runs at the end of the day always is data structures because These Guys these abstract data types they cannot run there's no code so why bother uh the it it just turns out it's a good engineering principle to have a clean interface to say what you need and leave it to someone else to figure out how to best do it and what best means can change so you sometimes get statements in in libraries this is a drop-in replacement for a built-in data structure for some for some purpose uh okay I don't have a really brilliant example in mind now it just means that you get reusable code the code that uses a data structure doesn't need to know what the data structure is like as long as it only uses the abstract interface so he can swap out the data structure in the the client code that uses it can remain completely the same that's really useful if you're writing big pieces of software the only way we know to tackle complexity in software is to decouple things have isolated units that you can swap out and understand in in isolation

8:55 it also happens to have some knock-on effects it just turns out to be useful to have names for certain abstractions so that you're not always talking in terms of bits and bytes and adding numbers on bits and bytes uh people get better at uh solving bigger problems if they have higher level abstractions to throw at it and then the theory thing if we have an abstract data type we can sometimes prove that there's no no implementation better than a certain lower bound and we'll see some some example of that uh and there's there's many many more in in the research literature and here again the notion of an abstract data type really is is fundamentally needed there otherwise you wouldn't you wouldn't know what what all algorithms really means here

9:49 good uh that's a lot of advertisement uh sometimes it's a bit like in in this picture that you have a very really nice interface and what's behind it is very rudimentary and sometimes it makes sense to break the interface up and look what is inside so that's in a way the argument against building cars with the hood uh sealed so that you can never open it uh the same happens in programming if if everything is too closely knit you sometimes Overlook uh

10:25 opportunities so say someone wanted to water their plants and so if they only see the interface they have to carry this ball around fill it 100 times right whereas really the thing is just an interface for a hose that you could have pulled out and that's that's uh why I put that picture I found that found that funny and sometimes this happens in computer science so adts are great but be wary that you don't get too narrow in your thinking only when it helps

11:05 again no trick question this is just uh testing both a have you heard these words before and B have you internalized some of what I've just said all right it's a long list I think you need a minute

11:50 let's try to get at least the 60 from before you more almost there uh we've always got some votes uh and they don't even fit on the screen how small can we go before you can't read it anymore you'll be fine right my slice is probably smaller fonts all right

13:23 so you can you can check for yourself if you get those right and let me briefly run through this so ADT is the name of the thing right uh stack and deck are adts a linked lists the data structure same for binary search 3Q is an ADT again that's a data structure that's a data structure that's an ADT uh okay so basically all that are crossed out are data structures concrete implementations of some of these I think we'll talk about most of these in this unit with a few exceptions so you'll you'll fill the gaps if you had some

13:58 Stacks

14:01 let's talk about the first of these beasts arguably the the most simple one uh a stack as the picture suggests um it could be a stack of books and the problem with this kind of arrangement also popular in in my office occasionally you can't really get conveniently at the books at the bottom so in a stack the operations that we support are listed here we can get the topmost item without changing the stack so just look at it we can add a more a new item on top of it so just put another book on top we can pop which means take the topmost item off and it's gone from the stack and we can test if the stack is empty and we create can create new empty Stacks that's this for uh making it a complete data structure a compute complete ADT uh other is is it clear what the operations are supposed to do now notice I could explain this on a stack of books just because it's a useful metaphor to remember this but I haven't really said how the data is represented or how the operations are supposed to be realized in a computer and there are different ways how to do that before we get to that okay this is

15:14 Clicker Question

15:18 almost yeah all right let's do it uh this later is so much fun um there's a little question just to check if you uh if you understand the uh the operations correctly

15:39 okay so the stack looks like this one is at the top two three four five that's what it looks like initially okay it seems um so so many people got this right instantly so maybe it's uh it's as I hoped uh the first pop removes the topmost then we're left with this the second pop removes the topmost so we're left with whatever's not crossed out and then push adds another one on top so we have the one and the rest is the same and now well my my way of writing this is uh top down so one three four five that's this one and that's what most of you found as well

16:56 goody uh or maybe for the to prove for the video uh almost all of you honed in on this one so that's a stack great we know what a stack is supposed to work like how can we build a stack

17:17 the simplest easiest way to build a stack is using a linked list now if you already know what linked lists are like you say yeah I've done clear if not let me try to briefly explain what it looks like um the key idea is to use a helper class that we use to represent data so here I created a class node so this this is this is proper is almost python code I think the prior knowledge survey had pretty much this example as python code with some things renamed to confuse you a bit so we have a class node that has two uh Fields so two instance variables one value and a pointer to another object and then the stack is is realized um by just a single pointer to the topmost element

18:10 um let me try to draw this a little bit so I'll try uh to have the two fields in the same order so value first and then next below and these kind of diagrams uh you can you can imagine I create a new object and it's just floating in in space so when I say a new object is created like in in this line 10 we just get a new box that we can fill and that we can point to so our stack the representation of the stack itself is just a single variable top that points to some element

18:58 and I'll draw this like this and then uh so that's that's a legend let's put it here so the initial stack was empty the top was just pointing nowhere that's a null pointer say we had called push with a value 42. then we would create a new node and put in the first field this value 42. and we point uh we put in the second field whatever top point it took before which would have been null uh initially if we call this one more time then I don't know say push 17. we would call this new note now top points to this so uh we have to as next we now get whatever top pointed to before and then we rewire the pointer from top to point to this new element that's one uh that's two or two two executions of of push and you can imagine how pop would be would be similar if you just follow the code you keep hold of where top pointed to before and then you rewire pointers the way the stack can grow and can shrink each element points to its neighbor below it in this in the stack that's all really you need to move up and down yep

20:39 yeah there should be it's empty and and create so create we may not really need if you can just say new stack uh empty is yeah empty is missing but you can figure out how you would implement it here uh I focused on the on the more interesting operations

20:55 but there would also be an is empty it's just a below the slide okay are we happy with this implementation uh let's see how how well it does uh first of all if we have n elements in the stack it requires Theta of n space because it requires one of these objects for each element on the stack that's not that bad because at least we don't require much more space than the number of elements we have and what's really good all operations are constant time because we just create a new element and rewire up a single pointer and for for pop as well so these are all uh constant time um if the memory management is constant type and that's as good as we can get the only thing that's sometimes inconvenient is the same statement here is also a downside we do have these extra pointers for every element we have one extra pointer and we have to store that so that's a bit bit of wasted space so if this uh stack is growing really really big and maybe also if the elements we store are really small it would be nice to get away from these extra pointers

21:05 Linked-list implementation for Stack - Discussion

22:24 Array-based implementation for Stack

22:28 now if you don't want any pointers the only thing we can really do is use an array and it's possible to use an array in this case the idea here I left out the detailed code you can find this in in the in the books I referenced I try to I wanted to have at least one example with concrete code on it to show you what what the pseudo code looks like that I would use it's quite close to python or other languages and for those I'll leave it with the conceptual idea so uh we can store one one big array

23:07 has all these all these cells and the other bit we need is one one index or one pointer into the array that tells us where's the topmost element so far so if we have our array from before 5 4 3 2 1. then top would point to this position if we want to add another element we write it in here and we rewire top to point one further further up if you want to pop an element we just bring top one down that's another easy way to do it the operations are still constant time because we're just changing one point or one index and we can access the array in constant time we can jump to a specific position now uh the problem with that is arrays have fixed size that's the Assumption from before so what do we do if the array is full and we want another push then we're a bit in trouble and with this simple implementation you just have to live with it it has fixed capacity and so if you want another push you're in an invalid State and there are implementations like this that can just throw an exception in that case so we need at the time of creation of such an array-based stack we need to fix

24:31 the capacity that's another annoying bit of it though uh we always reserve the space for the entire capacity even if we only use up a little bit of it so it's actually more wasteful in terms of space than the previous solution unless we're at least half full or so but the operations are probably even faster because we don't have memory allocation inside the operations

25:02 now of course uh the natural question is can you get The Best of Both Worlds can we have the fast access to the array and at the same time still be able to push as many elements as we like without running into this fixed capacity