Most of this material is review from CS 173, though
students may have forgotten some
of it, especially details of notation. The exceptions are the sections on strings and graph
Before you start, introduce yourself. Promise office hours will be posted very soon and
encourage them to come.
1 Homework guidelines
• Put each problem on a different sheet of paper, we grade them separately.
• Put your name on each sheet of paper you submit.
• Put the section number on every sheet of paper you submit.
• Homeworks will usually be due Mondays at 4pm.
• The next homework is due next Tuesday.
Do not forget to register with the news server and start reading the news-
What are Z, N (no zero), N0, (mention quickly Q and IR).
What does it mean for x to divide q ? Namely, there exists integer n such that q = xn. As
such, every number n is divisible by 1 and n (i.e., itself).
An integer number is even if it can be divided by 2. A number which is not even, is odd.
Q: Is zero even ? Well, 0 = 2· 0 and as such, 0 is divisible by two.
Meaning of p = q mod k. Examples... (i.e., 121 = 73 mod 3).
4 is not rational
A number x is rational if it can be written as the ratio of two integers . The fraction
is irreducible if α and β do not have any common divisors (except 1, of course). Note
that a rational number has a unique way to be written in irreducible.
Lemma 4.1 An integer k is even if and only if k2 is even.
Proof: If k is even, then it can be written as k = 2u, where u is an integer. As such,
k2 = (2u)2 = 4u2is even, since it can be divided by 2. As for the other possibility, if
k = 2u + 1, then
is odd (since it is the sum of an even number and an odd number), implying the claim.
Theorem 4.2 The number is not rational (i.e., is an irrational number).
Proof: Assume for the sake of contradiction that is rational, and it can written as the
Let us square both size of this equation. We get that
That is the number 2 is a divisor of . Namely, is an even number. But then, α must
be an even number. So, let α= 2a. We have that
Namely, is even, which implies, again that is even. As such, let us write , where
b is an integer. We thus have that
Namely, we started from a rational number in irreducible form (i.e., ) and we reduced
it further to a/b. But this is impossible. A contradiction. Our assumption that is a
rational number is false. We conclude that is irrational.
5 Review of set theory
Sets, set building notation (just show an example), subset, proper subset, empty set, Venn
Tuples, cross product of two sets .
Sets of sets, power set , sets can contain a mixture of stuff like
Demorgan' s Laws
Cardinality of a set
strings, empty string, sets of strings
substring, prefix , suffix, string concatenation
What happens when you concatenate the empty string with another string?
Suppose w is a string. Is the empty string a substring of w? (Yes!)
7 Recursive definition
Recursive definition (concrete example).
Let U be the set that contains the point (0, 0). Also:
• if (x, y)∈ U, then (x + 1, y) ∈ U.
• if (x, y) ∈ U, then (x, y + 1) ∈ U
Q: What is U?
A: Clearly, (0, 1)∈ U, (0, 2) ∈ U,.... (0, k) ∈ U (for any k).
As such, (1, k) ∈ U (for any k)
As such, (2, k)∈ U (for any k)
As such, (j, k) ∈ U (for any j > 0, k > 0).
(A more complicated example of this is in the homework.)
8 Induction example
The following wasn't done in some (all?) of the sections, but you may still find it useful to
Consider a graph G = (V,E). The graph G is connected, if there is a path between any
two vertices of G. A graph is acyclic if does not contain any cycle in it. A leaf in G is a
node that has exactly one edge adjacent to it.
Lemma 8.1 A connected acyclic graph G over n > 1 vertices, must contain a leaf.
Proof: Indeed, start from a vertex v ∈ V (G), if it is a
leaf we are done, otherwise, there
must be an edge e = vu of G adjacent to v (since G is connected), and travel on this edge
to u. Mark the edge e as used. Repeat this process of \walking" in the graph till you reach
a leaf (and then you stop), where the walk can not use an edge that was used before.
If this walk process reached a leaf then we are done. The other possibility is that the
walk never ends. But then, we must visit some vertex we already visited a second time (since
the graph is finite). But that would imply that G contains a cycle. But that is impossible,
since G is acyclic (i.e., it does not contain cycles).
Claim 8.2 A connected acyclic graph G over n vertices has exactly n - 1 edges.
Proof: The proof is by induction on n.
The base of the induction is n = 2. Here we have two vertices, and since its connected,
this graph must have the edge connecting the two vertices, implying the claim.
As for n > 2, we know by the above lemma that G contains a leaf, and let w denote this
Consider the graph H formed by G by removing from it the vertex w and the single edge
e' attached to it. Clearly the graph H is connected and acyclic, and it has n - 1 vertices.
By the induction hypothesis, the graph H has n - 2 edges. But then, the graph G has all
the edges of H plus one (i.e., e'). Namely, G has (n - 2) + 1 = n - 1 edges, as claimed.