关键词 > COMP2022/2922

COMP2022/2922 Assumed Knowledge, with a focus on strings S2 2023

发布时间：2023-09-01

Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

COMP2022/2922

Assumed Knowledge, with a focus on strings

S2 2023

This tutorial covers concepts from discrete mathematics that you will need.

Topics:

1. strings and recursive definitions

2. sets: set-builder notation {x : ...}, operations on sets such as n, U, X, /, and relations be- tween sets such as 己, 才, =

3. functions: domain,codomain, image, associative binary operations

4. finite sets and infinite sets

5. graphs and trees

6. asymptotic notation

7. proofs: providing a counterexample to show a claim is false; proof by contrapositive; proof of negation and proof by contradiction; proof by induction

Conventions:

• We write Z+ for the set of positive integers and Z0(+) for the set of non-negative integers.

• We will often use Python’s slicing notation for indexing, see thedocumentation.

1 Strings

Since this UoS focuses on strings and sets of strings, I’ve put that material first. After doing these questions you should be able to:

1. specify sets of strings in English and set-builder notation

2. reason about simple recursive functions that manipulate strings

3. be able to show that strings are/are not in a given set

An alphabet is a finite set of symbols. For instance, the set of ASCII symbols is an alphabet. A string is a finite sequence of symbols from some alphabet. For example, abracadabra is a string over the alphabet of ASCII symbols. It is also a string over the alphabet of lower-case English letters. A string is like Python’s str object; we can also think of (the contents of) a text file as being a string. Every string has a length (returned by len in Python). There is a single string of length 0, it is called the empty string, and written ϵ ( ’’ in Python). The concatenation of strings u, v is the string uv formed by appending v to the end of u (u + v in Python).

We will use the following exponentiation shorthand for strings. If u is a string and n is a positive integer then un is shorthand for

~->石-小

u · · · u

We use the convention that if n = 0 then un = ϵ . For instance, if u = aab then u0 = ϵ, u1 = u = aab, u2 = uu = aabaab, u3 = uuu = aabaabaab.

In this course we will be interested in strings because inputs to programs, and even programs themselves, can be thought of as strings.

We will also be interested in sets of strings because they naturally model computational problems with ”yes”/”no” outputs (see Lecture 1).

Problem 1.

1. What does it mean for an integer to be even? Is 0 an even integer?

2. If u = u1u2 · · · un is a string over alphabet {0, 1} what does the expression Σ1 ui2i−1 represent? Why do 101 and 10100 evaluate to the same number? What is the value of the expression on the empty string?

Problem 2. In this problem, the alphabet is the set {a, b}.

Give short precise English descriptions of each of these sets of strings.

1. {an bm : n, m ∈ Z0(+)}

2. {an bn : n ∈ Z0(+)}

3. {an b : n ∈ Z0(+)}

4. {u : u is a possibly empty string of as and bs such that | u | = 2n for some integer n}

Problem 3.

1	def myfun(s): # s is a string (using only ASCII	characters)
2	if s== ’ ’ : # empty string
3	return 1
4	if len(s) == 1:
5	return 1
6	if s[0] != s[-1]: # first and last characters	are different
7	return 0
8	t = s[1:len(s)-1] # remove the first and last	characters
9	return myfun(t) # recursive call
myfun is a program that takes as input a string, and returns 0 or 1. Trace the execution of myfun(”abb”) and myfun(”abba”). What does the function do? Argue that your answer is correct. [Advanced] Problem 4. [Extra]

1 def myfun(s): # s is a string that only uses characters a and b

2 if s== ’ ’ : # empty string

3 return 1

4 for i in range(1, len(s)):

5 if (s[0] != s[i]) and myfun(s[1:i]) and myfun(s[i+1:]):

6 return 1

7 # recall that s[1:i] is the substring from index 1 to index i-1

8 # recall that s[i+1:] is the substring from index i+1 to the end

9 return 0

myfun is a program that takes as input a string that only uses characters a and b, and returns 0 or 1.

Trace the execution of myfun(”abb”) and myfun(”abba”).

What does the function do?

Argue that your answer is correct. [Advanced]

Problem 5. In this problem the alphabet is the set of lower-case English letters. Let L be the set of strings of the form ww where w is a string. In other words, these are the strings whose left-half is equal to their right-half.

Now, aabaab is in L; to see this, take w = aab. On the other hand, aaaabaaaaaab is not in L since the left half aaaaba is not equal to the right half aaaaab.

1. Is the empty string in L?

j i

2. Show that the following strings are not in L: a(~)>·石小a b a(~)>·石小a b where i, j ∈ Z+

with 1 ≤ i < j.

j j+2

3. Show that the following strings are in L: a(~)>·石a(小)a(~)>·石a(小) where j ∈ Z+ .

Problem 6.[Extra] In this problem the alphabet is the set of lower-case English letters.

Let L consist of all strings of length a power of 2. E.g., ab, abaa, aaabaaab are strings in L. Show that the following strings are not in L:

1. aaabbbb

2j 2i

2. a · · · a b · · · b for some i, j ∈ Z+ with i < j.

Problem 7.[Extra]

1 def F(n): # input is a non -negative integer , output is an integer

2 if n == 0:

3 return 0

4 if n == 1:

5 return 1

6 return F(n-1)+F(n-2)

The number F(n) is often called the nth Fibonacci number, https://www . youtube.com/watch?v=SjSHVDfXHQ4

What does the function return when given n = 6 as input?

