CSE 21

Math for Algorithms

Be comfortable converting from **AND**s (set intersections ∩) to **OR**s (set unions ∪) and vice-versa. Recall De Morgan's laws! This conversion can occasionally come in handy for counting problems. For example, if it seems difficult to count

- |set A ∩ set B|
- |set which meets condition A
**AND**condition B|

via some application of the product rule, try counting

- |¬(¬set A ∪ ¬set B)|
- |¬(set which doesn't meet condition A
**OR**doesn't meet condition B)|

via some application of the sum rule (inclusion-exclusion in the general case). Note: ¬ (**NOT**) denotes the complement of a set and |x| denotes the size of a set.

As a more concrete example, take a look at problem 1g on Group HW1. It asks for

the number of passwords with >= 1 lowercase letterAND>= 1 uppercase letterAND>= 1 numeral

which is hard to count directly. Instead, you should have counted

(the total number of passwords) - (the number of passwords with 0 lowercase lettersOR0 uppercase lettersOR0 numerals)

which is a much easier prospect (hint: i-e!). Using the following definitions:

L: "has >= 1 lowercase letter"

U: "has >= 1 uppercase letter"

N: "has >= 1 numeral"

you'll see that we can restate the conversion as

|set with LANDUANDN|

=|¬(set with (NOTL)OR(NOTU)OR(NOTN))|

=|universe| - |set with (NOTL)OR(NOTU)OR(NOTN)|

noting in the final step that the **size of the complement of a set** is merely the **size of the universe** minus the **size of the set**. (*Likewise, the size of a set is equal to the size of the universe minus the size of the complement of the set.*)

Remember, we probably don't intend to make you write and count a billion sub-cases. If you find yourself doing this, consider trying to convert the problem to something more tractable, e.g. using De Morgan's laws.