# CS40, Spring 2008, UC Santa Barbara Lecture Notes

Please read the important disclaimer at the bottom of this page. Also note that these notes may be migrated to a wiki or some other tool in the near future. If/when that happens, this page will forward you to the new location of this material.

## Notes

### Mon 03/31

Overview of what this class will cover.

Included overview of

• truth tables, ∧ (and), ∨ (or)
• sets, ∩ (union), ∪ (intersection)
• predicates with ∀ (for all) ∃ (there exists)
• brief introduction to graphs (structures with vertices and edges) such as airline route maps
• NP-completeness of the travelling salesperson problem
• unsolvability of the halting problem

We discussed how this class fits in to learning about programming and building systems (i.e. the reasons most folks become interested in CS and CE in the first place). We offered a koan to explain why proving theorems is valuable. (See the syllabus for a summary of this discussion under the heading "what this class is about").

### Wed 04/02

#### Discussion (11am)

Enroll yourself in this course on moodle.cs.ucsb.edu (I'll give you the key in class)

Logic:

• Propositions (p, q, r) vs. Predicates (P(x), R(x), S(x,y), etc.)
• Propositional Logic vs. Predicate Logic vs. Predicate Calculus

Practice with predicate logic

#### Lecture (2pm)

Enroll yourself in this course on moodle.cs.ucsb.edu (I'll give you the key in class)

• sections 1.1 through 1.3 for Wednesday
• sections 1.4 and 1.5 for Friday
• sections 1.6 and 1.7 for next Monday

Homework 1 : Due Monday 04/07 (hand in on paper, during class).

Note that the lecture material will NOT BE ENOUGH to answer these problems. You MUST read the chapter. If you are stuck on any problem:

• Look for an odd numbered problem near it that is similar.Try to work it first, then check your answers against those in the back of the book. Odd numbered problems have answers in the back of the book.)
• Bring questions to the discussion section on Wednesday
1. p. 28 #6 (10 pts)
2. p. 28 #8 (40 pts)
3. p. 28 #34 (30 pts) (Read the definition of dual that appears right before problem 34).
4. p. 60 #12 a, b, c, d (20 pts).

New material:

Proofs:

• Direct proof
• Proof of formula that sum of numbers 1 to n = n(n+1)/2
• Inductive proof
• Another proof of formula that sum of numbers 1 to n = n(n+1)/2
• proof that sum of rational number and irrational number is irrational

### Fri 04/04

Direct proof of part of Fundamental Theorem of Arithmetic (Rosen p. 285 for proof, Rosen p. 211 for statement of the theorem).

• Note that I may have misstated in class that this was a complete proof of the Fundamental Thm of Arithmetic.
• In fact, we only proved part of the Theorem. We proved that if n is an integer > 1, then n can be written as the product of primes.
• The Fundamental Thm of Arithmetic includes that statement but goes further.
• It also says that if n is not prime, the product is of two or more primes, where the factors are written in order of nondecreasing size.
• The proof of this other part (i.e. that the prime factorization is unique) is on p. 233 of Rosen.
• Also, see my notes on the Moodle about the problem of rigor related to the objections some students raised to the idea of the "product of 1 number".

Proof by contradiction that there are infinitely many primes (Rosen p. 212). Also see summary

### Mon 04/07

Proof by contradiction that √ 2 is irrational (see Rosen p. 80)

Modus Ponens, Modus Tollens, Universal Modus Ponens, Universal Modus Tollens (see summary)

### Wed 04/09 discussion

How to prove an "if and only if" (↔)

How to prove the equivalent of three statements (i), (ii), (iii)

### Wed 04/09 lecture

• 2.1, 2.2, 2.3 by Friday 04/11
• 2.4 by Monday 04/14
• 3.1, 3.2 3.3 by Wednesday 04/16
• 3.4, 3.5 by Friday 04/18
• 3.6 3.7 by Monday 04/21
• 3.8 by Wednesday 04/23

Homework 2 due Wednesday 04/16

1. p 85, #2 (20 pts)

2. p. 85 #4 (20 pts)

3. p. 85, #18 (20 pts)

4. p. 85, #28 (20 pts)

5. p. 86 #32 (20 pts)

#### Homework 3 due Monday 04/21

1. p. 119 #4, (10 pts)

2. p. 120, #28 (40 pts)

#### More on proofs by contradiction

How a proof by contradiction works (summary)

Review of two proofs by contradiction (summary)

### Fri 04/11 lecture

#### Some definitions related to set theory:

set: unordered collection of objects

defn of subset: A ⊆B ↔ ∀x(x ∈ A →x ∈ B)

Example:

• Let P is the set of all people who ever entered Phelps 1425.
• Let F be the set of all CS40 students in the room right now
• Then F ⊆ P because if you are a CS40 student in the room right now, you have entered Phelps 1425.

Is the empty set a subset of P? That is, is ∅⊆A?

• To answer this question, ask is it the case that ∀x(x ∈ ∅ →x ∈ B)
• Remember, a→b is false only when a is true and b is false
• Can a ever be true in this case?
• If not, then a→b can never be false!

So defn of subset: A ⊆B ↔ ∀x(x ∈ A →x ∈ B)

proper subset: A ⊂B ↔ ∀x(x ∈ A →x ∈ B) ∧ ∃x ( x ∈ B ∧ x ∉ A)

Is F ⊂ P? What would we have to do to find out?

Let C be the set of all computer science majors at UCSB.
Let F be the set of all CS40 students in the room right now.

• Is C ⊆ F? Why or why not?
• Is C ⊂ F? Why or why not?
• Is F ⊆ C? Why or why not?
• Is F ⊂ C? Why or why not?

So:

• defn of subset: A ⊆B ↔ ∀x(x ∈ A →x ∈ B)
• defn of proper subset: A ⊂B ↔ ∀x(x ∈ A →x ∈ B) ∧ ∃x ( x ∈ B ∧ x ∉ A)

Come up with similar definitions for:

• union, i.e. x ∈ A∪B ↔ what?
• intersection i.e x ∈ A∩B ↔ what?
• set difference i.e x ∈ A-B ↔ what?

#### The power set: ℘(A)

power set of A: the set of all subsets of A

• Let A be the set {Brian, Rodrigo}
• What are all the subsets of this set?
• How many are there?

The notation (A) is sometimes used to mean power set of A (a letter P in a fancy-schmancy script.).

Now let B be the set A ∪ {Sara}.

• Now what are the subsets of B?
• That is to say, what are the elements of (B)
• How many are there?

When A is a set, the notation |A| doesn't mean "absolute value of".

• Instead, it means "how many elements are in A".
• We call this the cardinality of A.

So, |A| is 2. If we let B be A ∪ {Sara}, then |B| is 3.

Suppose | S| = n

• Then what is |(S) |
• How would we prove that?

### Mon 04/14

There is more to learn about relations, and we'll talk about it in a later class. But first, I want to do something daring. I'm going to have the "audacity of hope":

• I'm going to expect you to read a section in the textbook.

In particular, I expect you to read section 8.1 (pp. 519-527) by Friday 04/25. This is only eight pages, but in this eight pages are several important concepts:

First some review:

• The definition of a binary relation (p. 519)
• The idea of a function a special case of a relation (p. 520)

Then some new material. It isnt hard stuff, as CS40 goes—it is probably some of the most straightforward material we'll cover. But it is important stuff. So here goes:

• Relations on a set (e.g. a relation that is a subset of A × A) (p. 521)
• Definition of a reflexive relation (p. 522)
• Definition of a symmetric relation and an antisymmetric relation (p. 523)
• Definition of a transitive relation (p. 524)
• Combining relations with set operations (∪, ∩, set difference (-), etc.) (p. 525)
• The composite of two relations, i.e.R S (p. 526)
• The powers of a relation, i.e. R, R2, R3, etc. (p. 526)
• Proof that R is transitive ↔ Rn ⊆ R for n = 1,2,3,… (p. 527)

So, read this on your own, and be prepared for discussion questions, (or even a pop quiz!) any time from Friday 04/25 onward.

#### Skipping ahead in the book? Are you trying to make us fail?

Relax. As far as I can tell, there is only one thing in Section 8.1 that depends on anything we haven't already covered in class. And that thing is easy, and we are going to talk about it now. It is the idea of a divides b, or in notation, a | b

#### The divides operation (a | b)

(Reference: p. 201, Section 3.4)

When a and b are integers, with a≠0, the notation (a | b) means that a divides b, that is:

• There exists an integer c such that b = ac

More informally, (a | b) means that a "guzinta" b with a remainder of zero.

• You remember "guzinta" from 3rd or 4th grade math, yes?
• 5 guzinta 30 six times, remainder 0, thus (5 | 30) is true
• 7 guzinta 63 nine time, remainder 0, thus (7 | 63) is true
• But, 8 guzina 41 five times, remainder 1, thus (8 | 41) is false.
• We can write (if the browser supports the unicode character properly): 8 ∤ 41
• That should look like (8 | 41) with a slash (/) through the | character.

#### Now, we are ready for number theory!

(Note: credit to Tom Leighton, Ronitt Rubinfeld and others who have worked on the notes for MITs course "Mathematics for Computer Science, 6.042, which is the source for a lot of what follows below.)

Number theory is the study of the integers.

You might wonder:

• "What's so interesting about the integers?"
• "Doesn't math become easy when we don't have to worry about nasty numbers like √7, 1/π, and i"?
• "We don't even have to worry about fractions!"

Well, as it turns out number theory gives us the ability to share email messages securely (via cryptography), and can help Bruce Willis and Samuel L. Jackson avoid blowing up a nice park in New York, with a cute little elephant fountain! It squirts water out of its trunk!

(Oh, and also avoid getting killed themselves...)

... to be continued...

### Wed 04/16 lecture

We'll come back to Bruce and Samuel L. on Friday with more number theory. For today, I want to return to set theory (along with relations and functions). Remember, read Section 8.1!

### More terminology from set theory

ordered pair: (a,b)

• You've seen this before: points in plane for example

An ordered pair is a special case of an ordered n-tuple (a1, a2, a3, a4,... an)

tuples come up a lot in computer science

• databases
• a row in a database is a n-tuple where n is the number of columns
• networks
• a TCP connection is a 4-tuple of (srcIp,srcPort,destIp,destPort)
• compilers
• the abstract syntax tree is turned into tuples that are then converted into either bytecodes (as in Java), or machine language instructions (as in C, C++)

cartesian product: A × B = {(a,b) | a∈ A ∧ b ∈ B }

So, Let A = {Bryce, David}. Let B = {Michael, Ryan, Fey}

• List the elements of the set A × B?
• What is | A × B |?
• Is Bryce an element of the set A × B?

#### Even more terminology: relations and functions

Defiinition of binary relation (p. 519, Chapter 8)

• Let A and B be sets.
• A binary relation R from A to B is a subset of A × B.
• For example, if R = { (Bryce, Michael), (Bryce, Ryan), (David, Fey) } then R is a relation from A to B.
• We can write a R b to show that (a,b) ∈ R.
• It is called a binary relation because there are exactly two sets involved, A and B.
• Later (much later!) we might talk about n-ary relations where we look at subsets of A1 × A2 × .. × An
• But don't worry about that for now!

We can define a relation in math to model something about the real world.For example, all of the following might be relations from A to B with the definitions of A and B given above:

• Let T = {(a,b) ∈ A × B | A is taller than B }
• Let C = {(a,b) ∈ A × B | A is from the same county as B }
• Let D = {(a,b) ∈ A × B | A lives in the same dorm as B }
• Let V = {(a,b) ∈ A × B | A's name comes before B's name in the alphabet}

We can also relate a set to itself. For example, we could write similar relations as

• relations on S, that is, subsets of S × S,
• where S is the set of all students in the room right now.

Here are some relations "on S":

• Let T = {(a,b) ∈ S × S | A is taller than B }
• Let C = {(a,b) ∈ S × S | A is from the same county as B }
• Let D = {(a,b) ∈ S× S | A lives in the same dorm as B }
• Let V = {(a,b) ∈ S× S | A's name comes before B's name in the alphabet}

So we could ask questions like:

• Is (Don, David) in T?
• Is (Jimmy, Amos) in C?
• Is (Fey, Fey) in C?
• Is (Michael, Ryan) in D?
• Is (Bryce, Andre) in V?

#### Those old familiar ordered pairs...

Remember those old familiar ordered pairs from the Cartesian plane?

What set do those ordered pairs come from?

• I'll say it in class, but...
• I'm not going to put it in the online notes because I want to see if you can come up with it ...
• but it might be on the exam, so write it down!
• If you missed class, get the notes from someone!

#### Sets raised to powers

• The set A × A can also be written as A2
• The set A × A × A is written as A, and so forth.
• This makes sense:
• "raised to the power" means "repeated multiplication"
• cartesian product ( × )is the kind of multiplication we do on sets

Questions: Suppose is the set of all real numbers (a fancy script R)

• So what does familiar notion from high school algebra does 2 refer to?

These two sets are sometimes called "two space" and "three space".

### Fri 04/18/08

MIDTERM EXAM: Friday 05/02/2008

#### Coverage: chapters 1, 2, 3, 4.1, 4.2, section 8.1, plus notes from class

• Might specify more details later, but for now, that's what to study.
• Read 4.1, 4.2 for 4/25 (in addition to 8.1). They are mostly review.

#### More on Number Theory

• Again, why? Cryptography is the main reason
• But there are water jugs too...
• Mainly: wax on, wax off. It will make you stronger

Homework 4 (for Wednesday 04/23/08):

Be prepared to do a 10 minute presentation on one of the following two topics:

• diffie hellman key exchange
• chinese remainder theorem

You may use the blackboard, or powerpoint or a webpage. But one way or the other, be prepared to turn in something that shows you are preparted to present: either notes on paper, or your powerpoint file or your webpage.

You may work alone, or in pairs (your choice).

From among those that want a chance to present, we'll choose (at random) one person (or team) to present the diffie-hellman exchange, and another to present the chinese remainder theorem. Those persons have the opportunity to earn up to 100 points of extra credit (depending on the quality of the presentation).

### Mon 04/21/08

#### Functions

A function is a particular kind of relation. A relation is a function if and only if, for each element of A, it is related to exactly one element of B.

So, if S is all students in the room, and C is the set {Freshman, Sophomore, Junior, Senior, Other}, then we can define F as a relation from S to C.

F is a function because it is the case that every student is at least one of these things (Freshman, Sophomore, Junior, Senior, Other) and no student is more than one of these. That is, every student can be related to one and only one of these categories.

Formally, the definition of a funciton (p. 133) goes like this:

• A function from A to B is an assignment of exactly one element of B to each element of A.
• We write f(a) = b if b is the unique element of B assigned by the function f to the element a of A.
• If f is a function from A to B, we write f : A → B

So, every function is a relation, but not every relation is a function. For each of these, is it a function? Explain:

• Let T = {(a,b) ∈ S × S | A is taller than B }
• Let C = {(a,b) ∈ S × S | A is from the same county as B }
• Let D = {(a,b) ∈ S× S | A lives in the same dorm as B }
• Let V = {(a,b) ∈ S× S | A's name comes before B's name in the alphabet}

Let age = {(a,b) ∈ S× Z+ | b is how old student a is}

Here are the rules for a function again:

• a function from A to B assigns every element of A to exactly one element of B
• no element of A can be left out
• no element of A can be assigned to more than one element of B
• it is ok if some elements of B are left out, or some elements of B get mapped to more than once.

This illustration shows six possible relations from A to B. Which of them are functions? Onto and One to One:

So, functions are a restricted form of relations. We can get even more restrictive and talk about special kinds of functions.

The following web page has nice pictures of what it means for a function to be one-to-one or onto:

http://www.regentsprep.org/Regents/math/algtrig/ATP5/OntoFunctions.htm

And your book has nice explanations on pages 136 to 139. So read that, and then see if you can answer these questions:  #### Back to number theory:

We started out to prove last time that if we start with two empty jugs, a and b, where the operations are that we can:

• fill a jug,
• empty a jug, or
• pour water from one jug into another, until that jug is full

that the amount of water in each jug is always a linear combination of a and b.

We got sidetracked, because we wanted to prove this by induction, and we ended up reviewing how a proof by induction works. In particular, for this proof by induction, we show:

P(0), and P(n)→P(n+1)

How does that show that ∀n>=0, P(n)?

It turns out there is a proof by contradiction that this holds. That got us into a discussion of proof by contradiction where you are trying to prove a statement of the form pq by contradiction.

We used logic ( a truth table, in fact) to show that: ¬(pq)≡(p∧¬q)

So, in a proof by contradiction you always start out by assuming that what you are trying to prove is false, and then reasoning from that to a contradiction.

So, suppose if you want to prove that proof by induction is valid, that is you want to prove that:

(P(0) ∧ P(n)→P(n+1)) ⇒ (∀k>=0, P(k))

You would do it by assuming that this is false, i.e.

¬( (P(0) ∧ P(n)→P(n+1)) ⇒ (∀k>=0, P(k)) )

Which is equivalent to writing:

( (P(0) ∧ P(n)→P(n+1)) ∧ ¬ (∀k>=0, P(k)) )

Which, by applying one of Demorgan's laws for the ∀ and ∃ notation, leads us to this:

( (P(0) ∧ P(n)→P(n+1)) ∧(∃k>=0,¬ P(k)) )

If you start from there, you can find a contradiction, thus proving that proof by induction is valid! (Well, at least it proves it for the case of a base case of 0, and showing a proposition is true for all integers >=0. Try it, as an exercise.)

But, that's not what we were setting out to do—that was just a reminder about proof by induction, and proof by contradition. So lets return to what we were trying to prove!

#### Start again... a proof about filling jugs, and linear combinations.

We started out to prove last time that if we start with two empty jugs, a and b, where the operations are that we can:

• fill a jug,
• empty a jug, or
• pour water from one jug into another, until that jug is full

that the amount of water in each jug is always a linear combination of a and b.

We will use a proof by induction, where P(n) is the proposition that after n steps, the amount of water in each jug is a linear combination of a and b, i.e.

j1= s1a + t1b

j2= s2a + t2b

We need to show that P(0), and P(n)→P(n+1)

We'll do this on the board in class...

### Wed 04/23/08

Homework 5 (for Monday 04/28/08)

(1) (10 pts) p. 260, problem 24. Show your work. You may write a program to do it if you like, or do it by hand. If you use a program, include your source code.

(2) p,. 244, # 2, (a, b, c, d) (10 pts each).

Presentations on Chinese Remainder Theorem, and Diffie Helman Key Exchange

But first, reminders of some definitions:

#### Division Algorithm, or Division Theorem (it isn't really an algorithm) (p. 202)

Let a be an integer, and d be a positive integer.
Then there are unique integers q and r, with 0 ≤ r < d, such that a = dq + r

Definitions of div and mod (needed to understand Diffie-Helman and the Chinese Remainder Theorem)

In a = dq + r, we have:

• the divisor d
• the dividend a
• the quotient q
• the remainder r

Here's a picture: We'll also need to understand modular arithmetic (p. 203).

#### Defn. of congruent modulo m:

If a and b are integers, and m is a positive integer,

• then a is congruent to b modulo m if m divides a-b
• we write: ab (mod m)

#### Theorem 3 from p. 203 (shows another way to define modulo)

Let a and b be integers and let m be a positive integer.

• then ab (mod m) ⇔ a mod m = b mod m

(In my opinion the second definition is easier to understand.)

So, we have 16 ≡ 21 (mod 5) because 16 mod 5 = 21 mod 5 = 1

And 5 ≡ 29 (mod 3) because 5 mod 3 = 2, and 29 mod 3 = 2.

With that, we should be able to understand the Chinese Remainder Theorem.

We may need a bit more to understand Diffie Helman

In mathematics, the integers a and b are said to be coprime or relatively prime if they have no common factor other than 1 or, equivalently, if their greatest common divisor is 1.

For example, 27 and 25 are relatively prime, even though neither is a prime number.

• They are relatively prime because their gcd is 1.
• Equivalently, their prime factorizations, 3⋅7 and 5⋅5 are disjoint

a primitive root modulo n is any number g with the property that any number coprime to n is congruent to a power of g (mod n).

That is, if g is a primitive root (mod n) and gcd(a, n) = 1, then there is an integer k such that gka (mod n). k is called the index of a.

That is:

• suppose g is a primitive root mod n, say 14
• Then, pick any integer a that is relatively prime to n, say, 11.
• Now, take g to every integer power, i.e. g, g2, g3, g4, etc. Eventually gk will be ≡ a (mod n)

Also, since a is any integer that is coprime with 14, that means that in the sequence g, g2, g3, etc..we must eventually encounter all of the numbers that are relatively prime with 14, mod 14. I.e. we must generate all of the numbers 1, 3, 5, 9, 11 and 13, in some order.

#### Let's see an example of primitive roots mod n

Take n = 14. Then all the numbers between 1 and 14 that are relatively prime with 14 are 1, 3, 5, 9, 11 and 13. We can see if any of these are primitive roots.

Let us list them all, with their powers, mod 14. In this table, the numbers i={1,3,5,9,11,13} are numbers that are "candidates" to be primitive roots modulo n. We are looking to see if any of them satisify the property. Note what happens with 3 and 5...

i: i, i2, i3, ... (mod 14)
1 : 1, 1, 1, 1, 1, ....
3 : 3, 9, 13, 11, 5, 1, 3, 9, 13, 11, 5, 1, ...
5 : 5, 11, 13, 9, 3, 1, 5, 11, 13, 9, 3, 1,
9 : 9, 11, 1, 9, 11, 1, 9, 11, 1, ...
11 : 11, 9, 1, 11, 9, 1, ...
13 : 13, 1, 13, 1, 13, 1, ...

See this Excel Spreadsheet for details

We see that for 3 and 5, if we take successive powers of 3 (or 5) mod 14, eventually we "generate" all of the numbers that are relatively prime to 14. That is pretty cool! So, we can say that 3 and 5 are primitive roots modulo 14, because successive powers geneerate all of the numbers modulo 14 that are relatively prime to 14.

Why is this important? Well, it comes up in Diffie Helman.

### Fri 04/25/08

We had a quiz on relations being reflexive, symmetric, antisymmetric, and transitive.

We went over the quiz, and then briefly discussed big-O (section 3.1-3.3 in your textbook).

### Mon 05/28/08

Announcement:

• You may bring 1 4x6 index card of notes (or 3x5 if you are really confident or write small) to the exam.
• I will collect these, and might not give them back, so make a photocopy if you want yours to have for the final

#### Reading assignment: for Wednesday 05/07 (goes along with Homework below)

• (Optional) skim 8.2 if you like. It is tempting to cover it because it is very "applied", i.e. it relates directly to how SQL databases work, but we have a whole course on that (CS174A), so for sake of time, we'll have to skip it.

• The matrix representation of relations is good background for topics in CS130A, including how graphs are represented using adjacency matrices.
• Understand how to tell whether a relation is reflexive, symmetric or antisymmetric just by looking at the matrix representation.
• Transitive closure is an important concept with many practical applications:
• reachability in a routing protocol (if, for instance, you work for Cisco Systems designing routing software.)
• all the people connected to someone in a social network like Facebook or LinkedIn
• Be able to find the reflexive and symmetric closures of a relation
• Be able to explain why reflexive and symmetric closure are easy, but transitive closure is more complicated (why the simple thing you do for reflexive and symmetric closure breaks down).
• equivalence relations, equivalence classes, and the idea of partitioning a set are important concepts that come up in many fields of math and computer science, including compilers, security, and networks (e.g. in routing protocol design)
• Be abe to give the definition of an equivalence class (the mnemonic RST may help)
• Be able to show whether a given relation is an equivalence relation
• Be able to explain the notation ab
• Be able to explain what a partition of a set is, and how an equivalence relation leads to the partition of a set

#### Homework 6 (for Wed 05/07/2008) (100 pts) Homework 7 (for Wed 05/14/2008) (100 pts)

1. p. 543, #8. Number your answer (a),(b),(c), and for each list whether the matrix in question is reflexive, irreflexive, symettric, antisymmetric, and/or transitive. (2 points for each correct answer, for a total of 30 points)
2. p. 542, #22 (15 pts). (-2 for each missing edge and/or mistaken edge).
3. p. 553, #2 (10 pts)
4. p. 554, #20 (15 pts, 5 pts each for a,b,c)
5. p. 554, # 24 ( 10 pts)
6. (20 pts) Are each of the following equivalence relations on the set "students in CS40 this quarter"? In each case, give a brief explanation of your answer.
1. is older then?
2. was born in the same year as?
3. is taller than?
4. is a member (or pledge) of the same fraternity/sorority as?

• 8.6, partial orders, aka posets,
• Relations that are RAT, not RST (reflexive, antisymettric and transitive)
• partial orders vs. total orders
• minimal, maximal, minimum, maximum, upper bound, lower bound, least upper bound, greatest lower bound
• You may skip the section on lattices
• But don't skip the section on topological sort—topological sort is the main real world applicaiton of partial orders!
• I'll tell you about where topological sort arises in the design of spreadsheets like MS Excel.
• See if you can guess..
• 9.1, introduction to graphs
• Graphs are one of the most useful data structures in computer science
• After you read this section, be able to explain some real world applications of graphs, and what the vertices and edges represent
• They also provide us with a way to tie cartesian product and relations to all of these real world applications. Consider:
• If the set V is the set of all vertices, then what is the set V × V?
• How does that relate to the concept of an edge?
• How does that relate to the concept of a relation?

• 9.2
• Know what a cycle in a graph is, and what a complete graph is (I don't care so much about "wheels")
• Know what the n-dimensional hypercube is
• Know how to tell whether a graph is bipartite, and what this has to do with coloring
• Know what a subgraph and a proper subgraph are
• 9.3
• Know how to represent a graph as an adjacency list and as an adjacency matrix
• Know what it means for two graphs to be isomorphic
• this term isomorphic is a very important one to know, because it arises not only in graphs, but in other topics as well.
• 9.4
• Know the terms connected for undirected graphs, and strongly vs weakly connected for directed graphs
• Know what connected components are
• Is Facebook a directed or undirected graph?
• What are the connected components of the Facebook graph?
• Read especially, Example 11 on p. 627 about the Strongly connected components of the Web Graph
• Also know:
• what a path is
• what a simple path is, and the distinction between a path and a simple path
• what a circuit is and the distinction between a path and a circuit
• what a simple circuit is, and the distinction between a simple circuit and a regular circuit
• Be able to draw a Venn diagram illustrating the relationships between paths, simple paths, circuits, and simple circuits, explaining what features characterize the paths in each part of the diagram.
• 9.5
• Know what an Euler path and circuit are
• Know what a Hamilton path and circuit are
• Be able to explain the difference (edges, vs. vertices)
• Are the necessary and sufficient conditions for an Euler path known by mathematicians? If so, what are they?
• 9.6
• Skim the section on Dijkstra's algorithm.. you'll see this in 130A, so we don't need to cover it here
• But do read the section on the Travelling Salesperson problem.
• This is an example of a particular kind of important problem in computer science
• I want to be sure you know about that.
• So, I'll ask you about it on the final exam to be sure that you know it.
• So, read, and find out what this is
• Refer back also to p. 197.

For Wednesday 05/14, read: 5.1 through 5.3

• 5.1: Know the principle of inclusion/exclusion
• 5.2: Know the pigeonhole principle
• 5.3: Permutations and Combinations
• Know what a permutation is, and the number of permutations of r elements from a set with n elements.
• 5.4: Know what a combination is, and the definition of C(n, r), also called n choose r, or  ( n ) r
which is also known as a binomial coefficient.

#### A bit more about Big-O from Sections 3.2

• First, section 3.1 and 3.3 will not be on the midterm exam.
• Most of 3.1 repeats material you already covered, or will cover, in CS10/CS20/CS130A
• One exception: I'll come back later and cover the Halting Problem, but that will not be on this exam
• We'll also cover section 3.3 sometime before the final
• Section 3.2 WILL be on the exam, except for big Omega and big Theta, which will be on the final.
• Big Omega and Big Theta are specifically listed as pre-requisistes for CS130A, so we MUST cover them.
• We'll do some sample problems for practice in recitation this week (since there isn't time for a homework assignment).
• Camilla will give you the answer key afterwards
• You can then ask questions on Wednesday if there is any part you don't understand.
• You can also practice with the odd numbered problems from p. 191
• Here is a review of Section 3.2

f(x) is O(g(x) if ∃ Ck where |f(x)| ≤ C|g(x)| What is the point of this?

• The point of big O notation is to look at what happens as the function grows.
• We care about that because it tells us how an algorithm will scale as the input size gets large

In general: It is helpful to memorize some relationships that come up a lot, as shown in this figure from the textbook: #### Review: some sample exam questions

Note that these links may not work later: they link to an experimental system for generating quiz/exam questions that may or may not be up when you try them. No guarantees. Also note that every time you refresh the page, you get a different question.

These don't by any means cover all the kinds of problems you could expect to get on the exam... but you can be sure that you'll get some of each of these!

#### Review: An example of one-to-one and onto: perm numbers

Consider the function p(s) : S {0, 1, 2, ... 9999999 } where:

• S is the set of all UCSB students, and
• p(s) maps a particular student to his/her "perm number"

Some questions:

• What would it mean if p were one-to-one?
• Is p one-to-one?
• What would it mean if p were onto?
• Is p onto?

#### Another example (we'll probably not have time to cover this in class, so work through this on your own. Bring questions to the discussion section or to class on Wednesday)

Let S = {Lopes,Landreaux,Baker,Garvey,Cey,Guerrero,Scioscia,Russell,Valenzuela}, that is, the starting lineup for the LA Dodgers opening game in 1981.

Let W = {P,C,1B,2B,3B,SS,LF,CF,RF}, the list of defensive positions in baseball.

Then let f be a relation from S to W as follows:

• f = {(s,w) ∈ S × W | player s started at position W}

For example, (Valenzuela, P) is an element of f, because Fernando Valenzuela was the starting pitcher for the 1981 opening game.

Questions:

• Is f a function?
• If so,
• is f one-to-one?
• is f onto?

Suppose we constructed a relation g from W to S as follows:

• g(p) is the last name of the LA Dodger that played position p in this game. For example, g(C) = Scioscia, because Mike Scioscia was the starting catcher.

Questions:

• Is g a function? Explain.
• If so,
• is g one-to-one? Explain.
• is g onto? Explain.

#### Terminology: Injection, Surjection, Bijection, 1-to-1 correspondence

• A function that is one-to-one is called an injection
• A function that is onto is called a surjection
• A function that is both 1-to-1 and onto is a bijection
• This is also called a 1-to-1 correspondence.

The 1-to-1 correspondence terminology is important, because a 1-to-1 correspondence with the positive integers is often used to help us count things.

For example, can we count all the possible programs that someone can write in Java? It turns out that we can, because we can put them in a 1-to-1 correspondence with the positive integers.

There is an infinite number of such programs, but we can count them—that is, for any Java program you write, we can find exactly where it fits in the list of all such programs. We can say: ah, that's program number 1,729,491,213. (It reminds me a lot of program number 1,323, except it is longer.) It might take us a long time to figure out which one it is, but we can do it—and if we know the length of the program, we can probably even estimate how long it will take to find that programs number in the list.

If as set has infinitely many things it, but the things can be all given specific numbers in a list, we call this a countably infinite set. (p. 158)

The set of all Java programs is countably infinite. The same is true of all the rational numbers (p. 159)

We'll see though, that there are some things we can't count. We can't count all the real numbers, or all the elements of (Z), for example. These are uncountably infinite sets. We'll prove this in a later class. (If you just can't wait, then read p. 160. Better yet, read it anyway. If you've been keeping up with the reading, you already have.)

Inverse functions

When a function is a 1-to-1 correspondence (i.e. it is a bijection), then can consider the inverse of a function.

• When f : A → B, and f is a bijection, then f-1:  B→ A, where f(a) = bf-1(b) = a
• Why is it necessary for f  to be both one-to-one and onto for f-1 to be a function? Explain.

To get from the reading: definitions of domain, codomain, image, preimage, composition (p. 134-141)

(possibly on a quiz on Friday, along with material from section 8.1, and definitions of function, 1-to-1, onto).

More stuff to get from the reading (p. 111 thru 128) (could be on the quiz too... or the midterm exam...)

universal set , venn diagrams, disjoint, complement of a set ( ), Demorgan's laws for sets (complement of union and intersection), generalized union and intersection

Midterm Exam 1

### Mon 05/05

Happy Cinco de Mayo.

New Plan:

• What was Homework 6 is now Homework 7 and is pushed back a week to Wednesday 05/14
• We clearly need more work on proof by induction.
• So, Homework 6 is now all induction all the time, and is due Friday 05/09.
• I'll return these on Monday 05/12 (provided you turn them in, in class Friday),
• We'll discuss them in class on Monday
• Next week in Discussion section, there will be an optional quiz on induction, worth 20 points.
• If you are happy with your score on question 2 on the exam, you don't need to come
• If you are unhappy with your score, you have an opportunity to raise your score.
• If you do better on the quiz than you did on question 2 on the exam, the new score can replace your old score.

Start Today! Come to office hours Wednesday if you need help!

Homework 6: Due 05/09/2008 (100 pts)

1. (20 pts) p. 279, #4 (Grading: parts a-d, f, 3 pts each, part e 5 pts).
2. (10 pts) p. 280 #6
3. (5 pts) p. 280 #10a
4. (10 pts) p. 280 #10b
5. (10 pts) p. 280 #16
6. (10 pts) p. 280 #32
7. (25 pts) p. 291 #4
(Hint: read example 4 on p. 287 first, then complete p. 291 #3 for practice first, and consult the answer in the back of the book if you need help.)
8. (10 pts) p. 292 #12

In class, I first went through the answer to question 2 from Midterm Exam 1, which is also covered on p. 267 of textbook (as Example 1.)

We then split into pairs and worked problems on the board:

• I wrote the problems on the board
• The students paired off and tried to solve them.
• Once a pair was finished, they visited other pairs to look at their proofs
• Finally, when there was 10 minutes left, we went over all of the proofs for the entire class.

The problems we worked were these. (Answers are in the book for each of these—either directly on the page given in the case of examples, or in the back of the book for odd numbered problems.)

1. Example 2 from p. 268. Show that the sum of the first n positive odd integers is n2
2. Example 3 from p. 269. Show that the sum of 2i from i=0 to n is (2n+1-1)
3. p. 279 #3. Let P(n) be the statement than 12 + 22 + ... + n2 = n(n+1)(2n+1)/6. Use induction to thos that this is true for all positive integers n≥1
4. p. 280 #5. Prove that 12 + 32 + ... + (2n+1)2 = n(2n+1)(2n+3)/3 whenver n is a non-negative integer.
5. p. 280 #15. Prove that 1⋅2 + 2⋅3 + … + n(n+1) = n(n+1)(n+2)/3 for every positive integer n
6. p. 280 #31. Prove that 2 divides n2 + n whenever n is a positive integer.

### Discussion Wed 05/07

Background for Transitive Closure

Also, you'll get your Exam 1 back.

### Wed 05/07

We started the process of proving the R* is the transitive closure of R.

We first reviewed the definitions of symmetric closure and reflexive closure, and discussed how the definition of transitive closure follows in a similar fashion.

We then reviewed from discussion the definitions of S ◦ R, Rn, and R* (see Discussion Notes from 05/07 for details).

We discussed the connection beteween the idea of a binary relation on a set, and the idea of a directed graph, that is that the set of edges in a graph E can be considered a binary relation on V, the set of vertices, i.e. E ⊆ V × V

We reviwed the definition of a path, from s to t in a directed graph G (p. 546)

We then said that in order to prove that R* is the transitive closure of R, we would need three other theorems. In each of these theorems, let R be a binary relation on A.

• Thm 1 from section 8.1, p. 527
• (R is transitive) ⇔ (Rn⊆ R, for n ≥ 1)
• Thm 1 from p. 547 about Paths
• Consider the graph corresponding to R.
• There is a path from a to b of length n, n≥1 ⇔ (a,b) ∈ Rn
• A Lemma left as an exercise to the reader (solution is not in the book)
• R is transitive → Rn is transitive

With those three in place, we can show that R* is the transitive closure of A
(Theorem 2 on p. 548).

So, we proceeded with the first half of proving Thm 1 from section 8.1, p. 527, i.e. the ⇐ part, that:
Assume (Rn⊆ R, for n ≥ 1) , show R is transitive.

### Fri 05/09

We continued with the ⇒ part of Thm 1 from section 8.1, p. 527, which is a proof by induction.

We then continued with Thm 1 from p. 547 about Paths. This is interesting because it is an "if and only if" inside a proof by induction.

We might then have also proved:

• R is transitive → Rn is transitive

(I forget if we did that on Friday, or left that to Monday 5/12)

### Mon 05/12

I handed back the graded Homework 6, and we talked about a few things to watch out for when doing inductive proofs:

• Don't fudge or skip steps in the algebra. Yes, you know where you are starting from and where you want to end up, but if you leave out the middle, the proof is not complete.
• Don't write down the thing you are trying to prove as an equality until you have proven it, unless you write words like "we want to show" in front of that equality.
• Be sure that all the steps in your argument are clear.

We then continued with a review of where we've been so far in the proof of R* as the transitive closure.
(Thm 2 on p. 548)

If we didn't prove R is transitive → Rn is transitive last Friday, we did it here. (Note, that this proof isn't in the book. If you didn't get it in the notes, then you need to come up with it on your own, or come see my during office hours to get it. It would make a super exam question.)

We then started the main event, i.e. the R is the transitive closure of R.

We started by stating what we needed to prove, namely that:

1. R ⊆ R*
2. R* is transitive
3. R* is contained in every transitive relation containing R
(i.e. R* is the smallest possible relation satisfying 1 and 2).

We proved 1 and 2, and left 3 for Wednesday.

### Wed 05/14

Today, we show the last part of Thm 2 from p. 548, namely
that R* is contained in every transitive relation containing R.

Formally, we show that when we have a relation S such that:

• S contains R, and
• S is transitive

Then S must contain R*

In notation: R ⊆ S ∧ (S is transitive) ⇒ (R* ⊆ S)

Proof:

We know by our previous lemma that is S is transitive, Sn is also transitive.

Also, we know that since S is transitive, Sn ⊆ S for n ≥ 1

That means that S* must be a subset of S, because every part of S* is in S.

We also know that R ⊆ S. So think about the graph representation of R and of S.

Since R ⊆ S if there is a path from a to b in the graph representation of R,
there must be a path from a to b in the graph representation of S.

That is, any path in R is also a path in S.

Thus, R*, the set of all paths in R is a subset of S*, the set of all paths in S.

So, we have R* ⊆ S* and S* ⊆ S. Therefore R* ⊆ S. (Q.E.D.).

#### New Topic: Equivalence Relations and Partial Orders

Equivalence relations: reflexive, symmetric, transitive (e.g. equals, "congruent mod 2")

Partial Orders: reflexive, antisymmetric, transitive (e.g. "less then or equal to" on Z, "divides" on Z)

• allow you to construct a directed acyclic graph (DAG)
• leads to topological sort (e.g. for project planning, PERT charts, identification of critical path)

#### Friday 05/16

Extra Credit presentations:

1. Choose one or more topics from the list below
2. Email me your topics in order of preference. Include as many as you like in your list. The more you include, the greater chance of getting a topic.
3. I'll email you back and let you know which topic you got
4. Prepare a 10-15 minute presentation on that topic within one week of receiving the email with your topic assignment.
• (similar to the ones done by Bryan/Rodrigo on Diffie-Helman, and by Fey on Chinese Remainder Thm.)
• email me your presentation notes or Powerpoint when you are ready to go, and I'll let you know when your presentation is scheduled
5. First come, first served.
6. Latest time/day to notify me of your topic preference (by email) is 5pm Monday.
7. Folks who already did a presentation are not eligible unless/until everyone who didn't do yet one gets a chance
8. If you do not respond with your notes or Powerpoint within a week, you forfeit the right the extra credit. No exceptions, no extensions.
9. The maximum credit is 100 points, applied to your quiz/homework component of the grade. No extra credit will be applied to the exam component. Actual points will depend on the quality of the presentation. For 90-100 points, I expect an "A" quality presentation, 80-90, "B" quality, etc.
10. You may work alone, or in pairs.

Topics:

• Monty Hall probability problem (taken: Andre)
• Birthday Problem (taken: Jimmy F.)
• PERT (Program Review and Evaluation Technique) and the connection to Topological Sorting (taken: Bryce)
• Bayesian Spam Filters (taken: James Marshall)
• Strassen's Algorithm for Matrix Multiplication (David)
• Lattices, and the Lattice Model of Information Flow (for government security clearances) (taken: Paul)
• Spanning Trees (and application to Computer Networks) (taken: Rodrigo)
• Finite State Machines (as application of graphs, and for language recognition, i.e. part of a compiler and/or applications in computer engineering) (taken: Bryan)
• Halting Problem (taken: Ryan)
• Mersenne Primes
• Euler's Theorem (taken: Michael Reynozo)
• Fermat's Theorem
• Kurt Gödel's "incompleteness Theorems", and Gödel Numbers

• most all of Chapter 8
• in Chapter 9, sections 9.1 through 9.6
• in Chapter 5, 5.1 through 5.3

• For Monday 05/19: 5.4, 5.5, 6.1
• For Wednesday 05/21: 6.2, 6.3, 6.4
• For Friday 05/23: 7.1, 7.2
• For Monday: 05/26: 7.3
• For Wednesday: 05/28: Re-read 3.1, 3.2 with special focus on:
• the Halting Problem (near the end of the section)
• Big Omega, and Big Theta (near the end of the section)

#### Homework 8: Due Wed 05/21

When the section and page number are not specified, they are the same as the previous problem(s)

1. section 5.1, p. 344, # 8 (10 pts)
2. #12, (10 pts)
3. #14 (10 pts)
4. section 5.1, p. 345 # 24 (10 pts)
5. #34 (10 pts)
6. section 5.1 p. 346 #62, a, b c and d (20 pts)
7. section 5.2, p. 360 #2 (10 pts)
8. section 5.2 p. 361 #8 (10 pts)
9. #14 (10 pts)

• #### directed vs. undirected

• degree, in-degree, out-degree
• edge weights
• cyclic, acyclic
• free trees, rooted trees
• simple graph, multi-graph
• connected graphs, connected components
• cycles, Cn
• complete graphs, Kn
• bipartite (two coloring)
• planar graphs  Hypercubes: ### #### Complete bipartite graphs: ### Applications:

Bipartite Graphs can be used to represent job assignments. The lines represent what jobs an employee has the skills to do, and the red lines show one possible assigment of the jobs.

Job assignment is related to the problem of finding a "maximal matching" in a graph like this one... Other applications are networks (for routing) and parallel computing, where the graph represents which processors can directly communicate.

You can have an array of vertex object, where each vertex object has a pointer to a linked list of adjacent vertices: Vertex Adjacent Vertices
a b,c,e
b a
c a,d,e
d c,e
e a,c,d

Or you can have a matrix where there is a 1 when the vertices are adjacent, and a 0 when they are not: a b c d e
a 0 1 1 0 1
b 1 0 0 0 0
c 1 0 0 1 1
d 0 0 1 0 1
e 1 0 1 1 0

If the graph is sparse, an adjacency list is often more efficient. It is O(|V|+|E|) in terms of space.

If the graph is dense, an adjacency matrix may be more convenient. It is O(|V|2) in terms of space.

Consider the speed of operations though.

• How quickly can we tell if (a,b) is in the graph in an adjacency list? In an adjacency matrix?

Isomorphic Graphs

Are these two graphs the same or different (other than the labelling of the edges)? If the graph is representing friend relationships, does it matter how I draw the graph?

How could we make a definition that says that two graphs really "represent" the same thing?

Two graphs represent the same thing, if and only if... what?  According to our textbook:

• The best known algorithms for solving this problem are still exponential time worst-case time complexity in the number of vertices in the graph.
• However, there are algorithms where the average case time complexity is O(n).
• It is hoped that a polynomial worst-case time algorithm can still be found. This is thus an open problem. Maybe one of you will solve it some day!

### Friday May 23

So today, we concentrated on the definition of Conditional Probability, and on applications of Bayes Theorem. You'll need this material for discussion next week, and for the final exam.

The book's presentation is not as clear as we might hope for. Camilla and I went through it several times before it clicked with us. However, when we went over it in class, it seemed to be very clear for the students.

So, if you missed this lecture, do read over the examples from the book, especially examples 3 and 4 on p. 404-405, and then 417 to 420, ,including examples 1 and 2.

(You don't need to worry about the generalized Bayes theorem, which is the last item on p. 420... but the rest of it is what we went over in class.)

### Wednesday May 28:

• Andre Sayre: Monty Hall Problem
• James Marshall: Bayesian Spam Filters
• If time: Jimmy Frier: Birthday Problem

### Friday: May 30

(Intro to recurrence relations, section 7.1)

Suppose we have a sequence of numbers a1, a2, a3, ...

Can we characterize that sequence somehow?

For example:

• the sequence 2,4,6,8,... can be characterized as 2i, where i∈ Z, i≥1.
• the sequence 1,2,4,8,16... can be characterized a 2i where i∈ Z, i≥0

Another important way we can characterize a sequence is with something called a recurrence relation.

Recurrence relations are important in the analysis of many algorithms, and an important tool you need for CS130A.

A recurrence relation for the sequence {an} is an equation that expresses an in terms of one or more of the previous terms of the sequence

That is, we express an in terms of a1, a2, a3, ... an-1

For example:

• the sequence 2,4,6,8,... can be characterized as an = an-1 + 2
• the sequence 1,2,4,8,16... can be characterized as an = 2an-1

Recurrence relations work like recursive functions, in that you need a base case. For recurrence relations, these are called initial conditions.

• the sequence 2,4,6,8,... can be characterized as an = an-1 + 2, with the initial condition a1 = 2
• the sequence 1,2,4,8,16... can be characterized as an = 2an-1with the initial condition a1 = 1

But, these are silly examples just to introduce the terminology. Let's look at some more interesting applications. The first one is not very practical sounding (at first), but it is classic, and interesting. And there is a data structure that it relates to that is useful in practice.

#### Rabbits on an island

Assume that:

• You put one pair of newborn rabbits (one boy, one girl) on an island
• They spend two months being young and innocent, and then they get busy
• One month later, you have another pair
• Assume that a female rabbit always gives birth to exactly one boy and one girl
• This sounds implausible, but this is math, not biology. So, just suppose.
• Assume no rabbits ever die, there is enough food, and no problems with inbreeding, etc.

After n months, how many rabbits will there be? We then covered section 7.1 and how to solve linear non-homogenous recurrence relations of degree 2, using the technique from Section 7.2

### Monday: Jun 2

Presentation: Jimmy Frier: Birthday problem

Master Theorem for Recurrence relations (p. 479)

• applying it to Merge Sort
• applying it to Binary Search
• applying it to traversing a binary tree

### Lecture Wednesday: Jun 4

Final competition: Ryan vs. Andre for the Towers of Hanoi, plus any other final challengers

What will be on the final

#### Expect a survey IN EMAIL: PLEASE FILL IT OUT!!!

Preparation Questions: How well were you prepared for CS40?
=====================
Completely prepared, Somewhat prepared, etc.

1) Calculus with applications
2) Programming experience
3) Problem solving ability

Goal Questions: How well did we acheive these goals?
==============

Completely achieved, Somewhat acheived, etc.

4) Learn basic discrete mathematics
5) Learn the applicability of discrete mathematics to computer science
6) Learn mathematical induction and proof techniques
7) Learn mathematical reasoning

