Harvard Professor Explains Algorithms in 5 Levels of Difficulty | WIRED

hello world my name is David J Ma and I'm a professor of computer science at Harvard University today I've been asked to explain algorithms in five levels of increasing difficulty algorithms are important because they really are everywhere not only in the physical world but certainly in the virtual world as well and in fact what excites me about algorithms is that they really represent an opportunity to solve problems and I dare say no matter what you do in life all of us have problems to solve so I'm a computer science professor so I spend a lot

of time with computerss how would you define a computer for them well a computer is electronic like a phone but it's um a rectangle and you like can type like tick tick tick and you work on it nice do you know any of the parts that are inside of a computer um no can I explain a couple of them to you yeah so like inside of every computer is some kind of brain and the technical term for that is CPU or Central processing unit and those are the pieces of Hardware that know how to respond

to those instructions like moving up or down or left or right knows how to do math like addition and subtraction and then there's at least one other type of Hardware inside of a computer called memory or Ram if you've heard of this I know memory because you have to memorize stuff yeah exactly and computers have even different types of memory they have what's called Ram random access memory which is where your games where your programs are stored while they being used but then it also has a a hard drive or a solid state drive which

is where your data your high scores your documents once you start writing essays and and stories in the future stays there stays permanently so even if the power goes out the computer can still remember that information it's still there because the computer can't just like delete all the words itself because your fingers can only do that like you have to use your finger to delete all the stuff exactly have you heard of an algorithm before um yes algorithm is a list of instructions to tell people what to do or like a robot what to do

yeah exactly it's so it's just stepbystep instructions for doing something for solving a problem for yeah so like if you have a bedtime routine then first you say I get dressed I brush my teeth I read a little story and then I go to bed all right well how about another algorithm like um what do you tend to eat for for lunch any types of sandwiches you like uh I eat peanut butter and let me get some supplies from the cupboard here so should we make an algorithm together for why don't we do it this

way why don't we pretend like I'm a computer or maybe I'm a robot so I only understand your instructions and so I want you to feed me no pun intended an algorithm so step-by-step instructions for solving this problem but remember algorithms you have to be precise you have to give the right instructions the right instructions just do it for me soep step one was what open the bag okay opening the bag of bread stop now grab the bread and put it on the plate grab the bread and put it on the plate take all the

bread back and put it back in there so that's like an undo command little control Z okay take one bread and put it on the plate take the lid off the peanut butter okay take the lid off the peanut butter put the lid down okay take the knife take the knife put the blade inside the peanut butter and spread the peanut butter on the bread I'm going to take out some peanut butter and I'm going to spread the peanut butter on the bread I put a lot of peanut butter on because I love peanut butter

apparently I thought I was messing with you here but I think you're happy with this Put The Knife down and then grab one bread and put it on top of the second bread sideways sideways like put it flat on oh flat ways okay and now done you're done with your sandwich should we take a delicious bite yep let's take a bite okay here we go what would be the next step be you here clean all this mess up clean all this mess up right we made an algorithm step-by-step instructions for solving some problem and if

you think about now how we made peanut butter and jelly sandwiches sometimes we were imprecise you didn't give me quite enough information to do the algorithm correctly and that's why I took out so much bread Precision being very very correct with your instructions is so important in the real world because for instance when you're using the worldwide web and you're searching for something on Google or being you want to do the right thing so like if you type in just Google then you won't find the answer to your question pretty much everything we do in

life is an algorithm even if we don't use that fancy word to describe it because you and I are sort of following instructions either that we came up with ourselves or maybe our parents told us how to do these things and so those are just algorithms but when you start using algorithms in uh computers that's when you start writing code what do you know about algorithms nothing really um at all honestly I think it's just probably a way to store information um in computers and I dare say even though you might not have put this

word on it odds are you executed as a human multiple algorithms today even before you came here today like what were a few things that you did I got ready okay and get ready what does that mean brushing my teeth brushing my hair okay put getting dressed okay so all of those frankly if we really um Dove more deeply could be broken down into stepbystep instructions and presumably your mom your dad someone in the past sort of programmed you as a human to know what to do and then after that as a smart human you

