2. Data Structures and Dynamic Arrays

MIT 6.006 Introduction to Algorithms, Spring 2020
Instructor: Erik Demaine
View the complete course: ocw.mit.edu/6-006S20
KZbin Playlist: • MIT 6.006 Introduction...
Data structures are ways to store data with algorithms that support opperations on the data. These collection of osrted operations are interfaces. This class goes over two main interfaces: sequence and set.
License: Creative Commons BY-NC-SA
More information at ocw.mit.edu/terms
More courses at ocw.mit.edu
Support OCW at ow.ly/a1If50zVRlQ
We encourage constructive comments and discussion on OCW’s KZbin and other social media channels. Personal attacks, hate speech, trolling, and inappropriate comments are not allowed and may be removed. More details at ocw.mit.edu/comments.

[@pantheonCaspian]

This man's enthusiasm for algorithms is what I want in my life.

[@unorandom3009]

I've been listening to this guy teaching algorithms for over 10 years seems his age algorithms is super efficient where his age is always constant O(1)

[@factfinderchannel9965]

It will be exponential time his age algorithm efficiency if you keep following his course for the next 20-30 years.

[@michelealessandrini3421]

Maybe it's amortized constant, one night he suddenly becomes old.

[@unorandom3009]

@@michelealessandrini3421 exactly he look the same after ten years that's why it's constant O(1)

[@OscarMartinez-nt6zn]

@@unorandom3009 but with amortized someday all of a sudden he will need to grow and become O(N)

[@primaryesthethicinstincts4832]

You've been learning algorithms for 10 yrs??

[@ParthPatel-vj2zv]

0:00 : intro 0:50 : interface vs data-structure 5:50 : static sequences & static arrays 16:50 : dynamic sequences & linked-list 25:20 : static array vs linked-list 34:25 : dynamic arrays (lists in python) 46:27 : amortization

[@MrApolloIII]

Shout out to the camera man! For panning to the information he’s referencing that we can’t see!

[@domemvs]

Thanks to the MIT for making this available for free. This is a very selfless move. Amazing

[@georgejetson9801]

This is what passion looks like. I got my CS degrees at the first boom/bust cycle in the 80s. I've enjoyed everything about this career.

[@RurikLoderr]

I've been programming on and off since high school (class of 2003) and recently decided to catch back up with the MIT OpenCourseWare lectures... 10:05 to 11:17 is the first time I've ever had zero indexing explained in a way that just makes it clear that's why it's being done. Never in my entire life had anyone just said it was an offset in memory and I'm kind of disappointed. That single simple fact of something I thought I knew well just made a whole lot of memory addressing knowledge grok immediately.

[@anastasiyauraleva8123]

sameee!!!

[@dcpugh]

Awesome lecture! A treat to hear a talk on basics by such an accomplished computer scientist!

[@ssaadhussain902]

This lecture was so brilliant. The concepts are crystal clear.

[@yeboahdominic1896]

In fact I have been watching a lot of tutorials from this channel and this professor is one of my favorites.

[@FlexGC]

Yes he's great. He is / was also a prodigy. I think he got his bachelors when he was still a teen.

[@noelcovarrubias7490]

@@FlexGC no way? O:

[@MufaddalHakim]

@@noelcovarrubias7490 He became a professor at MIT when he was 20

[@nadiatalaat3561]

@@FlexGC which programming language he explain with ?

[@1ncandescence737]

Oh my! Was wondering when we are getting a refreshed version of 6.006!

[@HulkRemade]

I love the way this guy writes on the board. It's so satisfying.

[@hanyanglee9018]

Oh, oh, I'm so happy. Years ago I downloaded the old videos and tried watching on metros. I quit at around 1/3. It was too hard for me. Now I'm back. Let me try learning this again.

[@shankar7435]

Never got a chance to listen to lectures at IIT. I am lucky enough to learn from even quality lectures. Thanks to MIT.

[@ayushbhardwaj2708]

kzbin.info/aero/PLBF3763AF2E1C572F&si=idwQNxg_A75C6hdz Even IITs have a combined open courseware.

[@otmaneer-ragragui4458]

Thank you so much for not enabling ads in this videos

[@shankar7435]

I experienced the fact that when you listen to passionate people, you would love to become passionate. This is the ultimate benefit I am taking away right now from this lecture.

[@diannadimambro2188]

saw his 2005 and now his 2020. such a great professor!

[@harshitarawat8941]

__sizeof__ > 1 Len : 48 size, any addition > +8 with append resize at : 1st , +4, +4, +8

