Name: 0.2 Data Structures and Algorithms: Computational Problems
Uploaded: 2025-01-06T13:31:39.000Z
Duration: 6 min 33 s
Description: Thousands of YouTube videos with English-Chinese subtitles! Now you can learn to understand native speakers, expand your vocabulary, and improve your pronunciation...

Okay, so let's talk about computational problems and develop a definition for computational problems.

So we won't dwell on a formal definition, that'll be covered in other courses like 347 and 547.

Adverbs of manner

So informally, for our class, a computational problem describes a problem that has a structured collection of input data and criteria for correct solution.

Okay, so let's look at an example computational problem.

So we're going to be looking at sorting as our first computational problem.

So this applies to the example problem that we've already discussed.

You've got a big pile of books, you want to put it into order, you could sort it.

So a lot of libraries use call numbers that are numbers, literally.

So a sorting process that works with numbers seems like an appropriate choice.

We're going to be even more precise, though, we're going to focus just on integers.

So let's break the idea of a computational problem down into its two different parts, a structured collection of input data.

And let's talk about what that means for our sorting problem.

We'll come back to that in just a second.

But before we do, let's also think about our criteria for a correct solution.

Sorted seems pretty straightforward, right?

But again, we'll be a little bit more precise.

Okay, so now let's be more precise about both of those points.

So a structured collection of input data, what we really mean in this case today is an array of data.

And we want data that is of a data type that is totally orderable.

Okay, so what this means is in terms of discrete math, the data type must be able to be a total order.

So a total order is a type that is a total order, is something that basically has the notion of a less than or equal to operation.

For any two elements, we can determine if one of them comes before the other one.

So there's some clear way to answer the question, does x come before y?

Okay, so let's be even more precise in our problem definition.

Our structured collection of input data is an input array of integers, okay?

Okay, so what about our second criteria, the criteria for correct solution?

Earlier, we just said ordered seems simple enough, but let's be even more precise with that.

Not only should it be sorted, ordered, it should contain the same values.

So in a sense, we want some idea of the conservation of data.

We don't wanna create or destroy data in our output data, okay?

And of course, the data should be sorted.

But we can fall back to our definition of a total order for our definition of sorted.

Basically, for any two elements, x and y, if x is less than y, if x comes before y, we would expect x to come before y in our final array.

Okay, there are lots of other examples of computational problems that are really interesting, and many of them are pervasive in computer science.

So one of them is the shortest path problem, where you're trying to minimize some concept of distance between two places.

So Google Maps oftentimes does shortest path sorts of problems.

Famous computer science problem is called the traveling salesperson problem.

In the traveling salesperson problem, there's a salesperson who's going to travel amongst multiple cities and then return home.

And the goal is to find a path amongst all those cities that's as short as possible, maybe takes as little time as possible or uses as little gas as possible, so on.

In fact, there are a whole bunch of different types of optimization problems that try and minimize a cost of some sort or maximize profit of some sort.

There are all sorts of subtle variations on the idea of minimization and maximization that all fall into the class of optimization problems.

Another interesting class of problems is factoring.

So factoring prime numbers is an important part of modern cryptography.

Another really interesting problem is called the halting problem.

So the basic premise of the halting problem is you've got some sort of a finite computer program.

Basically, you're given a piece of code and you have to identify whether the code will ever finish or not on a given input set.

It turns out that that's an unusually hard problem.

Okay, so let's talk about our next major component here, an algorithm.

An algorithm is something that will solve a computational problem.

So the term algorithm is named after a 9th century mathematician, one of the people who helped foster the numeric system that we currently use.

The basic definition of an algorithm is that it's an effective procedure for taking any instance of a computational problem and finding a correct solution.

So let's break down all three of those parts.

So first off, it's an effective procedure.

What we really mean by that is this is something that can be turned into a computer program.

That halting problem that was mentioned just a minute ago, it turns out there's no real way to convert that into an algorithm, into a computer program.

Our second point, for taking any instance of a computational problem.

So that means that any valid input set should work, any.

Not just some, it shouldn't just work on some input sets, it should work on any.

Okay, and our third component, finding a correct solution.

So in the context of 247, we mean it's 100% perfectly correct all the time.

In some contexts in computer science, we're looking for things that are probabilistically correct.

It's not the case for our definition in 247.

 Okay, so with that, let's take a concrete look at our sorting problem and talk about a couple of different ways it could be solved.