Explore
For Enterprise
Join for Free
Log In

Arts and Humanities
Business
Computer Science
Data Science
Information Technology
Health
Math and Logic
Personal Development
Physical Science and Engineering
Social Sciences
Language Learning
Degrees
Certificates

Explore all of Coursera

Browse
Search
For Enterprise
Log In
Join for Free

Reduction 2

Loading...

Advanced Algorithms and Complexity

University of California San Diego

4.6 (315 ratings) | 32K Students Enrolled

Course 1 of 6 in the Data Structures and Algorithms Specialization

You've learned the basic algorithms now and are ready to step into the area of more complex problems and algorithms to solve them. Advanced algorithms build upon basic ones and use new ideas. We will start with networks flows which are used in more typical applications such as optimal matchings, finding disjoint paths and flight scheduling as well as more surprising ones like image segmentation in computer vision. We then proceed to linear programming with applications in optimizing budget allocation, portfolio optimization, finding the cheapest diet satisfying all requirements and many others. Next we discuss inherently hard problems for which no exact good solutions are known (and not likely to be found) and how to solve them in practice. We finish with a soft introduction to streaming algorithms that are heavily used in Big Data processing. Such algorithms are usually designed to be able to process huge datasets without being able even to store a dataset.

Skills You'll Learn

Python Programming, Linear Programming (LP), Np-Completeness, Dynamic Programming

Reviews

4.6 (315 ratings)

5 stars
223 ratings
4 stars
64 ratings
3 stars
17 ratings
2 stars
6 ratings
1 star
5 ratings

YC

May 15, 2019

This is a very challenging course in the specialization. I learned a lot form going through the programming assignments!

NN

Jan 04, 2017

Loved what I learnt, I also implemented a project using Google MAP API for the organization I'm working at

From the lesson

Streaming Algorithms (Optional)

In most previous lectures we were interested in designing algorithms with fast (e.g. small polynomial) runtime, and assumed that the algorithm has random access to its input, which is loaded into memory. In many modern applications in big data analysis, however, the input is so large that it cannot be stored in memory. Instead, the input is presented as a stream of updates, which the algorithm scans while maintaining a small summary of the stream seen so far. This is precisely the setting of the streaming model of computation, which we study in this lecture. The streaming model is well-suited for designing and reasoning about small space algorithms. It has received a lot of attention in the literature, and several powerful algorithmic primitives for computing basic stream statistics in this model have been designed, several of them impacting the practice of big data analysis. In this lecture we will see one such algorithm (CountSketch), a small space algorithm for finding the top k most frequent items in a data stream.

Introduction5:23

Heavy Hitters Problem7:33

Reduction 14:35

Reduction 26:30

Basic Estimate 18:04

Basic Estimate 27:14

Final Algorithm 15:27

Final Algorithm 212:57

Taught By

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

Transcript

I have said that if we would like to design an approximate data structure for

finding the top key elements in a data stream,

it is useful to first design a data structure for ApproxPointQuery.

So now let me make this statement precise and give a formal reduction.

I will show that if we have the data structure for PointQuery,

then an exact data structure for find top follows.

And, similarly, if we have data structure for ApproxPointQuery,

then approximate find top follows as well.

And I'll do this in a few steps.

And I'll start with the simplest possible case.

Suppose that we want to find the top one,

the most frequent element in the data stream, so k is 1.

Now we assume that we have a data structure for exact PointQuery.

We want to find top data structure for k equals 1.

Look, so we're given a stream S as a sequence of items, i1, i2 through iN.

We will maintain a data structure for PointQuery.

Besides that, we will maintain two other variables.

One is the current maximum,

the current most frequent element in the stream so far.

The second one is its frequency.

We initialize them to null and zero initially, and

then we look at every position p between 1 and N on the stream.

We'll look at the data item that arrives in position p.

We call the PointQuery data structure to get the count of this item so far.

Let's call it f.

Now, we check.

If the current maximum is the data item that we're looking at,

then we simply update its count and proceed.

If we're not actually storing any of the data items,

which only happens at the very beginning of the stream,

then we store the item ip, and initialize its frequency to 1.

Now otherwise, we compare the frequency of the item that we're storing

to the frequency of our current item, as reported by PointQuery.

And if one is smaller than the other one, then we just swap them.

Okay, so why does this work?

Well, because in each position in the stream the current maximum,

the variable that we're storing is either NULL or

actually contains the current most frequent element so far.

Good, so this is a very simple reduction.

Now does it generalize from k equals 1 to k bigger than 1?

Well yes, it does.

And it works as follows.

Again, we'll assume that we have an exact PointQuery data structure, which is

a somewhat unrealistic assumption, but it's useful for our development.

Now we're given a stream of data items.

We'll maintain the PointQuery data structure, but

now instead of just two variables, we'll maintain a heap

H of at most k elements by count, by their count so far in the stream.

Good, so for each position p between 1 and n, we look at the current data item,

we ask PointQuery to give us the frequency of this data item so far.

We'll call it f.

If the heap contains our data item already,

we'll simply update its count and continue.

Otherwise, if the heap contains fewer than k elements,

we just add our item to the heap with the current count.

Now if the heap actually contains exactly k elements, then we'll look at

the minimum, the least frequent element that we're currently storing in the heap.

If that element is less frequent than the one we're holding in our hand, ip,

then we evict the least frequent element from the heap and

insert our current element with the count as given by PointQuery.

Okay, so why does this work?

Well, it is not hard to see that following is true.

For simplicity, let's assume that the set of top k,

in most frequent items is actually unique.

The argument is very similar without that, and is left as an exercise.

So in this case for every item i, in the top k,

let pi denote the last position in the stream where i occurs.

We'll notice that then at position pi, our element i will be inserted into

the heap if it wasn't there before, and, after that, it will never be evicted.

And so the reduction actually works.

Good, so this is the reduction that we got.

If we have an exact data structure for maintaining exact PointQuery,

then we can find the top k items quite easily.

Well, the question is why is this useful?

Because before we argued that exact PointQuery is unrealistic.

We need to pretty much store the entire stream.

Well it turns out that the exactly same reduction works for

the approximate version of the problem.

If we have a small space data structure for ApproxPointQuery, and that's something

that actually exists and we will construct it at the end of this lecture, then we can

approximately find the top key elements using essentially the same set of code.

Just whenever we look at an item ip, the current data item arriving in the stream,

we ask our ApproxPointQuery to give us an estimate of the count, and

use that estimate just as if it was the exact.

Okay so, the proof of this is very similar.

One can check that if we have a procedure data structure ApproxPointQuery,

that for every element i at every point in the stream returns an estimate

of i's count so far, which is off by at most fk,

which is the final frequency of the kth dominant element times epsilon,

then we can get a data structure for approximate top k.

Okay, so now that we have this reduction, in the rest of the lecture,

we will concentrate on designing a small space data structure for

solving the ApproxPointQuery problem.

So we want to design a small space data structure that observes the date items in

the stream, and at the end of the stream, can be queried to give an approximate

answer to the number of occurrences of any given data item so far.

What we will have to specify are the actual parameters of our data structure,

so how much space do we use?

What is the quality of approximation that we provide?

And what is the success probability with which we work?

This will be done in the rest of the lecture.

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

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

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