S (p. 526)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.
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").
Enroll yourself in this course on moodle.cs.ucsb.edu (I'll give you the key in class)
Logic:
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:
New material:
Proofs:
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
Proof by contradiction that √ 2 is irrational (see Rosen p. 80)
Modus Ponens, Modus Tollens, Universal Modus Ponens, Universal Modus Tollens (see summary)
How to prove an "if and only if" (↔)
How to prove the equivalent of three statements (i), (ii), (iii)
Some practice with these techniques
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)
1. p. 119 #4, (10 pts)
2. p. 120, #28 (40 pts)
How a proof by contradiction works (summary)
Review of two proofs by contradiction (summary)
set: unordered collection of objects
defn of subset: A ⊆B ↔ ∀x(x ∈ A →x ∈ B)
Example:
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.
So:
Come up with similar definitions for:
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
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:
S (p. 526)So, read this on your own, and be prepared for discussion questions, (or even a pop quiz!) any time from Friday 04/25 onward.
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
(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.
(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...
Some divisibility proofs
An answer key
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!
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}
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:
Remember those old familiar ordered pairs from the Cartesian plane?
What set do those ordered pairs come from?
Questions: Suppose ℜ is the set of all real numbers (a fancy script R)
These two sets are sometimes called "two space" and "three space".
MIDTERM EXAM: Friday 05/02/2008
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).
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?
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:
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 p→q by contradiction.
We used logic ( a truth table, in fact) to show that: ¬(p→q)≡(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!
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= s1 ⋅ a + t1 ⋅b
j2= s2⋅ a + t2 ⋅b
We need to show that P(0), and P(n)→P(n+1)
We'll do this on the board in class...
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:
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:
We'll also need to understand modular arithmetic (p. 203).
If a and b are integers, and m is a positive integer,
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
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 gk ≡ a (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.
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.
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).
Announcement:
(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.
For Fri 05/09/2008, also read:
For Monday 05/12/2008, also read:
For Wednesday 05/14, read: 5.1 through 5.3
| ( | n | ) |
| r |
f(x) is O(g(x) if ∃ C ∃ k where |f(x)| ≤ C|g(x)|
What is the point of this?
In general:
It is helpful to memorize some relationships that come up a lot, as shown in this figure from the textbook:
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!
Consider the function p(s) : S → {0, 1, 2, ... 9999999 } where:
Some questions:
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.
Questions:
Suppose we constructed a relation g from W to S as follows:
Questions:
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 (
), Demorgan's laws for sets (complement of union and intersection), generalized union and intersection
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)
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.)
Background for Transitive Closure
Also, you'll get your Exam 1 back.
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.
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)
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:
We proved 1 and 2, and left 3 for Wednesday.
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)
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.).
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)
Extra Credit presentations:
Topics:
Previous Reading Assigments included:
I am adding, these:
When the section and page number are not specified, they are the same as the previous problem(s)
Hypercubes:
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.
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?
How about these graphs?
What about these?
According to our textbook:
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.)
(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.
Assume that:
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
Presentation: Jimmy Frier: Birthday problem
Master Theorem for Recurrence relations (p. 479)
Final competition: Ryan vs. Andre for the Towers of Hanoi, plus any other final challengers
What will be on the final
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
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:
Strassen's Algorithm (David) (class: please read Example 5 on p. 476, and Example 11 on p. 479)
Halting Problem (Ryan)
Big Omega and Big Theta (from section 3.)
Evaluations
Presentations:
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)
}
So:
halts("noLoops","banana"); returns truehalts("loops", "apple") returns falseThe 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.
halts("diagonal","diagonal") returns true inside the call to diagonal.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.
`
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.)