ICS 6B
Fall 2013
Homework 6


Due: Wednesday, Nov 13

Covers Sections 3.3-3.5

  1. Below is a Hasse diagram for a partial order.

    1. Name the minimal elements.
    2. Name the maximal elements.
    3. Which of the following pairs are comparable? (A, D), (B, E), (G, F), (D, B), (C, F), (C, E)

  2. Draw a Hasse diagram for the following relation on the set A={a, b, c, d, e, f}. R = {(b, e), (b, d), (c, a), (c, f), (a, f), (a, a), (b, b), (c, c), (d, d), (e, e), (f, f)}.

  3. For each relation defined below, indicate whether the relation is a partial order or strict order or neither. In the case that it is a partial order or a strict order, indicate whether it is also a total order. Justify your answers. Note that in some cases "not necessarily" can be a correct answer.

    1. The domain is the set of all integers. a is related to b if b = a⋅3n, for some positive integer n.

    2. The domain is the set of all runners in a race. a is related to b is a beats b. Ties are possible.

    3. The domain is the set of all runners in a race. a is related to b is a beats b. Ties are not possible.

    4. The domain is the set of all integers. a is related to b if a and b are relatively prime.

    5. The domain is the power set of a finite set. X is related to Y if X-Y is not empty.

    6. The domain is the set of all words in the Engilsh language (as defined by, say, Webster's dictionary). Word x is related to word y if x appears before y in alphabetical order.

    7. The domain is the set of all words in the Engilsh language (as defined by, say, Webster's dictionary). Word x is related to word y if x appears as a substring of y. For example, "ion" is related to the word "companions" because the letters i-o-n appear in order in the word "companions".

    8. The domain is the set of all students in a class. Student x is related to student y if x knows student y's phone number.

    9. The domain is the set of all cell phone towers in a network. Two towers can communicate if they are within a distance of three miles from each other. x is related to y, if x can send information to y through a path of communication links.

    10. The domain is the set of members of a chess club. x is related to y if x has ever beaten y in a game of chess

  4. Which of the following graphs are acylic? For each graph that is acyclic, give it's transitive closure (i.e. G+).


  5. Give two different topological sorts for the digraph below:


  6. Given the graph below, which orderings of the vertices are topological sorts for the graph?

    1. b, e, c, g, f, a, d
    2. b, g, f, c, e, a, d
    3. b, e, c, g, f, a, d
    4. b, e, c, g, a, f, d

      1. Below is a set of required courses for a degree. The directed acyclic graph shows the prerequisite structure for the courses. Your job is to devise an academic plan for a student. An academic plan is a set of courses for the student to take in each quarter. In each case, you need to devise an academic plan which respects the prerequisites and takes the fewest number of quarters. You can assume that every course is offered in every quarter.

        1. Devise an academic plan for the student if he can only take one course per quarter.
        2. Devise an academic plan for the student if he can take up to two courses per quarter.
        3. Devise an academic plan for the student if he can take up to three courses per quarter.
        4. What's the fewest number of quarters the degree will take if the student can take an unlimited number of courses per quarter?