Return to Video

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