DOC PREVIEW
MIT 6 042J - Mini-Quiz

This preview shows page 1-2 out of 5 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 5 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 5 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 5 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Problem 1Problem 2Problem 3Massachusetts Institute of Technology 6.042J/18.062J, Spring ’10: Mathematics for Computer Science March 17 Prof. Albert R. Meyer revised March 17, 2010, 700 minutes Mini-Quiz Mar. 17 Your name: • This quiz is closed book. Total time is 25 minutes. • Write your solutions in the space provided. If you need more space, write on the back of the sheet containing the problem. Please keep your entire answer to a problem on that problem’s page. • GOOD LUCK! DO NOT WRITE BELOW THIS LINE Problem Points Grade Grader 1 8 2 6 3 6 Total 20 Creative Commons 2010, Prof. Albert R. Meyer.2 Your name: Mini-Quiz Mar. 17 Problem 1 (8 points). Starting with some number of 4-cent and 7-cent stamps on the table, there are two ways to change the stamps: (i) Add one 4-cent stamp, or (ii) remove two 4-cent AND two 7-cent stamps (when this is possible). (a) Let A be the number of 4-cent stamps; and B be the number of 7-cent stamps. The chart below indicates properties of some derived variables; fill it in. derived variables: B 4A + 7B rem(B, 2) rem(4 ∗ A + 7 ∗ B, 2) weakly increasing strictly increasing weakly decreasing strictly increasing constant (b) Circle the properties below that are preserved invariants: 1. The number of 7-cent stamps (B) must be even. 2. The number of 7-cent stamps (B) must be greater than 0. 3. The total cost of stamps (4 ∗ A + 7 ∗ B) must be odd. 4. 4A > 7B. (c) Using the Invariant Principle, show that it is impossible to have stamps with a total value of exactly 90 cents on the table when we start with exactly 211 7-cent stamps. (You may use without proof the preserved invariance of some of the properties from part (b).)3 Mini-Quiz Mar. 17 Your name: Problem 2 (6 points). Covering edges were introduced in class problem: if a and b are distinct vertices of a digraph, then a is said to cover b if there is an edge from a to b and every path from a to b traverses this edge. If a covers b, the edge from a to b is called a covering edge. Let D be a finite directed acyclic graph (DAG). (a) If there is a path in D from a vertex, u, to vertex, v, explain why there must be a longest path from u to v. (b) Give a proof of the following claim from the class problem: Claim. If there is a path in D from a vertex, u, to vertex, v, then there is a path from u to v that only traverses covering edges. (c) Show that the Claim fails for the finite digraph, F , with three vertices and edges from every vertex to every other vertex. Hint: What are the covering edges of F ?4 Your name: Mini-Quiz Mar. 17 Problem 3 (6 points). Let G be a connected simple graph. Prove that if an edge in a connected graph is not traversed by any simple cycle, then it is a cut edge.1 1A simple cycle is a subgraph of G isomorphic to the cycle graph Cn for n ≥ 3. An edge is a cut-edge when removing the edge disconnects the graph.MIT OpenCourseWarehttp://ocw.mit.edu 6.042J / 18.062J Mathematics for Computer Science Spring 2010 For information about citing these materials or our Terms of Use, visit:


View Full Document

MIT 6 042J - Mini-Quiz

Documents in this Course
Counting

Counting

55 pages

Graphs

Graphs

19 pages

Proofs

Proofs

14 pages

Proofs

Proofs

18 pages

Proofs

Proofs

18 pages

Quiz 1

Quiz 1

9 pages

Quiz 2

Quiz 2

11 pages

Load more
Download Mini-Quiz
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Mini-Quiz and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Mini-Quiz 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?