Bummer! This is just a preview. You need to be signed in with a Basic account to view the entire video.
Defining an Algorithm8:27 with Pasan Premaratne
Earlier we looked at a generic definition of an algorithm. Let's dig deeper in this video and come up with a list of steps we need to fulfill to call our code an algorithm
In the last video, we ran through an exercise where I had some of my coworkers 0:00 guess what number I was thinking. 0:04 So what was the point of that exercise? 0:06 You might be thinking, hey, I thought I was here to learn about algorithms. 0:07 The exercise we just did was an example of a real life situation you'll 0:11 run into when building websites, apps, and writing code. 0:16 Both approaches taken by John and 0:20 Britney to find the number I was thinking of are examples of searching for a value. 0:22 It might be weird to think that there's more than one way to search. 0:28 But as you saw in the game, 0:31 the speed at which the result was obtained differed between John and Britney. 0:32 Think about this problem from the perspective of a company like Facebook. 0:37 At the time of this recording, Facebook has 2.19 billion active users. 0:41 Let's say you're travelling in a different country and 0:46 meet someone you want to add on Facebook. 0:49 You go into the search bar and type out this person's name. 0:51 If we simplify how the Facebook app works, it has to search across these 0:54 2.19 billion records and find the person you are looking for. 0:59 The speed at which you find this person really matters. 1:04 Imagine what kind of experience it would be if, when you search for 1:07 a friend, Facebook put up a spinning activity indicator and 1:11 said come back in a couple of hours. 1:15 I don't think we'd use Facebook as much if that was the case. 1:17 From the company's perspective, working on 1:20 making search as fast as possible using different strategies really matters. 1:23 Now I said that the two strategies Britney and John used were examples of search. 1:28 More specifically, these are search algorithms. 1:33 The strategy John took, where he started at the beginning of the range and 1:36 just counted one number after the other, is a type of search called linear search. 1:41 It is also called sequential search, which is a better description of how it works. 1:46 Or even simple search, since it really is quite simple. 1:51 But what makes his approach an algorithm as opposed to just looking for something? 1:55 Remember, we said that an algorithm is a set of steps or 2:00 instructions to complete a task. 2:03 Linear search is a search algorithm, and we can define it like this. 2:06 We start at the beginning of the list or the range of values. 2:10 Then we compare the current value to the target. 2:14 If the current value is the target value that we're looking for, we're done. 2:17 If it's not, we'll move on sequentially to the next value in the list and 2:21 then repeat step two. 2:26 If we reach the end of the list, then the target value is not in the list. 2:28 This definition has nothing to do with programming, and 2:32 in fact you can use it in the real world. 2:36 For example, I could tell you to walk into a book store and 2:38 find me a particular book. 2:41 And one of the ways you could do it is using the linear search algorithm. 2:43 You could start at the front of the bookstore and read the cover or 2:47 the spine of every book to check that it matches the book that you're looking for. 2:50 If it doesn't, you go to the next book, and repeat until you find it or 2:55 run out of books. 2:59 What makes this an algorithm is the specificity of how it is defined. 3:00 In contrast to just jumping into a problem and solving it as we go along, 3:06 an algorithm follows a certain set of guidelines, 3:10 and we use the same steps to solve the problem each time we face it. 3:14 An important first step to defining the algorithm isn't the algorithm itself, but 3:18 the problem we're trying to solve. 3:22 Our first guideline is that an algorithm must have a clear problem statement. 3:24 It's pretty hard to define an instruction set when you don't have a clear idea of 3:30 what problem you're trying to solve. 3:34 In defining the problem, we need to specify how the input is defined, and 3:36 what the output looks like when the algorithm has done its job. 3:41 For linear search, the input can be generally described as a series of values 3:44 and the output is a value matching the one we're looking for. 3:49 Right now, we're trying to stay away from anything code-related, so 3:53 this problem statement definition is pretty generic. 3:56 But once we get to code, we can actually tighten this up. 3:59 Once we have a problem, an algorithm is a set of steps that solves this problem. 4:02 Given that, the next guideline is that an algorithm definition must 4:07 contain a specific set of instructions in a particular order. 4:12 We really need to be clear about the order in which these instructions are executed. 4:16 Taking our simple definition of linear search, if I switched up the order and 4:21 as I had moved sequentially to the next value before specifying that first 4:26 comparison step. 4:30 If the first value were the target one, our algorithm wouldn't find it because we 4:32 moved to the second value before comparing. 4:36 Now you might think, okay, that's just an avoidable mistake, and 4:38 kind of common sense. 4:42 The thing is, computers don't know any of that and just do exactly as we tell them. 4:43 So a specific order is really important. 4:48 The third guideline is that each step in our algorithm definition must not be 4:51 a complex one and needs to be explicitly clear. 4:55 What I mean by that is that you shouldn't be able to break down any of 4:58 the steps into further into additional subtasks. 5:02 Each step needs to be a distinct one. 5:05 We can't define linear search as search until you find this value because that can 5:08 be interpreted in many ways and further broken down into many more steps. 5:12 It's not clear. 5:17 Next, and this one might seem obvious, but algorithms should produce a result. 5:18 If it didn't, how would we know whether the algorithm works or not? 5:24 To be able to verify that our algorithm works correctly, we need a result. 5:28 Now, when using a search algorithm, the end result can actually be nothing, 5:34 which indicates that the value wasn't found. 5:37 But that's perfectly fine. 5:40 There are several ways to represent nothing in code, and 5:42 as long as the algorithm can produce some results, we can understand its behavior. 5:45 The last guideline is that the algorithm should actually complete and 5:50 cannot take an infinite amount of time. 5:54 If we let John loose in the world's largest library and 5:56 asked him to find a novel, we have no way of knowing whether he succeeded or 6:00 not unless he came back to us with a result. 6:04 Okay, so quick recap, 6:07 what makes an algorithm an algorithm and not just something you do? 6:08 One, it needs to have a clearly defined problem statement, input, and output. 6:13 When using linear search, the input needs to be just a series of values. 6:18 But to actually use Britney's strategy, there's one additional precondition, so 6:22 to speak. 6:27 If you think about her strategy, 6:28 it required that the numbers be sorted in ascending order. 6:30 This means that where the input for John is just a series of values, 6:33 to solve the problem, 6:37 the input to Britney's algorithm needs to be a sorted series of values. 6:38 So clearly defined problem statement, clearly defined input, and 6:42 clearly defined output. 6:47 Second, the steps in the algorithm need to be in a very specific order. 6:49 The steps also need to be distinct, 6:54 you should not be able to break it down into further subtasks. 6:56 Next, the algorithm should produce a result. 7:00 And finally, the algorithm should complete in a finite amount of time. 7:04 These guidelines not only help us define what an algorithm is, but 7:09 also helps us verify that the algorithm is correct. 7:13 Executing the steps in an algorithm for 7:17 a given input must result in the same output every time. 7:20 If, in the game I played, the answer was 50 every time, 7:24 then every single time John must take 50 turns to find out that the answer is 50. 7:28 If somehow he takes 50 turns in one round then 30 the next, 7:34 then we technically don't have a correct algorithm. 7:38 Consistent results for 7:42 the same set of values is how we know that the algorithm is correct. 7:43 I should stress that we're not going to be designing any algorithms on our own, and 7:48 we'll start off and spend most of our time learning the tried and 7:52 true algorithms that are known to efficiently solve problems. 7:56 The reason for talking about what makes for a good algorithm, though, 7:59 is that these same set of guidelines makes for good algorithmic thinking, 8:03 which is one of the most important skills we want to cultivate. 8:07 When we encounter a problem, before rushing in and thinking about solutions, 8:10 what we want to do is work through the guidelines. 8:15 First we break down the problem into any possible number of smaller problems, 8:18 where each problem can be clearly defined in terms of an input and an output. 8:23
You need to sign up for Treehouse in order to download course files.Sign up