can sort of take it from there and you don't need their help anymore but that's kind of what we're doing when we program computer something maybe even more familiar nowadays like odds are you have a cell phone your contacts or your dress book but let me ask you why that is like why does Apple or Google or anyone else bother alphabetizing your contacts I just assumed it would be easier to navigate what if your friend happened to be at the very bottom of this randomly organized list like why is that a problem like he or

she is still there I guess it would take a while to get to while you're scrolling that in of itself is kind of a problem or it's an inefficient solution to the problem so it turns out that back in my day before there were cell phones like everyone's numbers from high schools like were literally printed in a book and everyone in my town and my city my state was printed in an actual phone book even if you've never seen this technology before how would you propose verbally to find John in this phone book or I

would just flip through and just look for the J I guess yeah so let me propose that we start that way I could just start at the beginning and step by step I could just look at each page looking for John looking for John now even if you've never seen this here technology before it turns out this is exactly what your phone could be doing in software like someone from Google or Apple or the like they could write software that uses a technique in programming known as a loop and a loop as the word implies

is just sort of do something again and again what if instead of starting from the beginning and going one page at a time what if I or what if your phone goes like two pages or two names at a time would this be correct do you think well you could skip over John I think in what sense if he's in one of the middle pages that you skipped over yeah so sort of accidentally and frankly with like 50/50 probability John could get sandwiched in between two pages but does that mean I have to throw that

algorithm out alt together maybe you could use that strategy until you get close to the section and then switch to going one by one okay that's nice so you could kind of like go twice as fast but then kind of pump the brakes as you near your exit on the highway or in this case near the J section of the book exactly and maybe alternatively if I get to like a b c d e f g h i j k if I get to the K section then I could just double back like one page

just to make sure John didn't get sandwiched between those pages so the nice thing about that second algorithm is that I'm flying through the phone book like two pages at a time so 2 4 6 8 10 12 it's not perfect it's not necessarily correct but it is if I just take like one extra step so I think it's fixable but what your phone is probably doing and frankly what I and like my parents and grandparents used to do back in the day is we'd probably go roughly to the middle of the phone book here

and just intuitively if this is an alphabetized phone book in English what section am I probably going to find myself in roughly K okay so I'm in the K section is John going to be to the left or to the right to the left yeah so John is going to be to the left to the right and what we can do here though your phone does something smarter is tear the problem in half throw half of the problem away being left with just 500 pages now but what might I next do I could sort of

naively just start at the beginning again but we've learned to do better I can go roughly to the middle here do it again yeah exactly so now maybe I'm in the E section which is a little to the left so John is clearly going to be to the right so I can again tear the problem portly in half throw this half of the problem away and I claim now that if we started with a th000 Pages now we've gone to 500 250 now we're really moving quick not on that page and I can call him

roughly how many steps might this third algorithm take if I started with a th000 Pages then went to 500 250 125 like how many times can you divide 1,000 and half maybe 10 that's roughly 10 because in the first algorithm looking again for someone like Zoe in the worst case might have to go all the way through thousand pages but the second algorithm you said was 500 maybe 500 in1 essentially the same thing so twice as fast but this third and final algorithm is sort of fundamentally faster because you're you're sort of dividing and conquering

it in half and half and half not just taking one or two bites out of it at of a time so this of course is not how we used to use phone books back in the day since otherwise they'd be single use only but it is how your phone is actually searching for zoy for John for anyone else but it's doing it in software oh that's cool so here we've happened to focus on searching algorithms looking for John in the phone book but the technique we just used can indeed be called divide and conquer where

you take a big problem and you divide and conquer that is you try to chop it up into smaller smaller smaller pieces a more sophisticated type of algorithm at least depending on how you implement it something known as a recursive algorithm recursive algorithm is essentially an algorithm that uses itself to solve the exact same problem again and again but chops it smaller and smaller and smaller [Music] ultimately hi my name is Patricia Patricia nice to meet you where are you a student at I'm starting my senior year now at NYU oh nice and what have

