Why Study Algorithms?

Loading...

Del curso dictado por Stanford University

Divide and Conquer, Sorting and Searching, and Randomized Algorithms

1845 calificaciones

Stanford University

Divide and Conquer, Sorting and Searching, and Randomized Algorithms

1845 calificaciones

Curso 1 de 4 en SpecializationAlgorithms

The primary topics in this part of the specialization are: asymptotic ("Big-oh") notation, sorting and searching, divide and conquer (master method, integer and matrix multiplication, closest pair), and randomized algorithms (QuickSort, contraction algorithm for min cuts).

De la lección

Week 1

Introduction; "big-oh" notation and asymptotic analysis.

Why Study Algorithms?4:15

Integer Multiplication8:38

Karatsuba Multiplication12:39

About the Course17:19

Merge Sort: Motivation and Example8:44

Merge Sort: Pseudocode12:51

Merge Sort: Analysis9:02

Guiding Principles for Analysis of Algorithms15:17

Conoce a los instructores

Tim Roughgarden
Professor
Computer Science

Hi, my name's Tim Roughgarden. I'm a professor here at Stanford

University. And I'd like to welcome you to this first

course on the Design and Analysis of Algorithms.

Now, I imagine many of you are already clear on your reasons for taking this

course. But let me begin by justifying this

course's existence. And giving you some reasons why you

should be highly motivated to learn about algorithms.

So what is an algorithm anyways? Basically it's a set of well defined

rules, a recipe in effect for solving some computational problem.

Maybe you have a bunch of numbers and you want to rearrange them so that they're in

sorted order. Maybe you have a roadmap and an origin

and a destination And you want to compute the shortest path from that origin to

that destination. May be you face a number of different

tasks that need to be completed by certain deadlines and you ant to know in

what order you should accomplish the task.

So that you complete them all by their respective deadlines.

So why study algorithms? Well first of all, understanding the

basics of algorithms and the related field of data structures is essential for

doing serious work in pretty much any branch of computer science.

This is the reason why here at Stanford, this course is required for every single

degree that the department offers. The bachelors degree the masters degree

and also the PHD. To give you a few examples routing and

communication networks piggybacks on classical shortest path algorithms.

The effectiveness of public key cryptography relies on that of

number-theoretic algorithms. Computer graphics needs the computational

primitives supplied by geometric algorithms.

Database indices rely on balanced search tree data structures.

Computational biology uses dynamic programming algorithms to measure genome

similarity. And the list goes on.

Second, algorithms play a key role in modern technological innovation.

To give just one obvious example, search engines use a tapestry of algorithms to

efficiently compute the relevance of various webpages to it's given search

query. The most famous such algorithm is the

page rank algorithm currently in use by Google.

Indeed in a December 2010 report to the United States White House, the

President's counsel of advisers on science and technology argued that in

many areas performance gains due to improvements in algorithms have vastly

exceeded event he dramatic performance gains due to increased processor speeds.

Third, although this is outside of the score, the scope of this course.

Algorithms are increasingly being used to provide a novel lens on processes outside

of computer science and technology. For example, the study of quantum

computation has provided a new Computational viewpoint on quantum

mechanics. Price fluctuations in economic markets

can be fruitfully viewed as an algorthmic process and even evolution can be

usefully thought of as a surprisingly effect search algorthim.

The last two reasons for studying algorthims might sound flippant but both

have more than a grain of truth to them. I don't know about you, but back when I

was a student, my favorite classes were always the challenging ones that, after I

struggled through them, left me feeling a few IQ points smarter than when I

started. I hope this course provides a similar

experience for many of you. Finally, I hope that by the end of the

course I'll have converted some of you to agree with me that the design and

analysis of algorithms is simply fun. It's an endeavor that requires a rare

blend of precision and creativity. It can certainly be frustrating at times,

but it's also highly addictive. So let's descend from these lofty

generalities and get much more concrete. And let's remember that we've all been

learning about and using algorithims since we were little kids.

Explora nuestro catálogo

Inscríbete de manera gratuita y obtén recomendaciones personalizadas, actualizaciones y ofertas.

Coursera brinda acceso universal a la mejor educación del mundo, al asociarse con las mejores universidades y organizaciones, para ofrecer cursos en línea.

© 2018 Coursera Inc. Todos los derechos reservados.

Descargar en la App Store

Consíguelo en Google Play