Problem Overview

Loading...

From the course by University of California San Diego

Algorithmic Toolbox

4366 ratings

University of California San Diego

Algorithmic Toolbox

4366 ratings

Course 1 of 6 in the Specialization Data Structures and Algorithms

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).

From the lesson

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!

Problem Overview2:44

Selection Sort8:08

Merge Sort10:53

Lower Bound for Comparison Based Sorting12:10

Non-Comparison Based Sorting Algorithms7:43

Meet the Instructors

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, and welcome to the sorting problem lesson.

As usual, we start with a problem I'll review.

So sorting is a fundamental computational problem.

Your input in this problem consists of a sequence of elements, and

your goal is to output this element in, for example, non-decreasing order.

The formal statement of this problem is as follows.

You are given a sequence of finite elements.

We will usually denote the sequence by A throughout this lesson.

And your goal is to output these same elements in non-decreasing order.

Once again,

sorting is an important computational task used in many efficient algorithms.

For some algorithms, it is just as important to process

given elements in non-decreasing order, going from smaller ones to larger ones.

In some other algorithms, just by sorting your input data,

you gain a possibility to perform your queries much more efficiently.

A canonical example of such situation is a search problem.

In this problem, we are given a sequence of finite elements.

And your goal is to check whether a particular element is present

in your sequence.

A simple way to solve this problem, is of course, just to scan your input sequence

from left to right and to check, whether your element is present in this sequence.

This gives you a linear kind algorithm.

And you know already that if you input data,

if you input sequences you sorted, then you can do this much more faster.

Basically, in time, in logarithmic time, in the size of your input sequence.

So ou first compare your element to the middle element.

If it is just few element, then you are done, if it is not, you continue

with the left half of your sequence or the right half of your sequence.

So in logarithmic number of comparison, and the worst case, you

will be able to say whether your element is present in this sequence or not.

So, if you are given a sequence and you are expecting many such queries.

You're expecting to be asked to check whether a given object is present or not.

For me such objects, then it just makes sense to first sort your input data and

only then perform all these queries.

This will give you a much more efficient algorithm in general.

All right.

And this is only a small example.

We will see many other situations,

where sorting your data first helps to perform queries much more efficiently.

So in the subsequent videos of this lesson,

we will study many efficient sorting algorithms.

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