Goals of Homework

• Learn to use sets and functions, and see how they act as formalisms for CS concepts.
• Understand the differences between symbols, strings, and languages; see how they appear in CS concepts.

Concepts

• Set-builder notation
• Set notation
• Set operations: union, intersection, complement, Cartesian product
• Relationship between C++ iterators and sets
• Function notation
• Function vocabulary: domain, range, onto (surjective), one-to-one (injective), and both (bijective).
• Relationship between C++ functions or methods and mathematical functions.
• Symbols, strings, and languages

Problems

1. (4 points) Section 2.1 problem 1 parts b and d.
2. (4 points) Section 2.1 problem 2 parts a and c.
3. (5 points) Section 2.1 problem 10 parts a, b, c, d, e. (International section 2.1 problem 8, a, b, c, d, e; 8th ed. section 2.1 problem 11 parts a, b, c, d, e)
4. (4 points) Section 2.2 problem 3 parts a-d.
5. (2 points) For $A = \{1,2\}$ and $B = \{a,b,c\}$, find $A \times B$.
6. (2 points) Find a simple counterexample that shows the following is false: $\mbox{if } A \cup B = A \cup C \mbox{ then } B = C$. Note that finding a counterexample is a useful way to show that something is false.
7. (2 points) Read the description of the std::set container in the standard template library. Does the definition of set match the definition in the book? Why or why not?
8. (2 points) Section 2.3 problem 2.
9. (4 points) Section 2.3 problem 12 parts a-d. Give a counter-example when false.
10. (4 points) Section 2.3 problem 13 parts a-d. Give a counter-example when false.
11. (4 points) Section 2.3 problem 20 parts a-d. (International Section 2.3 problem 16 parts a-d.)
12. (3 points) Section 2.3 problem 22 parts a, b, and d. Give a counter-example when false. (International section 2.3 problem 18 parts a, b, and d)
13. (2 points) Read this cplusplus.com discussion. Does this use of function match the definition in the book? Why or why not?
14. (7 points) Consider a set of symbols, V={a,b,c}. Identify the following as a symbol, string, or a language. List all that apply. See Homework 1 FAQ for definitions.
• a
• aa
• {a, b, c}
• {aa, bb}
• {}
• $\{ \lambda\}$
• $\lambda$