Problem Overview and Naive Algorithm

Loading...

University of California San Diego의 강좌에서

Algorithmic Toolbox

4484개의 평가

University of California San Diego

Algorithmic Toolbox

4484개의 평가

Specialization Data Structures and Algorithms에서 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).

수업에서

Algorithmic Warm-up

In this module you will learn that programs based on efficient algorithms can solve the same problem billions of times faster than programs based on naïve algorithms. You will learn how to estimate the running time and memory of an algorithm without even implementing it. Armed with this knowledge, you will be able to compare various algorithms, select the most efficient ones, and finally implement them as our programming challenges!

Problem Overview and Naive Algorithm4:03

Efficient Algorithm5:50

강사 만나기

Alexander S. Kulikov
Visiting Professor
Department of Computer Science and Engineering
Michael Levin
Lecturer
Computer Science
Neil Rhodes
Adjunct Faculty
Computer Science and Engineering
Pavel Pevzner
Professor
Department of Computer Science and Engineering
Daniel M Kane
Assistant Professor
Department of Computer Science and Engineering / Department of Mathematics

Hello everybody.

Welcome back.

Today, we're going to be talking about computing greatest common divisors.

So, in particular, what we'd like to do this lecture,

is we're going to define the greatest common divisor problem.

And, we're going to talk about an inefficient way to compute them.

And, next lecture we'll talk about how to do better.

So, okay.

What are GCDs?

So, suppose that you have a fraction, a over b.

And, you want to put it in simplest form.

Now, the standard way of doing this, is we want to divide the numerator and

denominator both by some d, to get some equivalent fraction, a/d / b/d.

Fair enough.

Now, what d do we want to use for this?

Well, it needs to satisfy two properties.

Firstly, d had better divide both a and b, since the new numerator and

denominator are both integers.

But, subject to that, we would like this d to be as large as possible.

So, that we can reduce the fraction as much as we possibly can.

So, turning this into a definition, we say that for two integers, a and

b, their greatest common divisor, or GCD,

is the largest integer d that divides both a and b.

Okay, so this is a thing that you use to reduce fractions.

However, it turns out that GCDs are a critically important

concept in the field of number theory.

The study of prime numbers, and factorization, and things like that.

And, because it's so important to number theory, it turns out that being able to

compute GCDs is actually very important in cryptography.

And, the fact that you can perform secure online banking is, in part,

due to the fact that we can efficiently compute GCDs of numbers in order for

our cryptographic algorithms to work.

So, because of this importance, we're going to want to be able to compute GCDs.

So, we'd like an algorithm that, given two integers, a and b, at say, at least 0,

we can compute the GCD of a and b.

And, just to be clear as to what kinds of inputs we care about,

we'd actually like to be able to run this on very large numbers.

We don't just want something that works for GCD of 5 and 12, or 11 and 73.

We'd like to be able to do things like the GCD of

3,918,848 with 1,653,264.

In fact, we'd also like to be able to compute much bigger numbers,

20, 50, 100, 1000 digits.

We'd still like to be able to get GCDs of numbers of those sizes pretty quickly.

Well, let's get started.

Let's start by just finding an algorithm that works.

What we'd like is the largest number that divides both a and b.

So, one thing we can do,

is we can just check all of the numbers that are candidates for

this, figure out which ones divide a and b, and return the largest one.

So, there's an easy implementation for this.

We create a variable called best, and set it to 0.

This just remembers the biggest thing we've seen so far.

We then let d run from 1 to a + b,

since this is the range of numbers that are valid.

Now, if d divides a, and d divides b, well, since d is increasing,

this has to be the new best that we've seen.

So, we set best equal to d, and then, at the end the of the day,

we return back the best thing we've seen.

So, that's a perfectly good algorithm.

It works.

Unfortunately, it's a little bit slow,

because we need to run through this for loop a + b many times.

And, this means that, even once a and b are, say, 20 digit numbers, it's already

going to be taking us at least thousands of years in order to run this computation.

And, so that's not sufficient for the sorts of applications that we care about.

We're going to need a better algorithm.

So, come back next lecture, and we'll talk about how to find a better algorithm for

this problem, and what goes into that.

Coursera 카탈로그 살펴보기

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

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

© 2019 Coursera Inc. All rights reserved.

앱스토어에서 다운로드하기

구글 플레이에서 받기