[@tetelim4428]

I really love Erik's style, so charmmmming

[@meguellatiyounes8659]

his series on dynamic programming were great

[@SalesforceUSA]

I don't know why KZbin recommended this to me, but I stayed for the whole lecture.,,

[@droneguy69]

I’m glad I saw this video. Thanks MIT for this. I just went thru algs and data structures and I think this is better than the one that I took.

[@eliel10268]

He is very energetic. I have now great teachers!

[@chiro5533]

Thanks MIT for this open Course, amazing!

[@vam8775]

Knowledge Heavy Playlist... 💥 Every computer science student fav track thanks to MIT Ocw

[@programming5542]

please do it for 6.046 and 6.854 the algorithm trilogy by the way good to see you pro eric my lockdown i spend time with your course 6.006 6.046 and the advance data structure and in the last lecure online algorithms . please mit ocw it is my request

[@NazriB]

Lies again? Meds DarkX

[@wpontius4355]

Working with Python and C++ counting from 0 to n, 0 would be your 1, 1 would be your 2...etc. His counting would give you n+1 (0,1,2,3,4), you want n-1 (0,1,2,3).

[@user-mc3el6ik3c]

WOW! I HOPE I CAN WATCH THIS ALL! AND COMPLETE THE COURESE

[@user-tl8gq3gl2n]

It is brilliant, I Love this method of learning ,thanks for MIT.

[@kudurmalla]

Great lecture. Thanks!

[@baigsab748]

Thanks for providing such awesome opportunity for learning

[@deletedaccount2580]

I am fan of this genius guy ,Eric 🙏🙏

[@cryptoaddict6715]

Thank you. I love this course.

[@rishiravi7312]

thank you very much sir for wonderful teaching

[@hadesunseen6388]

thank you for sharing such awesome content, its a real help for people like me who cant afford such higher studies

[@sharvyahmed]

Brilliant lecture 👍🏻

[@user-ib5ml1vz5r]

There is difference between ADT (Abstract Data Type) and DS (Data Structure). ADT is the specification. It answers questions "what data can be stored" and "what can I do with them". DS is the concrete implementation of ADT. DS specifies how data is stored (its layout) and what kind of algorithms process them. Single ADT (array, e.g.) can be satisfied using several DS (linked list, static array, etc.)

[@user-ib5ml1vz5r]

There are 2 main ADT: Set and Sequence. Set does not allow to receive an item via index; Sequence does. (what can I do with them?) Notice that the absence of indexes entails the inability to distinguish between two identical elements. Set does not allow to store dublicates; Sequence does. (what data can be stored?)

[@user-ib5ml1vz5r]

There are 2 main approaches how to construct DS: using an array or using pointers. In the array, data store in continuous part of memory. In the pointer-based approach, each item has links to some of others; physical addresses of items is generally unknown.

[@user-ib5ml1vz5r]

Static Sequence Interface (SSI) is an ADT, the variant of the Sequence. This interface maintain fixed number (aka length) of items x0, x1, ..., x(n-1), but these items are able to be rewritten. The list of operations of the Static Sequence Interface: build(X): make new DS. X is the something that may yield items one by one. len(): returns the n. iter_seq(): outputs the items in its order. get_at(i): returns the item number i. set_at(i, x): set x as the item number i.

[@user-ib5ml1vz5r]

Static Array is a DS, an obvious, natural way to implement the Static Sequence Interface Here and forth, we assume that our model of computation contains RAM with w-bit cells, where w=length of the word, group of bits the processor can to process per one step. The access to each cell takes equal time. Also, our model allows to allocate n sequential words in RAM in a Theta(n) time. Static Array is the consecutive, continuous part of RAM with constant length. array[0] = memory[address(array)], array[i] = memory[address(array) + i] for i from 0 to n-1. len, get_at, set_at operations have Theta(1) time complexity build, iter_seq have Theta(n).

[@user-ib5ml1vz5r]

Dynamic Sequence Interface (SSI) is an ADT, the variant of the Sequence. This interface maintain number (aka length) of items x0, x1, ..., x(n-1). The list of operations of the Dynamic Sequence Interface: [all of SSI operations] insert(x, i): transforms the sequence to y0, ..., y(n), where y0 = x0, ..., y(i-1) = x(i-1), y(i) = x, y(i+1) = x(i), ..., y(n) = x(n-1). delete_at(i): transforms the sequence to y0, ..., y(n-2), where y0 = x0, ..., y(i-1) = x(i-1), y(i) = x(i+1), ..., y(n-2) = x(n-1). So-called convenient operations insert/delere_first/last may be considered an implemented via special algorithms.

