Not all programs are created equal. Â In this course, we'll focus on writing quality code that runs correctly and efficiently. Â We'll design, code and validate our programs and learn how to compare programs that are addressing the same task.

Loading...

From the course by University of Toronto

Learn to Program: Crafting Quality Code

276 ratings

Not all programs are created equal. Â In this course, we'll focus on writing quality code that runs correctly and efficiently. Â We'll design, code and validate our programs and learn how to compare programs that are addressing the same task.

From the lesson

Week 3

- Jennifer CampbellAssociate Professor, Teaching Stream

Department of Computer Science - Paul GriesAssociate Professor, Teaching Stream

Department of Computer Science

Using the tools we've seen so far. Our computer programs can only do one

Â thing at a time. We've used methods that seem to do more

Â than one thing at a time, though. For example, list.sort sorts a list of

Â numbers, and list.index finds the index of a value in the list.

Â We're going to now explore these searching and sorting algorithms.

Â It turns out that they're really interesting, and there are a ton of

Â versions both sorting and searching. We're going to start now by taking a look

Â at linear search where we examine items one by one in a list.

Â One, we call helpline method index in class list.

Â We see that it returns the first index of the value that we're searching for.

Â For example, if we have an L refer to the list with a, b, c, a, and d as strings.

Â And we ask for the index of the a, we get back zero.

Â We don't get back 3 because it returns the index of the first occurrence of the

Â value in the list. When we ask what the index of the string

Â c is, it tells us 2. And when we ask for the index of string

Â d, it tells us 4. Here's how method index works.

Â When it's looking for d, it first looks at index 0, then 1, then 2, then 3.

Â And then in index 4, and it finds what we're looking for and it returns that

Â index. Linear means arranged in a line.

Â And we're essentially looking along the line from the start to the end in the

Â list. Here's how we're going to draw lists for

Â the rest of this week. We're going to place the values inside

Â the list instead of drawing an arrow to the value outside the list.

Â This is to save clutter, to make our drawings a little bit more clean.

Â We'll also draw our index variables above the indices to which they refer.

Â Here, i refers to zero. If we're looking for, say value v, which

Â refers to a, d, then what we'll do is we'll say, hey, is that value at L at

Â index i? And if it is, then we're happy we

Â returned i. If it isn't as in the case we have here,

Â what we do is we will add 1 to i, making i prefer to 1 now.

Â Is the d index an i now? No, it isn't.

Â So, we'll 1 to i. How about now?

Â No. Okay, L at index i equal to d?

Â No, okay. How about now?

Â yes we've done it. L at index i is d.

Â And, so we have found the value we're looking for.

Â So, we will return i in our linear search function.

Â We'll need to decide what to do if the value we're looking for is not in the

Â list. For example, what if it refers to the

Â string? In that case, let's return at least one.

Â We're going to continue to explore linear search by writing a function that

Â implements it. This function picks a list and any

Â object, and returns the integer into the index of that object in the list.

Â Here's an example called where we search for 2, where 2 appears at index 0.

Â Here's another where we search for 5, which is at index 2.

Â And now, we'll search for a number that isn't in the list.

Â We should get back minus 1. And our description is return the index

Â of the first occurrence of v in L, or return minus 1 if v is not in L.

Â Now, we'll draw our list again in order to help us reason about this algorithm.

Â i starts off at zero. Here's the code for that.

Â We don't know yet when we're going to stop, so we'll leave the condition blank.

Â But we do know that we add 1 to i each time through the loop.

Â After a couple of iterations, we have this general picture, i is some index.

Â We know that v is not here. Now, let's look at what this looks like

Â after this loop is over. [SOUND] What if v was not anywhere in

Â this entire list? What value does i have?

Â Well, i is to the right of this dividing line that I've, I've drawn.

Â And in this situation, where the value is not anywhere in the list, i is going to

Â end up equal to the length of l. So, one way to stop this loop is for i to

Â reach the length of L. We therefore can continue as long as i is

Â not equal to the length of L. The other situation in which we can stop

Â is when L find v at index i. That means that as long as i is not the

Â length of L, and v is not equal to L at index i, I add 1 to i.

Â After the loop terminates, I can check to see if i is equal to the length of L, to

Â know whether v was not in the list. If it wasn't, I'll return minus 1.

Â Otherwise, that means that I found v and I can return i.

Â Our algorithms that we're dealing with are starting to get more complicated.

Â Drawing pictures like this can really help develop correct code the first time

Â we write it, which in the long run will save us a ton of time.

Â We can actually get our initialization, i gets 0, straight from this picture right

Â here. If I have my list and I need the v not

Â section here to be empty, that puts the line right there, and that puts i right

Â at index zero. This picture is called a loop invariant.

Â An invariant is something that doesn't change and this picture describes what's

Â happening inside the loop after any number of iterations.

Â Before index i, we did not see a v. We have not yet examined anything from

Â index i onward, and so we still need to search it.

Â Looping variants and pictures like these are going to play a big part in the rest

Â of the lectures this week.

Â Coursera provides universal access to the worldâ€™s best education,
partnering with top universities and organizations to offer courses online.