Explore
For Enterprise
Join for Free
Log In

艺术与人文
商务
计算机科学
数据科学
信息技术
健康
数学和逻辑
个人发展
物理科学与工程
社会科学
语言学习
学位
证书

浏览 Coursera 的全部课程

浏览
搜索
企业版
登录
免费加入

Analysis and Implementation of the Efficient Algorithm

Loading...

Algorithmic Toolbox

加州大学圣地亚哥分校

4.7（4,765 个评分） | 150K 名学生已注册

课程 1（共 6 门，数据结构与算法专项课程）

The course covers basic algorithmic techniques and ideas for computational problems arising frequently in practical applications: sorting and searching, divide and conquer, greedy algorithms, dynamic programming. We will learn a lot of theory: how to sort data and how it helps for searching; how to break a large problem into pieces and solve them recursively; when it makes sense to proceed greedily; how dynamic programming is used in genomic studies. You will practice solving computational problems, designing new algorithms, and implementing solutions efficiently (so that they run in less than a second).

查看授课大纲

您将学习的技能

Dynamic Programming, Debugging, Software Testing, Algorithms, Computer Programming

审阅

4.7（4,765 个评分）

5 stars
3,562 ratings
4 stars
958 ratings
3 stars
169 ratings
2 stars
35 ratings
1 star
41 ratings

PR

Feb 10, 2019

The course is perfectly designed. The perfect start for those who start with data structures and algorithms. The Dynamic programming was a little bit tough but overall course is perfectly designed

AG

Feb 19, 2018

best course for clearing basics of algorithms as well as learning by doing and blow your mind by thinking hard from different prospectives to get desired solutions of programming assignments ...

从本节课中

Greedy Algorithms

In this module you will learn about seemingly naïve yet powerful class of algorithms called greedy algorithms. After you will learn the key idea behind the greedy algorithms, you may feel that they represent the algorithmic Swiss army knife that can be applied to solve nearly all programming challenges in this course. But be warned: with a few exceptions that we will cover, this intuitive idea rarely works in practice! For this reason, it is important to prove that a greedy algorithm always produces an optimal solution before using this algorithm. In the end of this module, we will test your intuition and taste for greedy algorithms by offering several programming challenges.

Celebration Party Problem6:57

Efficient Algorithm for Grouping Children5:26

Analysis and Implementation of the Efficient Algorithm5:25

教学方

Alexander S. Kulikov
Visiting Professor
Michael Levin
Lecturer
Neil Rhodes
Adjunct Faculty
Pavel Pevzner
Professor
Daniel M Kane
Assistant Professor

脚本

Now let us consider the pseudocode that implements this algorithm.

For the sake of simplicity we assume that the points in the input are given in

sorted order from smallest to largest.

We'll start with an empty set of segments denoted by R and

we start with index i pointing at the first point

which is the leftmost because the points are sorted.

Now we go through the points, and we find the leftmost point.

Currently i is pointing to the leftmost point in the set.

And at the start of the while loop i will

always point to the leftmost point which is still in the set.

Now we cover it with the segment from l to r which has unit length,

and the left end in the point xi, so this is a segment from xi to xi+1.

We add this segment to the solution set, and

then we need to remove all the points from the set which already covered.

Instead of removing the points, we will just move the pointer to the right and

forget about the points, which are to the left from the pointer.

So the next while loop, does exactly that.

We know that for any i that is larger than the current i, xi

is to the right from the left end of the segment, because the points are sorted.

So if xi is also to the left from R, then it is covered by the segment.

So we just go to the right, and to the right with pointer i.

And while xi is less than or equal to r, we know that the point is covered.

And as soon as we find some xi which is bigger than r, it means that this point is

not covered and all the points further in the array are also not covered.

So we stop.

And then we repeat again the iteration of the outer while loop.

Or maybe our pointer i is already out of the array of the input points.

And then we stop and

return R, which is the set of segments that we've built in the process.

Now let's prove that this algorithm works in linear time.

Indeed, index i changes just from 1 to n.

And we always increase it by one.

For each value of i, we add at most one segment to the solution.

So overall, we increase i at most n times and

add at most n segments to the solution.

And this leads to a solution which works in Big-O of n time.

Now, we had an assumption that the points in the input are already sorted.

What if we drop this assumption?

Then we will have to sort the points first, and

then apply our algorithm PointsCoverSorted.

Later in this module, you will learn how to sort points in time n log n.

Combining that with our procedure PointsCoverSorted will give you

total running time of n log n.

Now let's look at our improvement.

We first implemented a straightforward solution,

which worked in time at least 2 to the power of n.

And it worked very, very slowly.

So that even for 50 children,

we would have to spend at least 2 weeks of computation to group them.

Our new algorithm, however, works in n log n time.

And that means that even if we had 10 million children coming to a party,

it would spend only a few seconds grouping them optimally into several groups.

So that's a huge improvement.

Now let's see how we went to this end.

First, we've invented a naive solution which worked in exponential time.

It was too slow for us so we wanted to improve it.

But to improve it,

the very first important step was to reformulate it in mathematical terms.

And then we had an idea to solve it with a greedy algorithm.

So, we had to find some greedy choice and prove that it will be a safe move.

In this case, the safe move turns out to be to add to the solution

a segment with left and in the leftmost point.

And then we prove that this is really a safe move.

It is very important to prove your solutions before even trying to

implement them.

Because otherwise, it could turn out that you implemented the solution, tried to

submit it, got wrong answer or some other result, different from accepted.

And then, you've made a few more changes, but it still didn't work.

And then, you understand that your solution was wrong,

completely from the start.

And then you need a new solution, and you will have to implement it from scratch.

And that means that you've wasted all the time on implementation on the first

wrong solution.

To avoid that, you should always prove your solution first.

So after we've proved the safe move, we basically got our greedy solution.

Which works in combination with a certain algorithm in time n log n.

Which is not only polynomial, but is very close to linear time, and

works really fast in practice.

探索我们的目录

免费加入并获得个性化推荐、更新和优惠。

Coursera 致力于普及全世界最好的教育，它与全球一流大学和机构合作提供在线课程。

© 2019 Coursera Inc. 保留所有权利。

通过 App Store 下载

通过 Google Play 获取

Coursera
关于
管理团队
工作机会
目录
证书
MasterTrack™ 证书
学位
企业版
政府版

社区
Learners
Partners
Developers
Beta Testers
Translators

连接
博客
Facebook
领英
Twitter
Instagram
YouTube
技术博客

更多
条款
隐私
帮助
内容访问
媒体
联系我们
目录
附属公司