[@labeeb_ibrahim]

Has anyone got a ZIP of all the lecture notes? I usually found it on MIT OCW website. But not for this one.

[@nehaliacharya7257]

I think cracking a FAANG company will become a reality very soon. Thank you so much @MIT for these brilliant lectures.

[@andiuptown1711]

Update? 👀

[@user-xl6hx8lb7g]

update please...

[@andiuptown1711]

@@user-xl6hx8lb7g *They flipping burgers somewhere 🗿*

[@random-0]

Amazing, great lecture

[@boiledpotatos4828]

this is actually fun to watch

[@shivamjalotra7919]

My man is back.

[@enisten]

Erik Da Man!

[@factfinderchannel9965]

Great intro to computational complexity

[@stevesmith2553]

array start with - zero , one etc

[@hunternoah95]

The GOAT is back!

[@y2k898]

High quality free information, still useful after I working 10+ years

[@atharvsingh6901]

Finally I'm a student at MIT😊

[@kritgrover3716]

Great content!

[@VigyanBharat]

Awesome content!

[@thehvhnk]

Erik in the house !!!

[@AnkitMishra-hd5uu]

Where I will get full video of this guys

[@sumandangol0286]

🎯 Key Takeaways for quick navigation: 00:28 🧠 *Today's focus is on data structures, specifically sequences, sets, linked lists, and dynamic arrays.* 01:27 🗂️ *Interface defines what to do; data structure defines how to do it. Data structures involve storing and manipulating data with specified operations.* 02:51 🔄 *Two main interfaces: sets and sequences. Multiple data structures can solve the same problem, each with different advantages.* 05:43 📊 *Static sequence interface includes build, length, iteration, get, and set operations. Focus on static arrays as a natural solution.* 08:34 🧮 *Static array relies on the word RAM model, allowing constant time access. Memory allocation model assumes linear time for array creation.* 17:04 ➕➖ *Dynamic sequence interface adds insert and delete operations. Introduces the concept of insert_at to maintain indexing consistency.* 19:56 ⏮️⏭️ *Special cases like insert_first, insert_last, get_first, set_first, get_last, and set_last are introduced and can be more efficient to solve.* 21:20 🔗 *Linked lists, composed of nodes with item and next fields, are introduced as a data structure to implement dynamic sequences.* 23:17 📚 *Arrays and pointer-based data structures were discussed, highlighting the use of pointers as indices into the memory array.* 25:33 ⏭️ *Dynamic sequence operations were explored on static arrays and linked lists, revealing the challenges of insertion at the beginning for both.* 29:51 🔄 *Linked lists excel in insert and delete operations at the front but struggle with random access, making operations like get and set inefficient.* 33:51 🔄 *The lecture introduces dynamic arrays, aiming to combine the advantages of linked lists and static arrays for efficient operations.* 35:14 🧠 *Dynamic arrays relax the constraint that the array size equals the number of items, allowing for efficient insertions at the end in constant time.* 40:12 📏 *The lecture discusses resizing strategies for dynamic arrays, emphasizing the importance of choosing a constant factor larger than 1 to avoid frequent resizes.* 43:31 ⏱️ *The amortized analysis of resizing dynamic arrays is explained, revealing a geometric series summing to roughly linear time, emphasizing the efficiency of the strategy.* 45:51 🔄 *Geometric series are dominated by the last term, allowing for simplified analysis using theta notation, such as theta of the last term like 2 to the log n, which is theta n.* 46:45 📈 *Amortization is introduced as a way to analyze the average time of operations over a sequence, considering that while some operations may be expensive, they are balanced by cheaper ones, resulting in amortized constant time for certain operations.* 47:42 📊 *Amortization is described as an averaging concept over a sequence of operations, allowing for high-cost operations like resizing to be distributed across the cheaper ones, achieving almost constant time on average.* 49:38 🔄 *Dynamic arrays achieve constant amortized time for operations like insert_last and maintain constant time for get_at and set_at, showcasing a balance between the strengths of arrays and linked lists.* Made with HARPA AI

[@soyciro4623]

The instructor goes so fast! I can't actually get the idea or the theory. It looks like I should have a prior knowledge. Thank you for the content, though. It's really appreciated.

[@iagobarretoc8194]

my native language is not english but actually I did understand a lot from this. You can always rewatch, to understand more. Also to see/hear things you didnt notice previously

[@SuperOnlyP]

