The objectives are

  • Show a relation is an equivalence relation
  • Identify equivalence relations from zero-one matrices
  • Identify equivalence relations from directed graphs
  • Define a partition with its identical equivalence relation
  • Complete a relation to be an equivalence relation
  • Identify relations that are partial orders
  • Sort lists of tuples by lexicographic order
  • Find maximal and minimal elements in a partial order
  • Determine least upper bounds and greatest lower bounds given a partial order and a set
  • Given a partial order, determine if it is also a lattice
  • Draw Hasse diagrams for partial orders
  • Show how a topological sort proceeds on a partial order

Problems

All problems are worth 3 points and reference problems in the course text. International book problems switch from chapter 9 to be chapter 7. The number is the same on all but the last as noted.

  1. (5 points) 9.5.2
  2. (4 points) 9.5.16 (ad = bc is multiplication and not concatenation)
  3. (1 points) 9.5.22
  4. (3 points) 9.5.24
  5. (4 points) 9.5.42
  6. (5 points) 9.5.44
  7. (4 points) 9.5.48
  8. (2 points) 9.5.67
  9. (5 points) 9.6.2
  10. (4 points) 9.6.4 (for part a, assume two different people can be the same height)
  11. (3 points) 9.6.16 (the symbol in part c is lexicographic comparison)
  12. (1 points) 9.6.20
  13. (4 points) 9.6.22
  14. (4 points) 9.6.34 (| is the divisibility operator, a|b is true if and only if b is a multiple of a)
  15. (4 points) 9.6.44
  16. (1 points) 9.6.62
  17. (2 points) 9.6.66 (7.6.64 intl)
cs-236/homework-8.txt · Last modified: 2017/11/21 11:38 by kylej13
Back to top
CC Attribution-Share Alike 4.0 International
chimeric.de = chi`s home Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0