full transcript

From the Ted Talk by David J. Malan: What's an algorithm?

Unscramble the Blue Letters


What's an algorithm? In computer science, an aghotlirm is a set of ircntoutsins for siovnlg some problem, step-by-step. Typically, algorithms are executed by ctmruoeps, but we humans have arigomhlts as well. For intcnase, how would you go about counting the number of people in a room? Well, if you're like me, you probably point at each person, one at a time, and count up from 0: 1, 2, 3, 4 and so forth. Well, that's an algorithm. In fact, let's try to express it a bit more formally in pseudocode, English-like syntax that resembles a programming language. Let n eqaul 0. For each person in room, set n = n + 1. How to interpret this pseudocode? Well, line 1 declares, so to speak, a variable called n and initializes its value to zero. This just means that at the beginning of our algorithm, the thing with which we're counting has a value of zero. After all, before we start counting, we haven't counted anything yet. Calling this variable n is just a cvioonnten. I could have cllead it almost anything. Now, line 2 demarks the start of loop, a sequence of steps that will repeat some number of times. So, in our example, the step we're taking is cniutnog people in the room. Beneath line 2 is line 3, which describes exactly how we'll go about counting. The indentation implies that it's line 3 that will repeat. So, what the pudodsceoe is saying is that after starting at zero, for each person in the room, we'll increase n by 1. Now, is this algorithm correct? Well, let's bang on it a bit. Does it work if there are 2 people in the room? Let's see. In line 1, we inltiiziae n to zero. For each of these two pploee, we then increment n by 1. So, in the first trip through the loop, we udatpe n from zero to 1, on the second trip through that same loop, we update n from 1 to 2. And so, by this algorithm's end, n is 2, which indeed matches the number of people in the room. So far, so good. How about a corner case, though? Suppose that there are zero people in the room, besides me, who's doing the counting. In line 1, we again initialize n to zero. This time, though, line 3 doesn't execute at all since there isn't a person in the room, and so, n remains zero, which indeed matches the nmeubr of people in the room. Pretty simple, right? But counting people one a time is pretty iiifencefnt, too, no? sruely, we can do better! Why not count two people at a time? Instead of counting 1, 2, 3, 4, 5, 6, 7, 8, and so forth, why not count 2, 4, 6, 8, and so on? It even sounds faster, and it surely is. Let's express this ompttiiozain in pseudocode. Let n equal zero. For each pair of people in room, set n = n + 2. Pretty simple caghne, right? Rather than conut people one at a time, we instead count them two at a time. This algorithm's thus twice as fast as the last. But is it crocert? Let's see. Does it work if there are 2 people in the room? In line 1, we initialize n to zero. For that one pair of people, we then increment n by 2. And so, by this algorithm's end, n is 2, which indeed mcehats the number of people in the room. Suppose next that there are zero people in the room. In line 1, we initialize n to zero. As before, line 3 doesn't execute at all since there aren't any piras of people in the room, and so, n remains zero, which indeed matches the number of people in the room. But what if there are 3 people in the room? How does this algorithm fair? Let's see. In line 1, we initialize n to zero. For a pair of those people, we then increment n by 2, but then what? There isn't another full pair of people in the room, so line 2 no lonegr applies. And so, by this algorithm's end, n is still 2, which isn't correct. Indeed this algorithm is said to be buggy because it has a mistake. Let's redress with some new pseudocode. Let n equal zero. For each pair of people in room, set n = n + 2. If 1 person remains unpaired, set n = n + 1. To solve this particular problem, we've introduced in line 4 a condition, otherwise known as a branch, that only executes if there is one person we could not pair with another. So now, whether there's 1 or 3 or any odd number of people in the room, this algorithm will now count them. Can we do even better? Well, we could count in 3's or 4's or even 5's and 10's, but beyond that it's going to get a little bit difficult to ponit. At the end of the day, whether executed by computers or humans, algorithms are just a set of instructions with which to solve problems. These were just three. What problem would you solve with an algorithm?

Open Cloze


