Computation Lecture Notes and Exercises for CSC236
Computation Lecture Notes and Exercises
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
Computation
Lecture Notes and Exercises for CSC236
Department of Computer Science
Contents
Introduction 5
Induction 9
Recursion 29
Program Correctness 49
Regular Languages & Finite Automata 67
In Which We Say Goodbye 85
Appendix: Runtime Analysis 87
Introduction
There is a common misconception held by our students, the students of
other disciplines, and the public at large about the nature of computer
science. So before we begin our study this semester, let us clear up
exactly what we will be learning: computer science is not the study of
programming, any more than chemistry is the study of test tubes or
math the study of calculators. To be sure, programming ability is a
vital tool in any computer scientist’s repertoire, but it is still a tool in
service to a higher goal.
Computer science is the study of problem-solving. Unlike other disci-
plines, where researchers use their skill, experience, and luck to solve
problems at the frontier of human knowledge, computer science asks:
What is problem-solving? How are problems solved? Why are some
problems easier to solve than others? How can we measure the quality
of a problem’s solution?
Even the many who go into industry
confront these questions on a daily
basis in their work!
It should come as no surprise that the field of computer science
predates the invention of computers, since humans have been solving
problems for millennia. Our English word algorithm, a sequence of
steps taken to solve a problem, is named after the Persian mathemati-
cian Muhammad ibn Musa al-Khwarizmi, whose mathematics texts
were compendia of mathematics computational procedures. In 1936,
The word algebra is derived from the
word al-jabr, appearing in the title
of one of his books, describing the
operation of subtracting a number from
both sides of an equation.
Alan Turing, one of the fathers of modern computer science, devel-
oped the Turing Machine, a theoretical model of computation which is
widely believed to be just as powerful as all programming languages
in existence today. In one of the earliest and most fundamental results
A little earlier, Alonzo Church (who
would later supervise Turing during
the latter’s graduate studies) developed
the lambda calculus, an alternative
model of computation that forms
the philosophical basis for functional
programming languages like Scheme,
Haskell, and ML.
in computer science, Turing proved that there are some problems that
cannot be solved by any computer that has ever or will ever be built –
before computers had been invented at all!
6 david liu utm edits by daniel zingaro
But Why Do I Care?
A programmer’s value lies not in her ability to write code, but to un-
derstand problems and design solutions – a much harder task. Be-
ginning programmers often write code by trial and error (“Does this
compile? What if I add this line?”), which indicates not a lack of pro-
gramming experience, but a lack of design experience. When presented
with a problem, many students often jump straight to the computer,
even if they have no idea what they are going to write! And when the
code is complete, they are at a loss when asked the two fundamental
questions: Why is your code correct, and is it a good solution?
“My code is correct because it passed
all of the tests” is reasonable but unsat-
isfying. What I really want to know is
how your code works.
In this course, you will learn the skills necessary to answer both of
these questions, improving both your ability to reason about the code
you write and your ability to communicate your thinking with others.
These skills will help you design cleaner and more efficient programs,
and clearly document and present your code. Of course, like all skills,
you will practice and refine these throughout your university educa-
tion and in your careers.
Overview of this Course
The first section of the course introduces the powerful proof technique
of induction. We will see how inductive arguments can be used in
many different mathematical settings; you will master the structure
and style of inductive proofs, so that later in the course you will not
even blink when asked to read or write a “proof by induction.”
From induction, we turn our attention to the runtime analysis of
recursive programs. You have done this already for non-recursive pro-
grams, but did not have the tools necessary to handle recursion. We
will see that (mathematical) induction and (programming) recursion
are two sides of the same coin, so we use induction to make analysing
recursive programs easy as cake. After these lessons, you will always Some might even say, chocolate cake.
be able to evaluate your recursive code based on its runtime, a very
important consideration!
We next turn our attention to the correctness of both recursive and
non-recursive programs. You already have some intuition about why
your programs are correct; we will teach you how to formalize this
intuition into mathematically rigorous arguments, so that you may
reason about the code you write and determine errors without the use
of testing.
This is not to say tests are unnecessary!
The methods we’ll teach you in this
course are quite tricky for larger soft-
ware systems. However, a more mature
understanding of your own code cer-
tainly facilitates finding and debugging
errors.
introduction to the theory of computation 7
Finally, we will turn our attention to the simplest model of computa-
tion, the finite automaton. This serves as both an introduction to more
complex computational models like Turing Machines, and also formal
language theory through the intimate connection between finite au-
tomata and regular languages. Regular languages and automata have
many other applications in computer science, from text-based pattern
matching to modelling biological processes.
Prerequisite Knowledge
CSC236 is mainly a theoretical course, the successor to MAT102. This
is fundamentally a computer science course, though, so while math-
ematics will play an important role in our thinking, we will mainly
draw motivation from computer science concepts. Also, you will be
expected to both read and write Python code at the level of CSC148.
Here are some brief reminders about things you need to know – and
if you find that you don’t remember something, review early!
Concepts from MAT102
In MAT102, you learned how to write proofs. This is the main object
of interest in CSC236, so you should be comfortable with this style
of writing. However, one key difference is that we will not expect
(nor award marks for) a particular proof structure – indentation is
no longer required, and your proofs can be mixtures of mathematics,
English paragraphs, pseudocode, and diagrams! Of course, we will
still greatly value clear, well-justified arguments, especially since the
content will be more complex.
So a technically correct solution that is
extremely difficult to understand will
not receive full marks. Conversely, an
incomplete solution which explains
clearly partial results (and possibly
even what is left to do to complete
the solution) will be marked more
generously.
Concepts from CSC148
Recursion, recursion, recursion. If you liked using recursion CSC148,
you’re in luck: induction, the central proof structure in this course, is
the abstract thinking behind designing recursive functions. And if you
didn’t like recursion or found it confusing, don’t worry! This course
will give you a great opportunity to develop a better feel for recursive
functions in general, and even give you programming opportunities to
get practical experience.
This is not to say you should forget everything you have done with
iterative programs; loops will be present in our code throughout this
8 david liu utm edits by daniel zingaro
course, and will be the central object of study for a week or two when
we discuss program correctness. In particular, you should be very
comfortable with the central design pattern of first-year python: com-
A design pattern is a common coding
template which can be used to solve a
variety of different problems. “Looping
through a list” is arguably the simplest
one.puting on a list by processing its elements one at a time using a for or
while loop.
You should also be comfortable with terminology associated with
trees, which will come up occasionally throughout the course when we
discuss induction proofs.
You will also have to remember the fundamentals of Big-O algo-
rithm analysis, and how to determine tight asymptotic bounds for
common functions.
Finally, the last part of the course deals with regular languages;
you should be familiar with the terminology associated with strings,
including length, reversal, concatenation, and the empty string.
Induction
What is the sum of the numbers from 0 to n? This is a well-known
identity you’ve probably seen before:
n
∑
i=0
i =
n(n + 1)
2
.
A “proof” of this is attributed to Gauss:
1+ 2+ 3+ · · ·+ n− 1+ n = (1+ n) + (2+ n− 1) + (3+ n− 2) + · · ·
= (n + 1) + (n + 1) + (n + 1) + · · ·
=
n
2
(n + 1) (since there are
n
2
pairs)
This isn’t exactly a formal proof – what if n is odd? – and although it We ignore the 0 in the summation, since
this doesn’t change the sum.could be made into one, this proof is based on a mathematical “trick”
that doesn’t work for, say,
n
∑
i=0
i2. And while mathematical tricks are
often useful, they’re hard to come up with in the first place! Induction
gives us a different way to tackle this problem that is astonishingly
straightforward.
A predicate is a parametrized logical statement. Another way to view
a predicate is as a function that takes in one or more arguments, and
outputs either True or False. Some examples of predicates are:
EV(n) : n is even
GR(x, y) : x > y
FROSH(a) : a is a first-year university student
Every predicate has a domain, the set of its possible input values. For
example, the above predicates could have domains N, R, and “the set We will always use the convention that
0 ∈N unless otherwise specified.of all UofT students,” respectively. Predicates give us a precise way
of formulating English problems; the predicate that is relevant to our
example is
P(n) :
n
∑
i=0
i =
n(n + 1)
2
.
10 david liu utm edits by daniel zingaro
You might be thinking right now: “Okay, now we’re going to prove
A common mistake: defining the
predicate to be something like
P(n) :
n(n + 1)
2
. Such an expres-
sion is wrong and misleading because
it isn’t a True/False value, and so fails
to capture precisely what we want to
prove.
that P(n) is true.” But this is wrong, because we haven’t yet defined
n! So in fact we want to prove that P(n) is true for all natural numbers
n, or written symbolically, ∀n ∈ N, P(n). Here is how a formal proof
might go if we were not using mathematical induction:
Proof of ∀n ∈N,
n
∑
i=0
i =
n(n + 1)
2
Let n ∈N.
# Want to prove that P(n) is true.
Case 1: Assume n is even.
# Gauss' trick
...
Then P(n) is true.
Case 2: Assume n is odd.
# Gauss' trick, with a twist?
...
Then P(n) is true.
Then in all cases, P(n) is true.
Then ∀n ∈N, P(n). ■
Instead, we’re going to see how induction gives us a different, easier
way of proving the same thing.
The Induction Idea
Suppose we want to create a viral Youtube video featuring “The World’s
Longest Domino Chain!!! (like plz)".
Of course, a static image like the one featured on the right is no
good for video; instead, once we have set it up we plan on recording
all of the dominoes falling in one continuous, epic take. It took a lot
of effort to set up the chain, so we would like to make sure that it will
work; that is, that once we tip over the first domino, all the rest will
fall. Of course, with dominoes the idea is rather straightforward, since
we have arranged the dominoes precisely enough that any one falling
will trigger the next one to fall. We can express this thinking a bit more
formally:
(1) The first domino will fall (when we push it).
(2) For each domino, if it falls, then the next one in the chain will fall
(because each domino is close enough to the next one).
introduction to the theory of computation 11
From these two thoughts, we can conclude that
(3) Every domino in the chain will fall.
We can apply the same reasoning to the set of natural numbers. In-
stead of “every domino in the chain will fall,” suppose we want to
prove that “for all n ∈ N, P(n) is true”, where P(n) is some predi-
cate. The analogues of the above statements in the context of natural
numbers are
(1) P(0) is true (0 is the “first” natural number) The “is true” is redundant, but we will
often include these words for clarity.
(2) ∀k ∈N, P(k)⇒ P(k + 1)
(3) ∀n ∈N, P(n) is true
Putting these together yields the Principle of Simple Induction (also known simple/mathematical induction
as Mathematical Induction):(
P(0) ∧ ∀k ∈N, P(k)⇒ P(k + 1))⇒ ∀n ∈N, P(n)
A different, slightly more mathematical intuition for what induction
says is that “P(0) is true, and P(1) is true because P(0) is true, and P(2)
is true because P(1) is true, and P(3) is true because. . . ” However, it
turns out that a more rigorous proof of simple induction doesn’t ex-
ist from the basic arithmetic properties of the natural numbers alone.
Therefore mathematicians accept the principle of induction as an ax-
iom, a statement as fundamentally true as 1+ 1 = 2.
It certainly makes sense intuitively, and
turns out to be equivalent to another
fundamental math fact called the Well-
Ordering Principle.
This gives us a new way of proving a statement is true for all natural
numbers: instead of proving P(n) for an arbitrary n, just prove P(0),
and then prove the link P(k)⇒ P(k+ 1) for an arbitrary k. The former
step is called the base case, while the latter is called the induction step.
We’ll see exactly how such a proof goes by illustrating it with the
opening example.
Example. Prove that for every natural number n,
n
∑
i=0
i =
n(n + 1)
2
.
The first few induction examples
in this chapter have a great deal of
structure; this is only to help you learn
the necessary ingredients of induction
proofs. We will not be marking for a
particular structure in this course, but
you will probably find it helpful to use
our keywords to organize your proofs.
Proof. First, we define the predicate associated with this question. This
lets us determine exactly what it is we’re going to use in the induction
proof.
Step 1 (Define the Predicate) P(n) :
n
∑
i=0
i =
n(n + 1)
2
It’s easy to miss this step, but without it, often you’ll have trouble
deciding precisely what to write in your proofs.
12 david liu utm edits by daniel zingaro
Step 2 (Base Case): n = 0. We would like to prove that P(0) is true.
Recall the meaning of P:
P(0) :
0
∑
i=0
i =
0(0+ 1)
2
.
This statement is trivially true, because both sides of the equation are
equal to 0.
For induction proofs, the base case
usually a very straightforward proof.
In fact, if you find yourself stuck on the
base case, then it is likely that you’ve
misunderstood the question and/or are
trying to prove the wrong predicate.Step 3 (Induction Step): the goal is to prove that ∀k ∈ N, P(k) ⇒
P(k + 1). Let k ∈ N be some arbitrary natural number, and assume
P(k) is true. This antecedent assumption has a special name: the In-
duction Hypothesis. Explicitly, we assume that
k
∑
i=0
i =
k(k + 1)
2
.
Now, we want to prove that P(k+ 1) is true, i.e., that
k+1
∑
i=0
i =
(k + 1)(k + 2)
2
.
This can be done with a simple calculation:
We break up the sum by removing the
last element.
k+1
∑
i=0
i =
(
k
∑
i=0
i
)
+ (k + 1)
=
k(k + 1)
2
+ (k + 1) (By Induction Hypothesis)
= (k + 1)
(
k
2
+ 1
)
=
(k + 1)(k + 2)
2
Therefore P(k + 1) holds. This completes the proof of the induction
The one structural requirement we do
have for this course is that you must
always state exactly where you use
the induction hypothesis. We expect
to see the words “by the induction
hypothesis” at least once in each of
your proofs.
step: ∀k ∈N, P(k)⇒ P(k + 1).
Finally, by the Principle of Simple Induction, we can conclude that
∀n ∈N, P(n). ■
In our next example, we look at a geometric problem – notice how
our proof will use no algebra at all, but instead constructs an argu-
ment from English statements and diagrams. This example is also
interesting because it shows how to apply simple induction starting at
a number other than 0.
Example. A triomino is a three-square L-shaped figure. To the right,
we show a 4-by-4 chessboard with one corner missing that has been
tiled with triominoes.
Prove that for all n ≥ 1, any 2n-by-2n chessboard with one corner
missing can be tiled with triominoes.
introduction to the theory of computation 13
Proof. Predicate: P(n): Any 2n-by-2n chessboard with one corner miss-
ing can be tiled with triominoes.
Base Case: This is slightly different, because we only want to prove
the claim for n ≥ 1 (and ignore n = 0). Therefore our base case is
n = 1, i.e., this is the “start” of our induction chain. When n = 1,
we consider a 2-by-2 chessboard with one corner missing. But such a
chessboard is exactly the same shape as a triomino, so of course it can
be tiled by triominoes!
Again, a rather trivial base case. Keep
in mind that even though it was simple,
the proof would have been incomplete
without it!Induction Step: Let k ≥ 1 and suppose that P(k) holds; that is,
that every 2k-by-2k chessboard with one corner missing can be tiled by
triominoes. (This is the Induction Hypothesis.) The goal is to show that
any 2k+1-by-2k+1 chessboard with one corner missing can be tiled by
triominoes.
Consider an arbitrary 2k+1-by-2k+1 chessboard with one corner miss-
ing. Divide it into quarters, each quarter a 2k-by-2k chessboard.
Exactly one of these has one corner missing; by the Induction Hy-
pothesis, this quarter can be tiled by triominoes. Next, place a single
triomino in the middle that covers one corner in each of the three re-
maining quarters.
Each of these quarters now has one corner covered, and by the I.H.
again, they can each be tiled by triominoes. This completes the tiling
of the 2k+1-by-2k+1 chessboard. ■ Note that in this proof, we used the
induction hypothesis twice! (Or tech-
nically, 4 times, one for each 2k-by-2k
quarter.)Before moving on, here is some intuition behind what we did in the
previous two examples. Given a problem of a 2n-by-2n chessboard,
we repeatedly broke it up into smaller and smaller parts, until we
reached the 2-by-2 size, which we could tile using just a single tri-
omino. This idea of breaking down the problem into smaller ones
“again and again” was a clear sign that a formal proof by induction
was the way to go. Be on the lookout for phrases like “repeat over and
over” in your own thinking to signal that you should be using induc-
tion. In the opening example, we used an even more specific approach: In your programming, this is the same
sign that points to using recursive
solutions as the easiest approach.
in the induction step, we took the sum of size k+ 1 and reduced it to a
sum of size k, and evaluated that using the induction hypothesis. The
cornerstone of simple induction is this link between problem instances
of size k and size k + 1, and this ability to break down a problem into
something exactly one size smaller.
Example. Consider the sequence of natural numbers satisfying the fol-
lowing properties: a0 = 1, and for all n ≥ 1, an = 2an−1 + 1. Prove
that for all n ∈N, an = 2n+1 − 1.
We will see in the next chapter one way
of discovering this expression for an.
14 david liu utm edits by daniel zingaro
Proof. The predicate we will prove is
P(n) : an = 2n+1 − 1.
The base case is n = 0. By the definition of the sequence, a0 = 1, and
20+1 − 1 = 2− 1 = 1, so P(0) holds.
For the induction step, let k ∈ N and suppose ak = 2k+1 − 1. Our
goal is to prove that P(k + 1) holds. By the recursive property of the
sequence,
ak+1 = 2ak + 1
= 2(2k+1 − 1) + 1 (by the I.H.)
= 2k+2 − 2+ 1
= 2k+2 − 1 ■
When Simple Induction Isn’t Enough
By this point, you have done several examples using simple induc-
tion. Recall that the intuition behind this proof technique is to reduce
problems of size k+ 1 to problems of size k (where “size” might mean
the value of a number, or the size of a set, or the length of a string,
etc.). However, for many problems there is no natural way to reduce
problem sizes just by 1. Consider, for example, the following problem:
Every prime can be written as a product
of just one number: itself!Prove that every natural number greater than 1 has a prime
factorization, i.e., can be written as a product of primes.
How would you go about proving the induction step, using the
method we’ve used so far? That is, how would you prove P(k) ⇒
P(k + 1)? This is a very hard question to answer, because even the
prime factorizations of consecutive numbers can be completely differ-
ent!