you been studying the past few years I study computer science and data science if you were chatting with a non-cs nonata science friend of yours like how would you explain to them what an algorithm is some kind of like systematic way of like solving a problem or like a set of like steps to kind of solve a certain like problem you have so you probably recall learning topics like binary search versus linear search and the like so I've come here uh complete with a actual chalkboard with some magnetic numbers on it here like how would

you tell a friend to sort these I think one of the first things we learned was something called bubble sort it was kind of like focusing on like smaller like bubbles I guess I would say it like of the problem like looking at like smaller segments rather than like the whole thing at once what is I think very true about what you're hinting at is that bubble sort really focuses on like local small problems rather than taking a step back trying to fix the whole thing let's just fix the obvious problem in front of us

so for instance when we're trying to get from smallest to largest and the first two things we see are eight followed by one this looks like a problem cuz it's out of order so what would be the simplest fix the least amount of work we can do to at least fix one problem just like switch those two numbers cuz one is obviously smaller than eight perfect so we just swap those two then you would switch those again yeah so that further improves the situation and you can kind of see it that the one and the

two are now in place how about 8 and six switch it again switch those again 8 and three switch it again and conversely now the one and the two are closer to and coincidentally are exactly where we want them to be so are we done no okay so obviously not but what could we do now to further improve the situation go through it again but like you don't need to check the last one anymore because we know like that number is bubbled up to the top Yeah because it has indeed bubbled all the way to

the top so one and two yeah keep it as is okay two and six keep it as is okay six and three then you switch it okay we switch or swap those six and four swap it again okay so four and uh six and seven uh keep it okay seven and five swap it okay and then I think per your point we're pretty darn close let's go through once more one and two Keep It 2 three keep it 3 four keep it 4 six keep it 6 five and then switch it all right we'll switch

this and now to your point we don't need to bother with the ones that already bubbled their way up now we're 100% sure it's sorted yeah and certainly the search engines of the world Google and Bing and so forth they probably don't keep web pages in sorted order because that would be a crazy long list when you're just trying to search the data but there's probably some algorithm underlying what they do and they probably similarly just like we do a bit of work upfront to get things organized even if it's not strictly sorted in the

same way so that people like you and me and others can find that same information so how about social media can you Invision where the algorithms are in that world like maybe for example like Tik Tok like the for you page it's kind of like cuz those are like Rec like recommendations right it's like sort of like Netflix recommendations except more constant because it's just like every video you scroll it's like that's a new recommendation basically and it's like based on like what you've liked previously what you've like saved previously what you search up so

I would assume there's some kind of algorithm there kind of figuring out like what to put on your foru page absolutely just trying to keep you presumably more engaged so the better the algorithm is the better your engagement is maybe the more money the company then makes on the platform and so forth so it all sort of feeds together together but what you're describing really is more artificially intelligent if I may because presumably there's not someone at Tik Tok or any of these social media companies saying if Patricia likes this post then show her this

post if she likes this post then show her this other post because the code would sort of grow infinitely long and there's just way too much content for a programmer to be having those kinds of conditionals those those decisions being made behind the scenes so it's probably a little more artificially intelligent and in that sense You have topics like neuron networks and uh machine learning which really describe taking as input things like what you watch what you click on what your friends watch what they click on and sort of trying to infer from that instead

what should we show Patricia or her friends next okay yeah yeah that makes like the distinction more makes more sense now yeah I am currently a fourth year PhD student at NYU I do robot learning so that's half and half Robotics and Mission learning sounds like you've dabbled with quite a few algorith so how does one actually research algorithms or invent algorithms the most important was just trying to think about inefficiencies and also think about Connecting Threads the way I think about it is that algorithm for me is not just about the way of doing