What's an algorithm? In computer science, an _________ is a set of ____________ for _______ some problem, step-by-step. Typically, algorithms are executed by _________, but we humans have __________ as well. For ________, how would you go about counting the number of people in a room? Well, if you're like me, you probably point at each person, one at a time, and count up from 0: 1, 2, 3, 4 and so forth. Well, that's an algorithm. In fact, let's try to express it a bit more formally in pseudocode, English-like syntax that resembles a programming language. Let n _____ 0. For each person in room, set n = n + 1. How to interpret this pseudocode? Well, line 1 declares, so to speak, a variable called n and initializes its value to zero. This just means that at the beginning of our algorithm, the thing with which we're counting has a value of zero. After all, before we start counting, we haven't counted anything yet. Calling this variable n is just a __________. I could have ______ it almost anything. Now, line 2 demarks the start of loop, a sequence of steps that will repeat some number of times. So, in our example, the step we're taking is ________ people in the room. Beneath line 2 is line 3, which describes exactly how we'll go about counting. The indentation implies that it's line 3 that will repeat. So, what the __________ is saying is that after starting at zero, for each person in the room, we'll increase n by 1. Now, is this algorithm correct? Well, let's bang on it a bit. Does it work if there are 2 people in the room? Let's see. In line 1, we __________ n to zero. For each of these two ______, we then increment n by 1. So, in the first trip through the loop, we ______ n from zero to 1, on the second trip through that same loop, we update n from 1 to 2. And so, by this algorithm's end, n is 2, which indeed matches the number of people in the room. So far, so good. How about a corner case, though? Suppose that there are zero people in the room, besides me, who's doing the counting. In line 1, we again initialize n to zero. This time, though, line 3 doesn't execute at all since there isn't a person in the room, and so, n remains zero, which indeed matches the ______ of people in the room. Pretty simple, right? But counting people one a time is pretty ___________, too, no? ______, we can do better! Why not count two people at a time? Instead of counting 1, 2, 3, 4, 5, 6, 7, 8, and so forth, why not count 2, 4, 6, 8, and so on? It even sounds faster, and it surely is. Let's express this ____________ in pseudocode. Let n equal zero. For each pair of people in room, set n = n + 2. Pretty simple ______, right? Rather than _____ people one at a time, we instead count them two at a time. This algorithm's thus twice as fast as the last. But is it _______? Let's see. Does it work if there are 2 people in the room? In line 1, we initialize n to zero. For that one pair of people, we then increment n by 2. And so, by this algorithm's end, n is 2, which indeed _______ the number of people in the room. Suppose next that there are zero people in the room. In line 1, we initialize n to zero. As before, line 3 doesn't execute at all since there aren't any _____ of people in the room, and so, n remains zero, which indeed matches the number of people in the room. But what if there are 3 people in the room? How does this algorithm fair? Let's see. In line 1, we initialize n to zero. For a pair of those people, we then increment n by 2, but then what? There isn't another full pair of people in the room, so line 2 no ______ applies. And so, by this algorithm's end, n is still 2, which isn't correct. Indeed this algorithm is said to be buggy because it has a mistake. Let's redress with some new pseudocode. Let n equal zero. For each pair of people in room, set n = n + 2. If 1 person remains unpaired, set n = n + 1. To solve this particular problem, we've introduced in line 4 a condition, otherwise known as a branch, that only executes if there is one person we could not pair with another. So now, whether there's 1 or 3 or any odd number of people in the room, this algorithm will now count them. Can we do even better? Well, we could count in 3's or 4's or even 5's and 10's, but beyond that it's going to get a little bit difficult to _____. At the end of the day, whether executed by computers or humans, algorithms are just a set of instructions with which to solve problems. These were just three. What problem would you solve with an algorithm?

Solution


  1. surely
  2. pseudocode
  3. people
  4. update
  5. number
  6. called
  7. correct
  8. longer
  9. initialize
  10. matches
  11. inefficient
  12. instructions
  13. pairs
  14. algorithm
  15. convention
  16. count
  17. solving
  18. change
  19. instance
  20. optimization
  21. point
  22. equal
  23. algorithms
  24. computers
  25. counting

Original Text