this will help: kzbin.info/www/bejne/aIWQcpJ9e9qiitE . Here is the whole list for the course: kzbin.info/aero/PLhQjrBD2T382_R182iC2gNZI9HzWFMC_8 to have some basic idea how to use pointer in c. ideally, you need to manage the memory block in ram to create your own data structure. You can allocate memory statically or dynamically.

[@mytech6779]

Yes. Many colleges seem to list prerequisites only as a way to make more money on tuition costs. Example, my local college requires an introduction to CS class before all other CS classes, but then they waste time in the following classes to duplicate all of the lessons in the introduction class. They also require english 101 without regard for score on your placement test, mainly to give money to the English department, while in math you may skip to the level of your test score. ) MIT is different, when they list a prerequisite for a class it is because the class is truly designed with the assumption of specific existing knowledge. I ignored this one time and I needed to take an emergency class in calculus on the side so that I could keep up with my primary class.

[@jackmiller9829]

nice course

[@mingx009]

So great lecture in really giving you why and how, not just a bunch of hows. One question: delete_last() of array seems to me to only take O(1) constant time if choose to do so. I understand insert_last(x) would take O(n) time as a new array has to be created and copy all old elements (and inserted x) to the new array. But deleting the last one would still maintain the old array untouched for the first n-1 elements, and what only needs to be done is to update the len(static array) now to be n-1. Do I miss anything?

[@saararamzy8045]

Even I have the same question!

[@OscarMartinez-nt6zn]

In min 27:00 to 28:00 he explained this, but to sum it up basically though it seems like a O(1) operation it's not because a static array has a fix length and if you remove the last element then you are changing the space of memory that you were assigned meaning that the computer has to reallocate the memory to satisfy the new length of your array for that reason it's not convenient to use a static array for dynamic operations.

[@sirius7584]

동적 배열 - Relaxation of a contraint in size. - the size of an array is theta(n)

[@vuth89]

Thanks you from Cambodia

[@matthewcao8514]

Why is the time complexity for linked list for insert_last(x) and delete_last(x) linear? Shouldn't it be constant since we are able to access the tail?

[@guitsgarcia5446]

you don't store the tail on regular linked lists. Storing the tail is considered an "augmentation", and does reduce insert_last(x) to linear. delete_last(x) isn't so easy as you would need to fetch the second-to-last and update its pointer to null I think, therefore you would also need to go through the whole linked list. Doubly linked lists might solve this by storing tail on every element (see 32:34).

[@thinkGrey_]

Thanks MIT

[@johnphamlore8073]

Thank you MIT for your generosity. On a side note, is it still true that there is a special thick chalk great for fast writing on boards that Professor Demaine seems to be using that is no longer made and needs to be hoarded?

[@mitocw]

No need to hoard... the chalk is still available. It is known as either jumbo chalk or railroad chalk (used to mark boxcars).

[@playme1354]

If you care to know, I just attended MIT. Thanks to KZbin. 🥳🥳

[@iEuno1]

I learned that in 1992 and that is how I design my database systems .

[@georgejetson9801]

1980 here. :)

[@iEuno1]

@@georgejetson9801 Very good, I was in secondary 1 in 1980, when I learned Technical Drafting skills, which I used for my flowcharting and other diagrams designs in 1992 to this day. I scored 100% on it then.

[@tungvu4339]

I love it

[@pranki2254]

What about the operation cost for inserting_first() for the dynamic arrays (Python lists)?

[@h.kubilay6160]

o(n) because re index it. language does not matter.

[@thealchemist9781]

1.Apa yang ingin kamu lakukan dan bagaimana cara melakukannya

[@ouyaah]

44:45 wow that's nice

[@HikikomoriDev]

I like the colour coding here.

[@musaxebd]

What are the prerequisite for this course. I found the concept very hard to understand. Fyi, i am doing java programming and have basic knowledge of programming.

[@surfingcipher1059]

Sequence and series, descrite structures

[@basicsOfCode]

Publish other lectures too.. Pls

[@UmangPatel]

gifoyle is now a lecturer at mit

[@sbk-po3jf]

thanks to MIT QAQ

[@IIGrudge]

I don't understand why word >= log(n)

[@stevesmith2553]

do a two dim array

[@marcelsantee1809]

Why is len() constant time? Is it computed in an attribute along the build()?

[@muhammadzeeshan303]

Constant time is used to measure the efficiency of the operation len(). It will take a constant amount of time to find the length of any nth item.

[@muhammadzeeshan303]

And no build() is linear time not constant

[@aa-hf7hd]

