Reading:

• Lectures 1 and 2 of Automata and Computability
• Chapters 1-5 and 10 of Learning Perl, Third Edition
• Chapter 1 of Hopcroft, Motwani, and Ullman (HMU; on web page)

Total Points: 140

Problem 0.0 [30 points]

1. Gain access to Perl. Consulting Chapter 1 of Learning Perl and the CPAN links on the class homepage, you may install it on your own machine. Else, it is available on the department's UNIX Lab machines. For this part, report what platform (processor and OS), you used.
2. Getting Started. Do Exercise 1, on page 18 of Learning Perl. Turn in your source code.
3. Scalars. Do Exercise 5, on page 39 of Learning Perl. Turn in your source code and report your program's answer for Hello, world! and 5.
4. Arrays. Do Exercise 2, on page 55 of Learning Perl. Turn in your source code and your program's output for 4, 1, 2, 5, 3, 6, 7, 6, 3, 5, 2, 1, 4 using the word list provided in the problem.
5. Subroutines. Do Exercise 1, on page 71 of Learning Perl. Turn in your source code (for the subroutine only) and the result of running it with the example program on page 72, entering 1, 2, 3, 4, 5, 6 on separate lines, when prompted.
6. Hashes. Do Exercise 2, on page 85 of Learning Perl. You must sort the output. Test your program on the files frost.txt and mlk.txt available in the Code Repository of the course webpage. Turn in both source code and results.

Problem 0.1 [10 points]

[Sipser] Examine the following formal descriptions of sets so that you understand which members they contain. Write a short informal English description of each set. You may assume the reader knows about the set of integers (denoted Z), the positive integers (denoted Z₊), etc.

1. {1,3,5,7,...},
2. {...,-4,-2,0,2,4,...}
3. {n | n=2m for some m in Z₊}
4. {n | n=2m for some m in Z₊ and n=3k for some k in Z₊}
5. {n | n is an integer and n=n+1 }

Problem 0.2 [10 points]

[Sipser] Write formal descriptions of the following sets.

1. The set containing the numbers 1, 10, and 100.
2. The set containing all integers greater than 5.
3. The set containing all positive integers less than 5.
4. The set containing the numbers 1, 10, 100, 1000, ... .
5. The set containing nothing at all.

Problem 0.3 [10 points]

[Sipser] Let A be the set {x,y,z}, and B be the set {x,y},

1. Is A a subset of B? Is B a subset of A?
2. What is A U B?
3. What is A ^ B?
4. What is A x B?
5. What is the power set of B?

Problem 0.4 [10 points]

Draw a picture of each of the following sets. Below, a, b \in R (they are real numbers) with a < b.

1. {1,2,3},
2. [0,1] x {0,1},
3. [0,1] x [a,b],
4. {1,2,3} x {a,b},
5. {a,b} x [0,1].

Problem 0.5 [10 points]

How many elements are there in the sets

1. {-2, -1, ... , 11}, and
2. {0,1} x {a,b,c}?
3. If X has m elements and Y has n elements, how many elements are there in X x Y?
4. Suppose X_i has m_i elements, for i=1,2, ... ,N. How many elements are there in X₁ x X₂ x ... x X_N ?
5. If X has m elements, how many elements are there in the power set of X?

Problem 0.6 [10 points]

[Sipser] Let X be the set {1,2,3,4,5} and Y be the set {5,6,7,8,9}. The unary function f: X --> Y and the binary function g: X x Y --> Y are described in the following tables.

n f(n) 1 2 3 4 5 6 7 6 7 6

g 5   6   7   8   9 1 2 3 4 5 9   9   9   9   9 6   7   8   9   5 6   6   7   7   8 8   7   6   5   9 5   5   5   5   5

1. What is the value of f(2)?
2. What are the domain and range of f?
3. What is the value of g(2,9)?
4. What are the domain and range of g?
5. What is the value of g(4,f(4))?

Problem 0.7 [10 points]

1. [Sipser] Consider the directed graph G=(V,E) where V, the set of nodes, is {1,2,3,4} and E, the set of edges, is {(1,2),(2,3),(1,3),(2,4),(1,4)}. Draw the graph G.
2. Consider the two drawings of Example 5.2 on page 30 of Automata and Computability. Disregarding the circles and the arrows into the circles, treat them as directed graphs and write formal descriptions for them.

Problem 0.8 [15 points]

In each of the following, carefully identify the basis case(s) and the inductive step.

1. Prove by induction on n that the sum of the first n positive integers is S(n)=n(n+1)/2.
2. Prove by induction on n that the sum of the first n cubes (of positive integers) is (S(n))², where S(n) is defined in part (a).
3. Prove by general induction that any integer greater than or equal to 12 can be written as a sum of 3's and 7's.

Problem 0.9 [25 points]

Miscellaneous Exercise 1, page 315 of Automata and Computability. Give a formal proof.