What's an algorithm? In computer science, an algorithm is a set of instructions for solving some problem, step-by-step. Typically, algorithms are executed by computers, but we humans have algorithms as well. For instance, how would you go about counting the number of people in a room? Well, if you're like me, you probably point at each person, one at a time, and count up from 0: 1, 2, 3, 4 and so forth. Well, that's an algorithm. In fact, let's try to express it a bit more formally in pseudocode, English-like syntax that resembles a programming language. Let n equal 0. For each person in room, set n = n + 1. How to interpret this pseudocode? Well, line 1 declares, so to speak, a variable called n and initializes its value to zero. This just means that at the beginning of our algorithm, the thing with which we're counting has a value of zero. After all, before we start counting, we haven't counted anything yet. Calling this variable n is just a convention. I could have called it almost anything. Now, line 2 demarks the start of loop, a sequence of steps that will repeat some number of times. So, in our example, the step we're taking is counting people in the room. Beneath line 2 is line 3, which describes exactly how we'll go about counting. The indentation implies that it's line 3 that will repeat. So, what the pseudocode is saying is that after starting at zero, for each person in the room, we'll increase n by 1. Now, is this algorithm correct? Well, let's bang on it a bit. Does it work if there are 2 people in the room? Let's see. In line 1, we initialize n to zero. For each of these two people, we then increment n by 1. So, in the first trip through the loop, we update n from zero to 1, on the second trip through that same loop, we update n from 1 to 2. And so, by this algorithm's end, n is 2, which indeed matches the number of people in the room. So far, so good. How about a corner case, though? Suppose that there are zero people in the room, besides me, who's doing the counting. In line 1, we again initialize n to zero. This time, though, line 3 doesn't execute at all since there isn't a person in the room, and so, n remains zero, which indeed matches the number of people in the room. Pretty simple, right? But counting people one a time is pretty inefficient, too, no? Surely, we can do better! Why not count two people at a time? Instead of counting 1, 2, 3, 4, 5, 6, 7, 8, and so forth, why not count 2, 4, 6, 8, and so on? It even sounds faster, and it surely is. Let's express this optimization in pseudocode. Let n equal zero. For each pair of people in room, set n = n + 2. Pretty simple change, right? Rather than count people one at a time, we instead count them two at a time. This algorithm's thus twice as fast as the last. But is it correct? Let's see. Does it work if there are 2 people in the room? In line 1, we initialize n to zero. For that one pair of people, we then increment n by 2. And so, by this algorithm's end, n is 2, which indeed matches the number of people in the room. Suppose next that there are zero people in the room. In line 1, we initialize n to zero. As before, line 3 doesn't execute at all since there aren't any pairs of people in the room, and so, n remains zero, which indeed matches the number of people in the room. But what if there are 3 people in the room? How does this algorithm fair? Let's see. In line 1, we initialize n to zero. For a pair of those people, we then increment n by 2, but then what? There isn't another full pair of people in the room, so line 2 no longer applies. And so, by this algorithm's end, n is still 2, which isn't correct. Indeed this algorithm is said to be buggy because it has a mistake. Let's redress with some new pseudocode. Let n equal zero. For each pair of people in room, set n = n + 2. If 1 person remains unpaired, set n = n + 1. To solve this particular problem, we've introduced in line 4 a condition, otherwise known as a branch, that only executes if there is one person we could not pair with another. So now, whether there's 1 or 3 or any odd number of people in the room, this algorithm will now count them. Can we do even better? Well, we could count in 3's or 4's or even 5's and 10's, but beyond that it's going to get a little bit difficult to point. At the end of the day, whether executed by computers or humans, algorithms are just a set of instructions with which to solve problems. These were just three. What problem would you solve with an algorithm?

Frequently Occurring Word Combinations


ngrams of length 2

collocation frequency
counting people 2


Important Words


  1. algorithm
  2. algorithms
  3. applies
  4. bang
  5. beginning
  6. beneath
  7. bit
  8. branch
  9. buggy
  10. called
  11. calling
  12. case
  13. change
  14. computer
  15. computers
  16. condition
  17. convention
  18. corner
  19. correct
  20. count
  21. counted
  22. counting
  23. day
  24. declares
  25. demarks
  26. describes
  27. difficult
  28. equal
  29. execute
  30. executed
  31. executes
  32. express
  33. fact
  34. fair
  35. fast
  36. faster
  37. formally
  38. full
  39. good
  40. humans
  41. implies
  42. increase
  43. increment
  44. indentation
  45. inefficient
  46. initialize
  47. initializes
  48. instance
  49. instructions
  50. interpret
  51. introduced
  52. language
  53. line
  54. longer
  55. loop
  56. matches
  57. means
  58. mistake
  59. number
  60. odd
  61. optimization
  62. pair
  63. pairs
  64. people
  65. person
  66. point
  67. pretty
  68. problem
  69. problems
  70. programming
  71. pseudocode
  72. redress
  73. remains
  74. repeat
  75. resembles
  76. room
  77. science
  78. sequence
  79. set
  80. simple
  81. solve
  82. solving
  83. sounds
  84. speak
  85. start
  86. starting
  87. step
  88. steps
  89. suppose
  90. surely
  91. syntax
  92. time
  93. times
  94. trip
  95. typically
  96. unpaired
  97. update
  98. variable
  99. work