## ← Generating a Formula - Intro to Algorithms

• 3 Followers
• 12 Lines

### Get Embed Code x Embed video Use the following code to embed this video. See our usage guide for more details on embedding. Paste this in your document somewhere (closest to the closing body tag is preferable): ```<script type="text/javascript" src='https://amara.org/embedder-iframe'></script> ``` Paste this inside your HTML body, where you want to include the widget: ```<div class="amara-embed" data-url="http://www.youtube.com/watch?v=Moo_ayWSyzA" data-team="udacity"></div> ``` 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.