Explore
For Enterprise
Join for Free
Log In

Browse
Search
For Enterprise
Log In
Join for Free

Problem Overview

Loading...

Algorithmic Toolbox

University of California San Diego

4.7 (5,390 ratings) | 170K Students Enrolled

Course 1 of 6 in the Data Structures and Algorithms Specialization

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

Skills You'll Learn

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

Reviews

4.7 (5,390 ratings)

5 stars
4,011 ratings
4 stars
1,096 ratings
3 stars
193 ratings
2 stars
39 ratings
1 star
51 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 ...

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

Taught By

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

Transcript

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.

Get it on Google Play

Coursera
About
Leadership
Careers
Catalog
Certificates
MasterTrack™ Certificates
Degrees
For Enterprise
For Government
For Campus

Community
Learners
Partners
Developers
Beta Testers
Translators

Connect
Blog
Facebook
LinkedIn
Twitter
Instagram
YouTube
Tech Blog

More
Terms
Privacy
Help
Accessibility
Press
Contact
Directory
Affiliates