==================

Adequate Coverge, Should Cover More, etc.

8) Propositional and predicate logic
9) Sets, relations and functions
10) Mathematical induction and recurrences
11) Basic number theory and graph theory

#### What's on the exam?

The midterm covered: 1, 2, 3.2 (except big Omega and big Theta), 3.4, 3.5, 3.6, 3.7, 4.1, 4.2, section 8.1, plus notes from class

That material may make an appearance on the final as well. But in addition, we have the following material:

• 3.1 only p. 176 and 177 on the Halting Problem (also covered in Ryan's presentation)
• 3.2 (material on big Omega and big Theta--needed for CS130A) (will discuss in class Friday)
• Chapter 5 (entire chapter, except 5.6)
• In general, you do not need to memorize formulas in this chapter.
I will give you the formulas you need.
Instead, I want you to know how to apply them.
• 5.1 Basics of Counting
• 5.2 Pigeonhole Principle
• 5.3 Permutations and Combinations
• 5.4 Binomial Coefficients
• 5.5 Generialized Permutations and Combinations
• 6.1, 6.2 Probability
• 6.3 Bayes Theorem
• you do not need to memorize Bayes Theorem. Just know how to apply it to a problem.
• 7.1 (entire section) (Intro to Recurrence Relations)
• 7.2 thru page 464 (Linear Homongenous Recurrence Relations)
• 7.3 (Master Theorem)
• Chapter 8: Relations (selected sections as noted)
• 8.1 Relations and their properties: functions, reflexive, symmetric, transitive
• you should memorize definitions of reflexive, symmetric and transitiv
• 8.3 Representing relations (as matrices, adjacency lists, directed graphs)
• 8.4 Closures (symmetric, reflexive, transitive closures)
• Give special attention in your studying to the proof that R*, i.e.
R* = R ∪ R2 ∪ ... Rn ∪ ... is the transitive closure of R
• We spent several lectures on this, including several key lemmas.
• 8.5 Equivalence relations (and partitions of a set).
• Know that an equivalence relation is reflexive, symettric and transitive
• Know that an equivalence relation defines a partition of a set into equivalence classes
• 8.6 Partial Orders (only pages 566-570. Know that a partial order is reflexive, antisymetric and transitive).
• Chapter 9: Graphs
• 9.1 Graphs
• 9.2 Special types of graph
• Bipartite

#### Presentations:

• Strassen's Algorithm (David) (class: please read Example 5 on p. 476, and Example 11 on p. 479)

• Halting Problem (Ryan)

### Friday: Jun 6

Big Omega and Big Theta (from section 3.)

Evaluations

Presentations:

• Halting Problem (Ryan)
• Michael Reynozo: Euler's Theorem
• Brian Kerr: Finite State Machines
• Paul Gonzales: Partial Orders and Security Clearances

A program "halts" if it does not contain an infinite loop.

Here is a java method with an infinite loop, i.e. one that does not halt:

`And here is one that halts:`
```// return true if foo is an even length stringpublic static void noLoops (String foo) {  int i=foo.length;
return (i%2==0);}
```

```public static boolean loops (String foo) {  int i=foo.length;  while (i<2) {	i++; i%=2; // increment i, then mod by two
return (i%2==0);}

```

So both of these methods take a String as an input and return a boolean.

It would be nice to have a Java method that could take the name of any Java method like this as input , along with the input itself, and return true if the method halts, and false if it does not, like this:

`public static boolean halts(String methodName, String theInput) {`
``` // code here that either returns true or false
// depending on whether method halts when you call
// methodName(theInput)```
```}
```

So:

• `halts("noLoops","banana"); `returns `true`
• `halts("loops", "apple")` returns `false`

The problem of writing the method `halts()` is called the "halting problem". We can prove that this cannot be done, i.e. that the halting problem is undecidable.

It is a proof by contradiction. Like all such proofs, it starts by assuming the opposite. So, to prove that we cannot solve the halting problem, assume instead that we can solve it, i.e. that the function `halts()` exists, and works correctly.

In that case, we could write this function:

```public static boolean diagonal(String theInput) {
if (halts("diagonal",theInput)) {

loop();
} else {
return false;

}
```

So, suppose we did write that. Then, what happens if we call:

`halts("diagonal","diagonal")`

We can see from the program code that there are only two possibilities.

1. halts("diagonal","diagonal") returns false. means that when diagonal Diagonal goes into an infinite loop.
• That means that diagonal("diagonal") returns goes into an infinite loop
• The only way this can happen if if `halts("diagonal","diagonal")` returns `true` inside the call to diagonal.
• That's a contradiction. So maybe that shows that halts("diagonal","diagonal") returns false.
2. So suppose halts("diagonal","diagonal") returns false,
• Then inside diagonal, we always hit the else clause
• That means diagonal (with diagonal as input) always halts.
• So that's a contradiction too!

The conclusion is that it is not possible to write a halts() that won't have a bug in it. The halting problem is undecidable.

`

`  `

## Important Disclaimer

This is NOT intended to be a complete transcript of the lectures—far from it! You are expected to come to class and take notes, as needed.

This is, rather, a place for us to keep a record of items such as reading assignments, homework assignments, and in some cases, links to particular aspects of the lectures. This is a convenience for all of us, but again, I repeat for emphasis: this web site does NOT relieve you of the responsibility of attending class and taking notes, and being responsible for anything announced in class.

If you miss class for any reason—excused or not, beyond your control or not—it is generally understood in college that it is your responsibility to get the notes from a classmate. It is not the instructor's responsibility to provide them to you (either via a web site, by email, during office hours, or in any other way.)