6.042/18.062J Mathematics for Computer Science October 15, 2010 Tom Leighton and Marten van Dijk Problems for Recitation 11 1. Give a description of the equivalence classes associated with each of the following equivalence relations. (a) Integers x and y are equivalent if x ≡ y (mod 3). (b) Real numbers x and y are equivalent if �x� = �y�, where �z� denotes the smallest integer greater than or equal to z. 2. Show that neither of the following relations is an equivalence relation by identifying a missing property (reflexivity, symmetry, or transitivity). (a) The “divides” relation on the positive integers. (b) The “implies” relation on propositional formulas.2 Recitation 11 3. Here is prerequistite information for some MIT courses: 18.01 6.042 18.01 18.02→ → 18.01 18.03 6.046 6.840→ → 8.01 8.02 6.01 6.034→ → 6.042 6.046 18.03, 8.02 6.02→ → 6.01, 6.02 6.003 6.01, 6.02 6.004→ → 6.004 6.033 6.033 6.857→ → (a) Draw a Hasse diagram for the corresponding partially-ordered set. (A Hasse diagram is a way of representing a poset (A, �) as a directed acyclic graph. The vertices are the element of A, and there is generally an edge u v if u � v.→However, self-loops and edges implied by transitivity are omitted.) You’ll need this diagram for all the subsequent problem parts, so be neat! (b) Identify a largest chain. (A chain in a poset (S, �) is a subset C ⊆ S such that for all x, y ∈ C, either x � y or y � x.) (c) Suppose that you want to take all the courses. What is the minimum number of terms required to graduate, if you can take as many courses as you want per term? (d) Identify a largest antichain. (An antichain in a poset (S, �) is a subset A ⊆ S such that for all x, y ∈ A with x =� y, neither x � y nor y � x.)3 Recitation 11 (e) What is the maximum number of classes that you could possibly take at once? (f) Identify a topological sort of the classes. (A topological sort of a poset (A, �) is a total order of all the elements such that if ai � aj in the partial order, then ai precedes aj in the total order.) (g) Suppose that you want to take all of the courses, but can handle only two per term. How many terms are required to graduate? (h) What if you could take three courses per term? (i) Stanford’s computer science department offers n courses, limits students to at most k classes per term, and has its own complicated prerequisite structure. De-scribe two different lower bounds on the number of terms required to complete all the courses. One should be based on your answers to parts (b) and (c) and a second should be based on your answer to part (g).MIT OpenCourseWarehttp://ocw.mit.edu 6.042J / 18.062J Mathematics for Computer Science Fall 2010 For information about citing these materials or our Terms of Use, visit:
View Full Document
Unlocking...