\documentclass[11pt, twoside]{article}

\input{macros-course}

\newcommand{\nand}{|}
\renewcommand{\implies}{\longrightarrow}

\begin{document}
\pset{3}{September 19, 2000}{2:35pm in lecture, September 26, 2000}

\textbf{Self-study:  More set theory}
Read: Velleman, Sections 1.3, 1.4, 2.3. \\
Self-study problems (not to be handed in): Velleman \S 1.3, Exercise 4, \S 1.4
Exercises 1, 3, 4, 5, 6, 8, \S 2.3 Exercises 2, 3, 5, 6\\

%[[[Shlomi:  I put in a few more exercises from 1.4.]]]

\textbf{Reading:}
Velleman, Chapter 4 \\
Rosen, Sections 3.2, 3.3, 3.4, Chapter 6.\\

\medskip
\begin{problems}

\problem 
\textbf{Well-Ordering}
%[[[Shlomi:  We don't need to always tell them what the problem is
%about.  Sometimes they'll have to figure this out.  OK for this time,
%though.]]]
% (Rosen Chapter 3, Exercise 36 (p. 228).)
%[[[Shlomi:  I typed out the exercise rather than just citing Rosen,
%because I added the request that they ``explain their reasons''.]]]
A set is {\bf well-ordered\/} if every nonempty subset of the set has
a least element.
Determine whether each of the following sets is well-ordered.
Explain your reasons.
\bparts
\ppart The set of integers.
\ppart The set of integers greater than $-100$.
\ppart The set of positive rationals.
\ppart The set of positive rationals with denominator less than $100$.
\eparts

\problem \textbf{Structural Induction}

The set $SSS$ of ``super-symmetric strings'' is defined as follows:
\begin{enumerate}
\item
The length one strings consisting of individual letters of the
alphabet, $a$, $b$, $c$, $d$, ... $z$, are in $SSS$. \\
\item
If $\alpha$ and $\alpha'$ are two strings in $SSS$ then the string
$\alpha \alpha' \alpha$ is in $SSS$.
\item
$SSS$ contains nothing else.
\end{enumerate}
%[[[Shlomi:  Looks like we should add this ``nothing else'' clause in
%lecture notes for 4, for the definition of binary trees.]]]
%[[[Shlomi:  I changed this so that it's defining a subset of the set
%of all strings rather than an entirely new kind of data structure.
%That way, we get to use the previously-defined concatenation operation.]]]
\bparts
\ppart
Which of the following are super-symmetric strings?
i.  a     
ii.  aaaba   
iii.  abcbacabcba
iv. $\lambda$, the empty string
v. abaabcbaaba
%[[[George:  You might want to make up some more interesting strings,
%replace some of my examples, etc.]]]

\ppart
Prove by induction that in any super-symmetric string $\alpha$, 
exactly one letter appears an odd number of times.
\eparts
%[[[Shlomi:  Neat problem!]]]

\problem  
\textbf{Induction and Recursive Algorithms}
\bparts
\ppart Rosen \S 3.4, Exercise 18, and prove correctness of your algorithm.

\ppart Rosen \S 3.4, Exercise 24, and prove correctness of your algorithm.
\eparts
%[[[Shlomi:  Perhaps just use Exercise 18.  Does Ex. 24 introduce any
%really new ideas not covered by 18?  Let's not be too repetitive.]]]

\problem \textbf{Relations}
\bparts
\ppart Velleman \S 4.2, Exercise 3
\ppart Velleman \S 4.2, Exercise 7
\eparts
%[[[Shlomi:  I noticed a problem with the composition operation.  BOTH
%of our books use the reverse notation for the order of composition,
%where S circle R means that R comes first.  SO, I suggest that we go
%back and change the notation used in Lecture 5 notes.  Sigh.]]]

\problem \textbf{Relations}
Velleman \S 4.3, Exercise 9.
%[[[Shlomi:  Good problem.]]]

\problem \textbf{Relations}
\bparts
\ppart Velleman \S 4.4, Exercise 1. %[[[Good finger exercise.]]]
\ppart Velleman \S 4.4, Exercise 5. %[[[Good]]]
\ppart Velleman \S 4.4, Exercise 12. %[[[Shlomi:  Will you cover this
				     %in lecture?  If so, OK.  It will
				     %be a little hard for them, but
				     %that's probably OK.]]]
\eparts

\problem \textbf{Relations}
\bparts
\ppart Velleman \S 4.5, Exercise 3. %[[[OK, though it doesn't have
				    %anything to do with closures!]]]
\ppart Velleman \S 4.5, Exercise 5. %[[[OK, though they'll find it hard.]]]
\ppart Velleman \S 4.5, Exercise 12. %[[[OK]]]
\eparts
%[[[Shlomi: All the parts of this problem are a bit abstract.]]]

\end{problems}

%[[[Shlomi:  We have coverage holes:
%
% I assume you are going to cover equivalence relations before
% covering partial orders, as we discussed yesterday.
% So, we need to cover equivalence relations on the pset.
% 
% Add one or two problems on this, e.g., Rosen 6.5, problems 32, 38]]]
%
% Other coverage holes:  More advanced topics on partial orders, like
% topological sorting, task scheduling, Dilworth.
% But this is probably reasonable to postpone till the following week,
% because you might not get to these in lecture 5.
% But then we should make sure to give a problem on at least the first
% two of these topics for the next week.
% Well, we might want to at least cover topological sorting on this
% pset, if we're pretty sure we'll cover it in lecture 5 and in
% tutorial 3.
% If so, I suggest:
% 
% Find two total orders that are topological sorts of the divisibility
% relation for the set of natural numbers 1-8.
% (a) One with the MOST POSSIBLE pairs out of numerical order.
% (b) One with the FEWEST POSSIBLE pairs out of numerical order.
%
% I just made this last problem up.  Unfortunately, my solution to (a)
% is just a case analysis--I got 9 pairs out of order, but I don't
% have a proof that this is optimum.  If this seems too uninteresting,
% time-consuming, unsatisfying, or whatever, we could just ask them to
% find two different total orders.
%
% With these additional problems, the pset is probably now too long.
% Suggest which one(s) to delete?]]]

\end{document}