pretty late but yeah it's an attribute (idk if it's computed in build() though). python's len() will return a variable that gives the size of whatever object len() is called on, and that is an O(1) operation so python has to maintain that size variable as it updates, which is (some) overhead

[@marcelsantee1809]

@@aa-hf7hd I figured out myself in the meantime. But this is explanation is great for future readers, thank you!

[@jodisingh8972]

Great video but why chalk board for a tech institute

[@kubamilcarz]

thank you for doing that for free

[@michelealessandrini3421]

Excuse me, I'm not native English, what's that "recitation" class they sometimes talk about?

[@mitocw]

The purpose of the recitations is to expand upon course materials covered in lecture and allow students to practice working with the material in an interactive setting.

[@AhmedGamal-xi3vj]

@@mitocw Where to find the recitations classes?

[@mitocw]

Here is the playlist for the series: kzbin.info/aero/PLUl4u3cNGP63EdVPNLG3ToM6LaEUuStEY. The ones labeled problem sessions are the recitations. See the course on MIT OpenCourseWare for more info and materials (Lecture notes, recitation notes, problem sets, etc.) at: ocw.mit.edu/6-006S20. Best wishes on your studies!

[@catrinacraft]

They're all in a classroom in Spring 2020? The university must've stayed open!

[@hopetembo6820]

It made so much sense daummm😮

[@goldibollocks]

When you know you’ll be needing lots more memory later in your program: See you later, allocator

[@allandogreat]

Best algorithm in the world

[@user-rv4li7lt5i]

cool!

[@amo3838]

I looked for so many ways to start in programming ans find my self in this course. I love the enthusiasm. I hope to work through this class. Does someone has recommondations for me where I can train myself to become a programmer? Where I can do basic stuff?

[@mitocw]

There are many great resources to learn programming. From our materials, we recommend you start with MIT 6.0001 Introduction to Computer Science and Programming in Python: ocw.mit.edu/6-0001F16. There is an edx version starting January 26: www.edx.org/course/introduction-to-computer-science-and-programming-7

[@amo3838]

@@mitocw I thank you soooo much.

[@alb12345672]

I am programming since a teen in the 80s and there were no online resources back then. You had to be really motivated and push yourself to get books from bookstores and libraries. I have taught programming too. Best advice I can give you is to take an idea and start building it. Every time you hit a problem, research a solution. Yes, you need a certain baseline of knowledge, but don't spend years on that before starting to build something. All the school in the world is useless unless you can create something useful in code.

[@rounakpatra2210]

@@mitocw Is there any difference between 6.0001(YT) and edx Version?

[@tzachs_]

MIT..Please provide course vidoes of Principles of macroeconomics and Intermediate microeconomic theory.

[@dugwtf]

unusually good handwriting for a male teacher

[@alicehuang8898]

what is the book he mentioned to refer to by the end? Can someone tell me the name? Thx

[@mannyknowles]

Not sure but most likely this one: mitpress.mit.edu/books/introduction-algorithms-third-edition

[@tungo7941]

It's called CLRS, which stands for the name of the 4 authors. The exact name of this book is "introduction to algorithms"

[@mannyknowles]

So it is the book in the link I provided. Thanks for confirming.

[@chrislee5044]

40:46 lol, Jason my guy

[@anonymousrashiyama1432]

29:25

[@namanvyas9433]

Cool t-shirt

[@dawkosvk]

Drunk as fuck and watched this whole video....for sure I'll remember something out of this hahahah

[@kostagacinovic]

As it turns out, learning C before this was worth it

[@rajnishkushx]

Insert last in static array? Why O(n)?

[@llll-dj8rn]

because the way you build a static array is by allocating a fixed size of memory, say you allocated 7 blocks of the memory, and suppose your static array will be like that A = [1,2,3,4,5,6,7], now what if you need to add new one element to your existing array? no you can't, because as i've said you've allocated a specific size of the memory (may the eighth block of the old sequence is not available ), so now i have to allocate a new sequence of the memory that can store my new "8 element array".

[@adventurer2395]

The real epiphany comes at 40:00

[@anchalsani805]

I didn't got it

[@wingsonthebus]

I hereby slap my brain for every bad thought it’s ever had about Prof. Demaine. This is peak American: aware, unpretentious, brilliant! also this is uncalled for but screw it the world is ending he has a sweet fashion sense 🤘😤

[@Gato_Gao]

erik :')

[@Mikasks]

16:11 “Download more RAM”

[@Juan-dc6yf]

Why camera guy follow him and not show the board at once smh

[@TomerBenDavid]

3