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
(4 points) Section 2.1 problem 1 parts b and d.
(4 points) Section 2.1 problem 2 parts a and c.
(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 points) Section 2.2 problem 3 parts a-d.
(2 points) For $A = \{1,2\}$ and $B = \{a,b,c\}$, find $A \times B$.
(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.
(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?
(2 points) Section 2.3 problem 2.
(4 points) Section 2.3 problem 12 parts a-d. Give a counter-example when false.
(4 points) Section 2.3 problem 13 parts a-d. Give a counter-example when false.
(4 points) Section 2.3 problem 20 parts a-d. (International Section 2.3 problem 16 parts a-d.)
(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)
-
(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$
Back to top
search