something but it's about doing something efficiently learning algorithms are practically everywhere now CU Google I would say for example is learning every day about like oh what what articles with links might be better than others and reranking them um there are recommender systems all around us right like content feeds and social media or you know like YouTube or Netflix what we see is in a large part determined by this kind of learning algorithms nowadays there's a lot of concerns around some applications of machine learning and like deep fakes where it can kind of learn how

I talk and learn how you talk and even how we look and generate videos of us we're doing this for real but you could imagine a computer synthesizing this conversation eventually but how does it even know what I sound like and what I look like and how to replicate that all of this learning algorithms that we talk about right uh a lot like what goes in there is just lots and lots of data so data goes in something else comes out what comes out is whatever objective function that you optimize for like where is the

line between algorithms that like play games with and without AI I think when I started off my undergrad the current AI machine learning was not very much synonymous okay and even in my undergraduate in the AI class they learned a lot of classical gorithms for game plays like for example the AAR search right that's a very simple example of how you can play a game without having anything learned this is very much oh you are at a game State you just search down see what are the possibilities and then you pick the best possibility that

it can see versus what you think about when you think about I gameplay like the alpha zero for example or Alpha star or there are a lot of you know like fancy new machine learning agents that are you know even like learning very difficult games like go and those are learned agents as in they are getting better as they play more and more games and as they get more games they kind of refine their strategy based on the data that they seen and once again this high level abstraction is still the same you see a

lot of data and you learn from that right but the question is what is objective function that you're optimizing for is it winning this game is it forcing a tie or is it you know like opening a door in a kitchen so if the world is very much focused on supervised unsupervised reinforcement learning now like what comes next 5 10 years where's the world going I think that this is just U going to be more and more I don't want to use the word encroachment but that's what it feels like of algorithms into our everyday

life like even when I was taking the train here right the trains are being routed with algorithms but this has existed for you know like 50 years probably but as I was coming here as I was checking my phone those are different algorithms and you know they're they're kind of getting all around us getting they're with us all the time they're making our life better most places most cases and I think that's just going to be continuation of all of those and it feels like they're even in places you wouldn't expect and there's just so

much data about you and me and everyone else online and this data is being mind and analyzed and influencing things we see and here it would seem so there is sort of a Counterpoint which might be good for the marketers but not necessarily good for you and me as individuals you know like we're human beings but for someone we might be just a pair of eyes who are you know carrying a wallet and are there to buy things but there is so much more potential for this algorithms to just make our life better without you

know like changing much about our life I'm Chris Wiggins from associate professor of Applied Mathematics at Columbia I'm also the chief data scientist of the New York Times the data science team at the New York Times develops and deploys machine learning for Newsroom and business problems but I would say the things that we do mostly you don't see but it might be things like personalization algorithm are recommending different content and do data scientists which is rather distinct from the phrase computer scientist do data scientists still think in terms of algorithms as driving a lot of

it oh absolutely yeah in fact so in data science and Academia often the role of the algorithm is the optimization algorithm that helps you find the best model or the best description of a data set okay in data science and industry the goal often it's centered around an algorithm which becomes a data product right so a data scientist in Industry might be developing and deploying the algorithm which means not only understanding the algorithm and its statistical performance but also all of the software engineering around systems integration making sure that that algorithm receives input that's reliable

and has output that's useful as well as I would say the organizational integration which is how does a community of people like the set of people working at the New York Times integrate that algorithm into their process interesting and I feel like AI based startups are all their R and certainly within Academia are there connections between Ai and the world of data science absolutely the algorithms that there in can you connect those dots for you're right that AI as a field has really exploded I would say particularly many people experienced a chatbot that was really

really good today when people say I AI they're often thinking about large language models or they're thinking about generative AI or they might be thinking about a chatbot one thing to keep in mind is a chatbot is a special case of generative AI which is a special case of using large language models which is a special case of using machine learning generally which is what most people mean by AI you may have moments that are um what John kthy called look M No Hands results where you do some fantastic trick and you're not quite sure

