English subtitles

← Generating a Formula - Intro to Algorithms

Get Embed Code
3 Languages

Showing Revision 3 created 05/25/2016 by Udacity Robot.

  1. What I want you to think about is, imagine that we've got a graph with n nodes and m edges,
  2. and we're going to try to find out whether it's colorable well with k colors
  3. by turning it into a big formula like the one I just showed you.
  4. I want to know how many clauses are in the formula, and just to make that a bit more concrete
  5. a clause is the sort of thing that I got here in parenthesis, it's between the n's.
  6. We have a list of things that are combined and then there's an n and then there's more things
  7. that are combined and an n, so how many things are being ended together in the formula.
  8. So I want you to figure out an actual expression in terms of k, n and m that will tell you the answer,
  9. but I'll actually ask you to do it for just a concrete example.
  10. So imagine we've got 3 colors, 8 nodes and 20 edges, how many clauses are in the formula
  11. that result from converting this 3 colorability problem into a satisfiability problem,
  12. and when you have your answer, write it in this box and we'll check it for you.