Algorithms

Loading...

From the course by Johns Hopkins University

Introduction to Genomic Technologies

1480 ratings

Johns Hopkins University

Introduction to Genomic Technologies

1480 ratings

Course 1 of 8 in the Specialization Genomic Data Science

This course introduces you to the basic biology of modern genomics and the experimental tools that we use to measure it. We'll introduce the Central Dogma of Molecular Biology and cover how next-generation sequencing can be used to measure DNA, RNA, and epigenetic patterns. You'll also get an introduction to the key concepts in computing and data science that you'll need to understand how data from next-generation sequencing experiments are generated and analyzed. This is the first course in the Genomic Data Science Specialization.

From the lesson

Computing Technology

The lectures for this module cover a few basic topics in computing technology. We'll go over the foundations of computer science, algorithms, memory and data structures, efficiency, software engineering, and computational biology software.

What Is Computer Science?5:11

Memory and Data Structures6:45

Software Engineering8:07

What is Computational Biology Software11:28

Meet the Instructors

Steven Salzberg, PhD
Professor
Biomedical Engineering, Computer Science, and Biostatistics
Jeff Leek, PhD
Associate Professor, Biostatistics
Bloomberg School of Public Health

This lecture is going to describe what an algorithm is.

So, algorithms are a way of describing what a computer can do,

and we talk about them in the context of computer science and

computational biology all the time, but algorithms don't really need computers.

An algorithm is really just a very clear,

step-by-step series of instructions on how to do something.

So here is an example of an algorithm.

It's a recipe that tells you how to make chocolate brownies.

So you preheat the oven, you melt some chocolate chips and some butter together,

cool it off, stir in some eggs, then stir in the additional ingredients,

spread them out in a pan, and bake them in an oven.

Now presuming you know what all those words mean and

you know what some of the instructions require you to do,

such as preheat the oven, this is a complete set of instructions that lets

you go from a written description to an actual product.

So algorithms don't need computers.

They're just a way of describing in full detail something that we want to get done.

So, now switching to a more computational example one, another kind of algorithm

that we often, that we often deal with is how to find a maximum in some space.

So this is, this is a common a common sort of task in a variety of optimization

problems, in computer science and computational biology and in other fields.

So one way if you were trying to find a, if you, to find a maximum,

imagine you're in a, you're actually walking around in a landscape and

you want to find the highest place in that landscape.

Well, one way you could do that is you could just look around you and

find the direction in which you would be going uphill most rapidly.

In other words, the steepest slope.

And take a step in that direction.

And just keep doing that.

And with that algorithm, if you look at this little example of,

this cartoon example here, that algorithm would take you from

a valley up to the nearest peak, to the top of the nearest peak.

At some point, following that algorithm, you wouldn't be able to proceed.

So remember, the algorithm is look around,

find the area with the steepest upward slope and go that way.

So if you're in an area where everywhere you look it's downward,

you can no longer proceed, so the algorithm would halt at that point.

Now one interesting thing about this algorithm,

there's a whole family of algorithms like this,

is that it's not actually guaranteed to find the highest point in the world.

It'll just find the highest point in your local environment.

But still, it's a useful kind of algorithm and it's a way to think about the problem.

So let me talk about a, a, another, one more algorithm, and, a very,

very common problem we have in computer science is sorting.

There's all kinds of reasons for sorting.

Sometimes we want to put things in alphabetical order,

want to put things in numeric order, or you want to rank things in some other way.

So there's many algorithms for sorting.

Here I'm going to just illustrate one of them.

Let's consider the digits 0 through 9, and suppose they're given to us and

they're not in order, and we want to sort them to put them in order.

They might be, say, attached to something else.

Maybe they're rankings of, of candidates for something and

you want to put them in the right order from, from where 0 will be the minimum.

So one algorithm for doing that says the following.

First, put all the objects in some sort of list data structure

where you can scan through the list from beginning to end.

Now go to the beginning of the list,

compare the first two objects, in this case, 6 and 3.

If they're in the wrong order, simply flip them.

And now move on and see if compare 6 to the next item in the list.

If they're in the right order, okay, we're going to go back to the beginning and now

scan forward until we find two ord, two items that are in the wrong order again.

So we do that.

We get to 8 and 1 and we say oh, wrong order, so we flip those, and

then keep going from there.

We look at 8 and 9.

They're in the right order.

So we'll go back again to the beginning of the list,

scan forward till we get the first pair which is in the wrong order.

There's 6 followed by 1, so we flip those.

We move on and continue this process, always flipping things until we,

till we find obviously the right order.

Moving back to the beginning of the list and

scanning forward until eventually the entire list is sorted.

This algorithm is guaranteed to work.

If you write this down in code, it will always sort your list.

It's not the most efficient algorithm possible, because it actually makes many

passes through the list, and depending on how scrambled the numbers were

in the beginning, it might or might not give you an answer very quickly.

So for, we'll be talking about efficiency in another lecture, but this,

this is a way of introducing idea of efficient algorithms.

So an algorithm is a complete and precise description of how to do something.

But if the amount of data you're dealing with is large,

you also want to think about, how do I do that as fast as possible?

So just because the algorithm completes, and it gives you the correct answer,

doesn't mean it's always the best algorithm to use.

And that bubble sort algorithm, which is what I've just described,

is in fact not the fastest way to sort a list of numbers.

There are better ways to do it.

Explore our Catalog

Join for free and get personalized recommendations, updates and offers.

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

© 2019 Coursera Inc. All rights reserved.

Download on the App Store

Get it on Google Play