how it worked I think it's still very much early days large language models is still in the point of what might be called alchemy that people are building large language models without a real clear a priori sense of what the right design is for a right problem many people are trying different things out often in large companies where they can afford to have many people trying things out seeing what works publishing that instantiating it as a product and that itself is part of the scientific process I would think too yeah very much well science and

engineering because often you're building a thing and the thing does something amazing to large extent we are still looking for basic theoretical results around why deep neural networks generally work why are they able to learn so well they're huge billions of parameter models and it's difficult for us to interpret how they are able to do what they do and is this a good thing do you think or an inevitable thing that we the programmers we the computer scientist the data science who are inventing these things can't actually explain how they work because I feel like

friends of mine industry even when it's something simple and relatively familiar like autocomplete they can't actually tell me like why that name is appearing at the top of the list whereas years ago when these algorithms were more deterministic and more procedural you could even point to the line that made that name bubble up to the top so is this a good thing a bad thing that we're sort of losing control perhaps in some sense of the algorithm it has risks I don't know that I would say that it's good or bad but I would say

there's lots of scientific precedent there are times when an algorithm works really well and we have finite understanding of why it works or a model works really well and sometimes we have very little understanding of why it works the way it does in classes I teach certainly spend a lot of time on fundamentals algorithms that have been taught in classes for decades now whether it's binary search linear search bubble swort selection sort or the like but are if we're already at the point where I can pull up chat GPT copy paste a whole bunch of

numbers or words and say sort these for me does it really matter how chat GPT is sorting it does it really matter to me as the user how the software is sorting it like do the fundamentals become more dated and less important do you think now you're talking about the ways in which code and computation is a special case of Technology right so for driving a car you may not necessarily need to know much about organic chemistry even if if the organic chemistry is how the car works right so you can drive the car and

use it in different ways without understanding much about the fundamentals so similarly with computation we're at a point where the computation is so high level right as you you know you can import pyit learn and you can go from zero to machine learning and 30 seconds it's depending on what level you want to understand the technology where in the stack so to speak um it's possible to understand it and make wonderful things and Advance the world without understanding it at the particular level of somebody who actually might have originally designed the actual optimization algorithm I

should say though for many of the optimization algorithms there are cases where an algorithm works really well and we publish a paper and there's a proof in the paper and then years later people realize actually that prove was wrong and we're really still not sure why that optimization works but it works really well or it inspires people to make new optimization algorithms so I I do think that the the goal of understanding algorithms is Loosely coupled to our progress in advancing grade algorithms but they don't always necessarily have to require each other and for those

students especially or even adults who are thinking of now steering into computer science into programming who were really jazzed about heading in that direction up until for instance November of 2022 when all of a sudden for many people it looked like the world was now changing and now maybe this isn't such a promising path this isn't such a lucrative path anymore are llms are tools like chat GPT reason not to perhaps steer into the field large language models are a particular architecture for predicting let's say the next word or a set of tokens more generally

the algorithm comes in when you think about how is that llm to be trained or also how to be fine-tuned so the P of GPT is a pre-trained algorithm the idea is that you train a large language model on some Corpus of text could be encyclopedias or textbooks or what have you and then you might want to fine-tune that model around some particular task or some particular subset of texts so both of those are examples of training algorithms so I would say people's perception of artificial intelligence has really changed a lot in the last 6

months particularly around November of 2022 when people experienced a really good chatbot the technology though had been around already before academics had already been working with chat gpt3 before that and GPT 2 and gpt1 and and for many people it sort of opened up this conversation about what is artificial intelligence and what could we do with this and what are the possible good and bad right like any other piece of technology cransberg first law of technology technology is neither good nor bad nor is it neutral every time we have some new technology we should think

about its capabilities and the good and the possible bad as with any area of study algorithms offer a spectrum from the most basic to the most advanced and even if right now the most advanced of the those algorithms feels Out Of Reach because you just don't have that background with each lesson you learn with each algorithm you study that endgame becomes closer and closer such that it will before long be accessible to you and you will be at the end of that most advanced [Music] Spectrum