eecs2001-P Practice Questions
1 Relevant topics
All topics from Lectures 0 − 12 are relevant for the midterm, including regular expressions (but not including the pumping lemma). You should, in particular be comfortable with all questions that have appeared in the first two assignments, or have been solved during the tutorials. Below, I am listing some additional practice questions.
Practice questions
All exercises from chapter 0 in the textbook.
Recall that we use the notation [n] to denote the set {1, 2, 3, . . . , n} of natural numbers from 1 to n. For the following pairs of sets A and B, determine their relation (that is show if one of ⊆, , = or none of these holds between them. Further determine their intersections.
(a) A={n∈Z | ∃k∈Z,k≥0suchthatn=3kandn≤20} and B = {3,6,9,12,15,18}.
(b) A={1,3}×{1,2}andB={(1,1),(2,1),(3,1)}.
(c) A={3,6,9,12,15,18}∩{n∈N|neven}andB=[20]\{n∈N|nodd}
(d) A=P({1,2}×{1})andB={1,2}2 ∪{∅}
Draw the following graphs:
G = ({1, 2, 3, 4}, {{1, 2}, {1, 3}, {1, 4}})
G′ = ([4], {1} × [4])
Let G = (V,E) be a graph. (By default we assume an undirected graph.) Show that being connected by a path is an equivalence relation on the vertices of the graph (consider each vertex to be connected by a path of length 0 to itself). Is being connected by a (directed) path also an equivalence relation in a directed graph?
CS Help, Email: tutorcs@163.com
5. Determine whether the graphs G1 and 2 in the figure above are strongly connected.
6. Let’s consider the following alphabet:
Σ = {+,−,|}
Let’s consider the elements of that alphabet ordered according to the order in which
they are listed above. Now consider the language L={+−+−|, +−−, +−+|, +−|, ||}
IsLalanguageoverΣ? IsanywordinLasubstringofanyotherwordinL? IsL prefix-free? Can you order the words in L lexicographically and in string order?
7. Consider the pairs of sets A and B from the first question. For which ones does the exist a function f : A → B that is one-to-one? For which ones does there exist a function g : A → B that is onto?
8. Prove that in any graph that is a tree, we have
|V | = |E| + 1.
9. I recommend practicing with all exercises from the textbook that relate to material covered in the lectures so far. In particular: Exercises 1.1-1.23, 1.28 and Problems 1.31,1.36-1.43, and 1.51-1.52.
Computer Science Tutoring