What happens if we take the same code, but interpret 0 and 1 as strings, and + as string concatenation? Let’s write this using as and bs to make it a bit clearer, and rename the function G to distinguish it from F.

1	def G(n): # input is a	non -negative integer , output is a string
2	if n == 0:
3	return a
4	if n == 1:
5	return b
6	return G(n-1)+G(n-2)	# + refers to string concatenation

The string G(n) is often call the nth Fibonacci string, https://en.wikipedia . org/wiki/Fibonacci_word

What is G(6)?

2 Sets

Problem 8. Examine the following formal descriptions of sets so that you under- stand which members they contain. Write a short informal English description of each set.

1. {1, 3, 5, 7, ...}

2. {..., −4, −2, 0, 2, 4, ...}

3. {n | n = 2m for some m ∈ Z0(+)}

4. {n | n = 2m for some m ∈ Z0(+), and n = 3k for some k ∈ Z0(+)}

5. {n | n is an integer and n = n + 1}

6. {rem (n, 2) : n ∈ Z0(+)}, where rem (n, 2) is the remainder when dividing n by 2.

Problem 9. Let A be the set {x, y, z} and B be the set {x, y}.

1. Is A a subset of B?

2. Is B a subset of A?

3. What is A ∪ B?

4. What is A ∩ B?

5. What is A \ B?

6. What is B \ A?

7. What is A × B?

8. What is the power set of B?

Problem 10. Let A, B, Z besets such that A, B ⊆ Z.

1. Write A ∩ B in terms of the sets A, B, Z and only using the operations \ and ∪ .

2. Is the following true? Give reasons: A ⊆ B if and only if A ∩ (Z \ B) = ∅.

Problem 11. If A has a elements and B has b elements, how many elements are in A × B? Explain.

Problem 12. Recall that the power set of a set C is the set of sub- sets of C. E.g., the powerset of C = {a, b, c} has 8 elements, i.e., {∅, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}}. If C is a set with c elements, how many elements are in the power set of C? Explain your answer.

3 Functions

Problem 13. Let X be the set {1, 2, 3, 4, 5} and Y be the set {6, 7, 8, 9, 10}. The unary function f : X → Y and the binary function g : X × Y → Y are described in the following tables.

6 7 8 9 10

1. What is the value off (2)?

2. What are the domain, codomain off , and image off?

3. What is the value of g(2, 10)?

4. What are the domain, codomain off , and image of g?

5. What is the value of g(4, f (4))?

Problem 14. Recall that addition is an associative binary operation,i.e., x + (y + z) = (x +y)+ z, and so we may drop the parentheses and simply write x +y + z. Which of the following binary operations is associative?

1. Concatenation of strings

2. Intersection on sets

3. Union on sets

4. Multiplication on integers

5. Subtraction on integers

6. Division on real numbers

7. Exponential on real numbers

Problem 15.

The idea of a set being closed under an operation (aka function) will come up a few times in this course. A set is closed under some operation if, when we apply that operation to elements in that set, we are guaranteed to get another element in that set.

The set Z+ of positive integers is closed under the addition operation — this means that the sum of any two positive integers is a positive integer. We simply say “Z+ is closed under addition”. On the other hand, Z+ is not closed under subtraction, because if you subtract two positive integers, you are not guaranteed to get back a positive integer. To see this we give a counterexample, e.g., 1 − 3 = −2.

Answer the following questions:

1. Is the set of integers closed under addition? subtraction? multiplication? division?

2. Is the set of even integers closed under addition? subtraction? multiplica- tion? division?

3. Is the set of odd integers closed under addition? subtraction? multiplica- tion? division?

4. Is the set of real numbers closed under addition? subtraction? multiplica- tion? division?

5. Is the set of rational numbers closed under addition? subtraction? multipli- cation? division?

If you answered “no”, you should give a counterexample. If you answered yes, you should give a reason, or even a proof (see the section on ’Proofs’).

4 Finite sets and infinite sets

Recall that a set S is infinite means that for every positive integer n, the set S contains more than n elements.

Infinite sets are a tricky concept — many misconceptions exist. Here are some clarifications:

An infinite set does not have to include everything. For example, the set of strings of even length is infinite, but does not include aaa.

A set can be infinite even though the objects in that set are finite. An individual string is always finite. A set of strings might be infinite, if it contains infinitely many of these finite strings.

Infinite sets don’t have the same notion of size as finite sets. If we take a finite set and add a new element, the resulting set will of course be larger. But if we take an infinite set and add a new element, the resulting set can be exactly paired off with the original set. Eg. we can pair off (0, 1), (1, 2), (2, 3), (3, 4), ... to show that Z0(+) and Z+ have the same size.2

Problem 16. Suppose A is finite and B is infinite. For each of the following sets, say if it is infinite, finite, or we cannot tell without more information. Briefly explain your answers.

1. B ∪ A

2. B ∩ A

3. B / A

4. A / B

Suppose Z is infinite. For each of the following cases, conclude as much as possible about whether A or B are finite or infinite. Briefly explain your answers.

1. Z = A ∪ B

2. Z = A ∩ B

3. Z = B / A

Problem 17. In this course we will see a few operations on sets of strings. For instance, while concatenation is usually an operation on strings, union is an operation on sets of strings.

A collection of sets is closed under some operation if, when we apply that op- eration to sets in that collection, we always get another set in that collection.3 Intuitively, this allows us to ”build up” new sets of strings by combining other sets of strings.

Fix an alphabet Σ (re