This is the sense in which we want to maintain the order. Length will just return this fixed value n. Methods are the object-oriented way of thinking of operations that your interface supports.
Because somehow, we have to specify n to this data structure, because n is not going to be allowed to change. And I want to make a new data structure of size and a new static sequence of size n that has those items in that order. I'm going to want to also know its length. Exactly how you specify x isn't too important, but the idea is, I give you some items in some order. To build a data structure in this interface, you call build of x. So what do these do? Build is how you get started. And the operations I want to support are build, length, iteration, get, and set. I'm going to label them x 0 to x n minus 1, as in Python. This is where the number of items doesn't change, though the actual items might. I'm going to start with the static sequence interface. There's a few different levels of sequences that we might care about. Let's jump into the sequence interface, which I conveniently have part of here. I'll come back to this sort of highlight in a moment. But we're going to see both of these today. They're used a lot in programming, of course. One is arrays and the other is pointers- pointer-based or linked data structures. On the other hand, we're going to have two main- let's call them data structure tools or approaches. And in the next several lectures, we'll be bouncing back and forth between these. But we're going to be actually solving sequences today. Today, we're going to be focusing on this sequence data structure, although at the end, I'll mention the interface for sets. And this is the first item, the second item, the last item. In Python, you could store that in a list, for example. Maybe we want to represent the numbers 5, 2, 9, 7 in that order and store that. And on the other hand, we care about representing a particular sequence that we care about. And maybe we want to maintain them in sorted order and be able to search for a given value, which we'll call a key. And on the one hand, we care about their values. I guess there's not a Python sequence data type built in. It means something else to a Python programmer. One is called a set and one is called a sequence. We're going to think about two data structures. And depending on what you actually use those data structures for, you choose the right data structure. They might support some operations faster than others. And different data structures are going to have different advantages. The same problem can be solved by many different data structures. And this is the analogous notion for data structures, where we want to maintain some data according to various operations. Yesterday- or, last class, Jason talked about problems and defined what a problem was versus algorithmic solutions to the problem. Because- you can think of this as the problem statement.
#DIGITAL NUMBERS HELP US TALK ABOUT THE ORDER OF THINGS HOW TO#
The idea is to separate what you want to do versus how to do it. In this class, we're going to focus on two main interfaces and various special of them. And the data structure actually gives you algorithms- this is where the algorithms come in- for how to support those operations. In the interface, you specify what the operations do, what operations are supported, and in some sense, what they mean. What makes it interesting is having operations on that data. You just throw it in a file or something. So the interface will specify what data you can store, whereas the data structure will give you an actual representation and tell you how to store it. And in the context of data structures, we're trying to store some data. The idea is that an interface says what you want to do. But before we actually start with one, let me tell you/remind remind you of the difference between an interface- which you might call an API if you're a programmer, or an ADT if you're an ancient algorithms person like me- versus a data structure. This is the beginning of several data structures we'll be talking about in the next few lectures. We're going to talk about sequences, and sets, and linked lists, and dynamic arrays. There's lots of algorithms in each data structure. ERIK DEMAINE: Welcome to 006, Introduction to Algorithms, lecture two.