CS40, Spring 2008, UC Santa Barbara
Lecture Notes

Instructor: Phill Conrad

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.


Mon 03/31

Overview of what this class will cover.

Included overview of

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)


Practice with predicate logic

Lecture (2pm)

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

Assignment: Read Chapter 1

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:

  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:


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).

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)

Some practice with these techniques

Wed 04/09 lecture

Reading Assigments:

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)


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

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.


Come up with similar definitions for:

The power set: (A)

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

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}.

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

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

Suppose | S| = n

Mon 04/14

Terminology about Relations: a reading assignment

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":

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:

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:

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:

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

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:

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 discussion

Some divisibility proofs

An answer key

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)

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

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

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

Even more terminology: relations and functions

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

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:

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

Here are some relations "on S":

So we could ask questions like:

Those old familiar ordered pairs...

Remember those old familiar ordered pairs from the Cartesian plane?

What set do those ordered pairs come from?

Sets raised to powers

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

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

More on Number Theory

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

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

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


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:

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

How about this one:

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

Here are the rules for a function again:

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

Six possible 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:


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

which are one to one?

which are onto?

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:

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:

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:

Here's a picture:

division theorem

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,

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

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

(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

coprime or relatively prime (From Wikipedia, the free encyclopedia)

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.

Primitive root modulo n (From Wikipedia, the free encyclopedia)

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:

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


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


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?

For Fri 05/09/2008, also read:

For Monday 05/12/2008, also read:

For Wednesday 05/14, read: 5.1 through 5.3

A bit more about Big-O from Sections 3.2


f(x) is O(g(x) if ∃ Ck where |f(x)| ≤ C|g(x)|

Rosen 3.2 figure 1

What is the point of this?

In general:

Rosen 3.2 figure 2

It is helpful to memorize some relationships that come up a lot, as shown in this figure from the textbook:

rosen 3.2 figure 3


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:

Some questions:

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:

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


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


Terminology: Injection, Surjection, Bijection, 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.

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 (A complement), Demorgan's laws for sets (complement of union and intersection), generalized union and intersection

Fri 05/02

Midterm Exam 1

Mon 05/05

Happy Cinco de Mayo.

New Plan:

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:

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.

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:

(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:

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:

Then S must contain R*

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


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)

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.
  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.


Reading Assignment:

Previous Reading Assigments included:

I am adding, these:


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)

Now, today's topic:

Graph Terminology:

Complete Graphs K1 through K6

Cycles C1 through C6



C6 is bipartitie


Complete bipartite graphs:

complete bipartite graphs


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...

Modelling Job Assignments with a bi-partite graph

Other applications are networks (for routing) and parallel computing, where the graph represents which processors can directly communicate.

Adjacency List vs. Adjacency Matrix representations:

You can have an array of vertex object, where each vertex object has a pointer to a linked list of adjacent vertices:

Simple Graph 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:

Simple Graph   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.


Isomorphic Graphs

Are these two graphs the same or different (other than the labelling of the edges)?

Isomorphic Graphs


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?

How about these graphs?

Two isomorphic graphs

What about these?

non-isomorphic graphs

According to our textbook:

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.)

Monday May 26: Memorial Day Holiday

Wednesday May 28:

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:

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:

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

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:

After n months, how many rabbits will there be?

Fibonacci Rabbits


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)


Discussion, Wednesday Jun 4: The Towers of Hanoi

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

Coverage Questions: How well was this material covered?

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:


Friday: Jun 6

Big Omega and Big Theta (from section 3.)



An additional word about the halting problem:

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 string

public 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)


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)) {

} else {
  return false;


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


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.
  2. So suppose halts("diagonal","diagonal") returns false,

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.



Final Exam

The final exam will be 4-7pm on June 9, 2008.

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.)