## Decision Problems - Intro to Algorithms

• 0:00 - 0:03
To make some of the issues, we're going to be talking about simpler.
• 0:03 - 0:09
We're going to focus in on some sense very simple kinds of problems.
• 0:09 - 0:12
Problems that take inputs just like what we've been looking at.
• 0:12 - 0:18
Be the graph or less, whatever happens to be and processes that to get an answer,
• 0:18 - 0:20
and the answer is just 0 or 1, yes or no.
• 0:20 - 0:25
So that's the sense in which it's making a decision. It's making a yes no decision base on the inputs.
• 0:25 - 0:31
An example is graph connectivity where you're given a graph and your ask,
• 0:31 - 0:36
are all the nodes reachable from all the other nodes in the graph and the answer is either yes or no.
• 0:36 - 0:38
It is either connected or it's not connected.
• 0:38 - 0:43
So even though this output is very very simple just 0 or 1 one bit.
• 0:43 - 0:45
It can actually be fairly complicated.
• 0:45 - 0:51
Sometimes very very complicated to take the input and decide whether it is zero or one.
• 0:51 - 0:58
Here's another example. If I give you a graph and node v and a node u and a number k.
• 0:58 - 1:04
Those are the inputs. The question is can v be reached in fewer than k steps from u?
• 1:04 - 1:07
Another question is given a graph, is it a tree? Yes or no.
• 1:07 - 1:12
For it to be a tree, it needs to be connected and not have any cycles in it. No loops.
• 1:12 - 1:17
Now the decision problem is given a graph, is there a bridge link somewhere in the graph?
• 1:17 - 1:22
An edge that if it gets removed separates the graph into two separate pieces.
• 1:22 - 1:28
Given a graph and a number K. Is there a pair of nodes that are K steps apart.
• 1:28 - 1:33
That the shortest path between them is no more than K steps.
• 1:33 - 1:35
Now the question is G bipartite.
• 1:35 - 1:40
This was a homework problem or they were a closely related homework problem
• 1:40 - 1:44
where you can take a graph and try to work out whether it is separable
• 1:44 - 1:49
into two sets of nodes with edges only going between the sets.
• 1:49 - 1:54
Now you could argue that in sometimes this problems are a little bit silly.
• 1:54 - 1:59
We don't often want to know just one bit of answer, we want to know something like,
• 1:59 - 2:03
is there a pair of nodes K steps apart but find me a pair of nodes K steps apart,
• 2:03 - 2:11
or is the graph bipartite but separated into two pieces and show me what those pieces are,
• 2:11 - 2:15
or can v be reached in fewer than K steps from u?
• 2:15 - 2:17
Well if it can be show me the path.
• 2:17 - 2:21
I really like to know the path cause that's what I'm going to be able to work with.
• 2:21 - 2:26
So an interesting fact about decision problems is that they are often directly relatable
• 2:26 - 2:32
to the version of the problem that your interested and that actually gives the answer,
• 2:32 - 2:39
and sometimes you can actually connect them with only a polynomial amount of extra work.
• 2:39 - 2:46
So basically, if the decision problem is efficient so is the problem that returns the more interesting input.
Title:
Decision Problems - Intro to Algorithms
Video Language:
English
Team:
Udacity
Project:
CS215 - Intro to Algorithms
Duration:
02:47
 Udacity Robot edited English subtitles for Decision Problems - Intro to Algorithms Gundega edited English subtitles for Decision Problems - Intro to Algorithms Amara Bot added a translation

# English subtitles

## Revisions Compare revisions

• API
Udacity Robot
• Gundega
• Amara Bot