(Required) Mitchell, Chapters 1--2.
(Recommended) "Why Undergraduates Should Learn the Principles of Programming Languages", 2011. An overvew of why PL is worth studying and what the course objectives are. Draft Available on the course web page.
In preparation for the semester, please do the following:
Carefully read the syllabus.
Accept my Slack invitation (sent via email) and join the CS 334 Slack Workspace. Send me a direct message to say "hi".
You will recieve an email about setting up your account on Gradescope. Please log in and complete that process. You will submit work through Gradescope.
Set up the recommended software from the software page.
As indicated below in [What To Turn In], your answers must be submitted as a single PDF each week. There are many ways to prepare a PDF:
All of these are fine. Even plain text would work reasonably well, although some basic formatting would make your life easier. You will likely want to include figures in problem sets some weeks --- for this you can use a drawing program or just draw by hand and take pictures.
Here are a few resources if you'd like to use latex or markdown:
Latex:
Markdown:
For each of the following function definitions, give the graph of the function. Say whether this is a partial function or a total function on the integers. If the function is partial, say where the function is defined and undefined.
For example, the graph of \tt f(x) = if\ x>0\ then\ x+2\ else\ x/0 is the set of ordered pairs \{ \langle x, x+2\rangle \,|\, x>0\}. This is a partial function. It is defined on all integers greater than 0 and undefined on integers less than or equal to 0.
Functions:
\tt f(x) = if\ x+2>3\ then\ x*5\ else\ x/0
\tt f(x) = if\ x<0\ then\ 1\ else\ f(x-2)
\tt f(x) = if\ x=0\ then\ 1\ else\ f(x-2)
Suppose you are given the code for a function {\tt Halt0} that can determine whether a program P requiring no input halts. Can you solve the halting problem using {\tt Halt0}?
To be more precise, suppose I give you a Java function
boolean Halt0(String program)
where calling the function with the source code for program P has
the following behavior. Halt0(P)
returns:
You should not make any assumptions about the behavior of Halt0
on
arguments that do not consist of a syntactically correct program.
Can you write a Java program Halt
that reads a program text
P as input, reads an integer n as input, and then decides
whether P halts when it reads n as input? Such a Halt
program
would have the following form, and it would print "yes" if P halts
when it runs and reads input n a
nd "no" if P does not halt when
it runs and reads input n:
void Halt() {
String P = readString();
String n = readInteger();
...
}
You may assume that any program P read by your program begins with
a statement that reads a single integer from standard input, and
then performs operations Q. That is, all P read at the start of
your Halt
function will have the form
int x = readInteger();
Q
where Q is the rest of the program text, and Q does not perform any input.
If you believe that the halting problem can be solved if you are
given Halt0
, then explain your answer by describing how a program solving the halting problem would work. To
do this, just describe what replaces \ldots in the Halt
program definition above. If you believe that the halting problem
cannot be solved using Halt0
, then explain
briefly why you think not.