Explore
For Enterprise
Join for Free
Log In

검색
포 엔터프라이즈 (For Enterprise)
로그인
무료 회원 가입

Intro

Loading...

Algorithmic Toolbox

캘리포니아 샌디에고 대학교

4.7(5,375개의 평가) | 170K명의 학생이 등록함

데이터 구조 및 알고리즘 전문 분야에서 6의 강좌 1

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). Do you have technical problems? Write to us: coursera@hse.ru

강의 계획서 보기

배우게 될 기술

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

검토

4.7(5,375개의 평가)

5 stars
4,000 ratings
4 stars
1,093 ratings
3 stars
192 ratings
2 stars
39 ratings
1 star
51 ratings

MB

Mar 06, 2018

Cool course. Thank you! One suggestion about your book (Learning Algorithms Through Programming and Puzzle Solving): could you add some theory which would serve as a brief reminder before problems?

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

수업에서

Divide-and-Conquer

In this module you will learn about a powerful algorithmic technique called Divide and Conquer. Based on this technique, you will see how to search huge databases millions of times faster than using naïve linear search. You will even learn that the standard way to multiply numbers (that you learned in the grade school) is far from the being the fastest! We will then apply the divide-and-conquer technique to design two efficient algorithms (merge sort and quick sort) for sorting huge lists, a problem that finds many applications in practice. Finally, we will show that these two algorithms are optimal, that is, no algorithm can sort faster!

Linear Search7:19

Binary Search7:10

Binary Search Runtime8:20

강사:

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

스크립트

Hi, I'm Neil Rhodes. Welcome to the divide and conquer module. In the last module, you learned about how to use greedy algorithms to solve particular classes of problems. In this module you'll learn about ways of solving problems using divide and conquer algorithms. The term divide and conquer is quite old, and when applied to war, suggests that it's easier to defeat several smaller groups of opponents than trying to defeat one large group. In a similar fashion, divide and conquer algorithms take advantage of breaking a problem down into one or more subproblems that can then be solved independently. Just as not all problems can be solved with a greedy algorithm, not all problems can be solved using divide and conquer. Instead, these are both techniques that are part of a toolbox of strategies to solve problems. As you're designing an algorithm, you'll need to consider whether or not a greedy algorithm might work. If not, would a divide and conquer algorithm work? Let's look at the general structure of a divide and conquer algorithm. Here, we have a problem to be solved represented abstractly as a blue rectangle. We break the problem down into a set of non-overlapping subproblems. Represented here, by colored rectangles. It's important that the subproblems be of the same type as the original. For example, here's a way to break down the original rectangle problem into a set of subproblems that are not of the same type. These subproblems are triangles. Thus this does not represent the divide and conquer algorithm. In this case, we've broken down the original rectangle problem into a set of subproblems that are themselves rectangles. The difficulty is that these subproblems overlap with one another. Thus it too does not represent the divide and conquer algorithm. We return now to breaking down our problem into a set of non-overlapping subproblems of the same original type. We break it apart, then we go ahead and solve each subproblem independently. We solve the first problem, represented by a check mark. We then continue solving each problem, in turn. Once we've successfully solved each of the subproblems, we combine the results into a solution to the original problem. One question that comes up, how do we solve each subproblem? Since each subproblem is of the same type as the original, we can recursively solve the subproblem using the same divide and conquer strategy. Thus, divide and conquer algorithms naturally lead to a recursive solution. In practice, while you can program a divide and conquer algorithm recursively, it's not uncommon to rewrite the recursive program into an iterative one. This is often done both because some programmers aren't as comfortable with recursion as they are with iteration, as well as because of the additional space that a recursive implementation may take in terms of additional stack space. This can be language and implementation dependent. In summary, the divide and conquer algorithm consists of one: breaking the problem into non-overlapping subproblems of the same type. Two: recursively solving those subproblems. And three: combining the results. In the next video, we'll see an extremely simple example of divide and conquer.

Coursera 카탈로그 살펴보기

무료로 참여해 맞춤화된 추천, 업데이트 및 제안을 받아보세요.

Coursera는 세계 최고의 교육에 대한 보편적인 접근 기회를 제공하며, 최고의 대학 및 기관들과 제휴하여 온라인 강좌를 제공합니다.

© 2019 Coursera Inc. All rights reserved.

Coursera
소개
리더십
직업
카탈로그
수료증
MasterTrack™ 수료증
학위
포 엔터프라이즈 (For Enterprise)
정부용
캠퍼스용

커뮤니티
Learners
Partners
Developers
Beta Testers
Translators

연결
블로그
Facebook
Linkedin
Twitter
Instagram
YouTube
기술 블로그

기타
조건
개인정보 보호
도움말
접근성
보도 자료
문의하기
디렉토리
계열사