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

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

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

2 жыл бұрын

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

@michelealessandrini3421

2 жыл бұрын

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

@unorandom3009

2 жыл бұрын

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

@OscarMartinez-nt6zn

2 жыл бұрын

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

@primaryesthethicinstincts4832

10 ай бұрын

You've been learning algorithms for 10 yrs??

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

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.

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

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

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

2 жыл бұрын

sameee!!!

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

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

@FlexGC

2 жыл бұрын

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

@noelcovarrubias7490

2 жыл бұрын

@@FlexGC no way? O:

@MufaddalHakim

2 жыл бұрын

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

@nadiatalaat3561

Жыл бұрын

@@FlexGC which programming language he explain with ?

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.

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

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

@ayushbhardwaj2708

4 ай бұрын

kzread.info/head/PLBF3763AF2E1C572F&si=idwQNxg_A75C6hdz Even IITs have a combined open courseware.

Thank you so much for not enabling ads in this videos

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

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.

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

Thanks MIT for this open Course, amazing!

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.

I really love Erik's style, so charmmmming

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

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

He is very energetic. I have now great teachers!

Great lecture. Thanks!

his series on dynamic programming were great

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

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

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

2 жыл бұрын

Lies again? Meds DarkX

I find 39:30 amusing in that im imagining the blackboard area as the array being talked about. The blackbored is of static size however, so to store new elements old elements have to be overwritten. Yet, many of the points being made do still apply.

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

I am fan of this genius guy ,Eric 🙏🙏

Thanks for providing such awesome opportunity for learning

thank you very much sir for wonderful teaching

Thank you. I love this course.

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

@andiuptown1711

5 ай бұрын

Update? 👀

@user-xl6hx8lb7g

3 ай бұрын

update please...

@andiuptown1711

3 ай бұрын

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

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

this is actually fun to watch

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).

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

The GOAT is back!

Brilliant lecture 👍🏻

My man is back.

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.)

@igor-sukharev

2 жыл бұрын

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

@igor-sukharev

2 жыл бұрын

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.

@igor-sukharev

2 жыл бұрын

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.

@igor-sukharev

2 жыл бұрын

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).

@igor-sukharev

2 жыл бұрын

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.

Amazing, great lecture

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

Great content!

Where I will get full video of this guys

array start with - zero , one etc

Erik Da Man!

Awesome content!

Great intro to computational complexity

Finally I'm a student at MIT😊

Erik in the house !!!

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

2 жыл бұрын

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

2 жыл бұрын

this will help: kzread.info/dash/bejne/ZIhho8GAdtjVhNI.html . Here is the whole list for the course: kzread.info/head/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

2 жыл бұрын

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.

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

2 жыл бұрын

Even I have the same question!

@OscarMartinez-nt6zn

2 жыл бұрын

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.

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

@h.kubilay6160

2 жыл бұрын

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

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

@georgejetson9801

2 жыл бұрын

1980 here. :)

@iEuno1

2 жыл бұрын

@@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.

Thanks MIT

Publish other lectures too.. Pls

nice course

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

10 ай бұрын

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).

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

1.Apa yang ingin kamu lakukan dan bagaimana cara melakukannya

unusually good handwriting for a male teacher

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

Thanks you from Cambodia

Great video but why chalk board for a tech institute

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

do a two dim array

gifoyle is now a lecturer at mit

It made so much sense daummm😮

thank you for doing that for free

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

8 ай бұрын

Sequence and series, descrite structures

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).

🎯 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

44:45 wow that's nice

thanks to MIT QAQ

I love it

I like the colour coding here.

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

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

@muhammadzeeshan303

2 жыл бұрын

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

2 жыл бұрын

And no build() is linear time not constant

@aa-hf7hd

2 жыл бұрын

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

2 жыл бұрын

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

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

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

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

@mannyknowles

2 жыл бұрын

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

@tungo7941

2 жыл бұрын

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

@mannyknowles

2 жыл бұрын

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

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

2 жыл бұрын

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

2 жыл бұрын

@@mitocw I thank you soooo much.

@alb12345672

2 жыл бұрын

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

2 жыл бұрын

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

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

@mitocw

2 жыл бұрын

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

2 жыл бұрын

@@mitocw Where to find the recitations classes?

@mitocw

2 жыл бұрын

Here is the playlist for the series: kzread.info/head/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!

Best algorithm in the world

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

40:46 lol, Jason my guy

I didn't got it

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

@llll-dj8rn

9 ай бұрын

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".

cool!

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

The real epiphany comes at 40:00

29:25

16:11 “Download more RAM”

Cool t-shirt

Post malone teaching DS and Algo, hell yeah!!

erik :')

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