Algebraic Review
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
induction.
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-
groups !
2 Numbers
What are Z, N (no zero), N0, (mention quickly Q and IR).
3 Divisibility
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
irreducible ratio 
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
As such,
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
diagram
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
6 Strings
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).
Note that
(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
read.
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
leaf.
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.
| Prev | Next |