path: root/fonts/apl/problems.tex

%===================================================================
% Sample problems; solutions give examples on using APL style in TeX
% Taken from the course ``Mathematics on the Computer'', Fall 87
%===================================================================

\magnification = \magstep1

\advance\vsize by 3truecm

\input mssymb    % for some math symbols only! This is the new
                 % symbol font for some standard and non-standard
                 % mathematical symbols. It is only used here for
                 % blackboard bold letters. If you dont have it,
                 % just define \def\Bbb{} etc.

\input aplstyle

\choosett{apl}

\font\sans = amss10
\font\sltt = amsltt10

\def\header{{\sans  Sample problems  9.\ 10.\ 1987}}
% some of them come from Sims' ``Abstract Algebra, A Computational Approach''
\def\APL{{\sltt APL}}

\nopagenumbers
\tolerance = 300
\noindent
\header

\vskip 2cm

\item{1.} Let $N>1$ be an integer. Show that each of the following
          matrices represents a binary operation on
          $S(N)$ (we set locally \BX@IO_0@.) Which of them are
          associative, which commutative?
          \medskip

          \itemitem{a)} @(@\IO@N)@\SO@.@\CE\IO@N@

          \itemitem{b)} \AB@(@\IO@N)@\SO@.-@\IO@N@

          \itemitem{c)} @N@\AB@(@\IO@N)@\SO@.+@\IO@N@

          \itemitem{d)} @N@\AB@(@\IO@N)@\SO@.#@\IO@N@

           \medskip
\item{}    Here @x@\CE@y@ is $\max(x,y)$, @x@\AB@y@ is
           $y\bmod x$ and \AB@x@ is the absolute value of $x$.

\bigskip

\item{2.} Write an \APL\ function @GPOWER@ that computes for a group
          @G@ (global variable) the $n$-th power of a given element $x$.
          (If $S(M)$ is a representation vector of @G@, then
          @GPOWER@ is a map $S(M)\times \Bbb Z\to S(M)$. Simply
          use iteration.)

\bigskip

\item{3.} (Continuing problem 2.) A faster algorithm is obtained by
          decomposing $x^n$ into its 2--base form
          $x^n = x^{i_0}\times x^{2i_1}\times
          x^{4i_2}\times ... \times x^{{2^k}i_k}$, where $i_j\in\{0,1\}$. Show
          that the complexity of this algorithm is $O(\log_2(n))$.
          (Show that the number of necessary multiplications does
          not exceed $2\log_2(n)$). How would you write the corresponding
          function in \APL? (Note that the binary representation of $n$
          can be obtained by applying iteratively the procedure $n\bmod 2$.)

\bigskip

\item{4.} Write an \APL\ function @GTSGP@ that computes for a given group @G@
          (global variable) the subgroup generated by a given subset $A$. The
          function @GTSGP@ has one argument (the vector @A@) and returns
          a subset of the set $S(N)$ (as a vector). (Extend the set @A@
          by the group operation until @A@ becomes closed with respect
          to the operation.)

\bigskip

\item{5.} Write an \APL\ function @INV@ that returns for a group @G@
          the vector of inverse elements as a vector $S(N)\to S(N)$ so
          that the index of the inverse of $x_i$ is @(INV G)[I]@.

\bigskip

\item{6.} Let $(G,\theta)$ be a group and let $A$ be a subset of $G$. Program
          the following algorithm in \APL\ to find the subgroup @H@
          generated by @A@. Compare the perfomance of this algorithm
          with the algorithm in Problem 4.
          \medskip

          \itemitem{a)} put $H$ and $Y$ equal to $\{e\}$.

          \itemitem{b)} let $Y$ be $YA\smallsetminus H$.

          \itemitem{c)} if $Y=\emptyset$, stop.

          \itemitem{d)} put $H$ equal to $H\cup Y$ and
                        go to (b).

          \medskip
\item{}     ($e$ is the neutral element and $YA\smallsetminus H$
           is the set--theoretical difference of $YA$ and $H$.
           The product $YA$ is the set $\{y\theta a: y\in Y, a\in A\}$.)

\bigskip

\item{7.} Write an \APL\ function @PROD@ that returns for given groups
          $(G_1,\theta_1)$ ja $(G_2,\theta_2)$ the {\sl direct product}
          $(G_1\times G_2,\theta_1\times\theta_2)$ as a group table.
          (The binary operation in the product is $(x,y)\theta_1\times\theta_2
          (z,w) = (x\theta_1 z,y\theta_2 w)$).

\bigskip

\vfill\eject

%==========================================================================
% Solutions to above sample exercises
%==========================================================================

%\advance\vsize by 3truecm

\choosett{apl}

\noindent
\header%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\vskip 1cm

\noindent
As the index of the neutral element we use the index origin \BX@IO@ which
usually has the value @0@. Then  $S(N)=
\{0,\dots,N-1\}$, given by the vector \IO@N@.
An example on groups are the cyclic groups $({\bf Z}_n,+)$
the group tables of which are generated by the \APL\ function @ZNPLUS@:

\hskip\parskip\vbox{\hsize=15truecm
\begintt
    @DL Z_ZNPLUS N;@BXIO
[1]   @BXIO_0
[2]   Z_N@AB(@ION)@SO.+@ION
    @DL
\endtt
}\smallskip

\item{1.}  The matrices represent binary operations of $S(N)$,
           since they are $N\times N$-matrices with elements from
           $S(N)$. They are all associative and also commutative except for
           the case (b). This can be seen by the function @TEST@:

\hskip\parskip\vbox{\hsize=15truecm
\begintt
    @DL Z_TEST B
[1]  " B IS A BINARY OPERATION. THE FUNCTION RETURNS A BOOLEAN 2-VECTOR
[2]  " (B ASSOCIATIVE, B COMMUTATIVE)
[3]   Z_(&/&/&/B[B;]=B[;B]),&/&/B=@TRB
    @DL
\endtt
}\smallskip

\item{2.}

\hskip\parskip\vbox{\hsize=15truecm
\begintt
    @DL P_X GPOWER N;I
[1]  " G GLOBAL
[2]   P_@BXIO @DM I_0
[3]  TEST:@GO(N<I_I+1)/0
[4]   P_G[P;X]
[5]   @GOTEST
    @DL
\endtt
}\smallskip

\item{3.}

\hskip\parskip\vbox{\hsize=15truecm
\begintt
    @DL P_X BGPOWER N;IJ
[1]  " G GLOBAL
[2]   P_@BXIO
[3]  NEXTJ:@GO(0=N,IJ_2@ABN)/0,SQX
[4]   P_G[P;X]
[5]  SQX:X_G[X;X]
[6]   N_(N-IJ)%2
[7]   @GONEXTJ
    @DL
\endtt
}

\item{}  A comment: if $i_j=0$, then the power is not increased,
         but the square $x^{2^{j+1}}=(x^{2^j})^2$ is computed.
         The number of iterations is $k$; $n = i_0+i_12+\cdots+i_k2^k \ge 2^k$,
         when $i_k \not= 0$, and hence $k \le \log_2(n)$.
         Thus, the complexity is $O(\log_2(n))$.
\smallskip

\vfill\eject
\item{4.}

\hskip\parskip\vbox{\hsize=15truecm
\begintt
    @DL Z_A GTSGP G
[1]  " RETURNS THE SUBGROUP OF G GENERATED BY A
[2]   Z_,A
[3]  TEST:@GO(&/&/G[Z;Z]@EPZ)/FOUND
[4]   Z_Z UNION G[Z;Z]
[5]   @GOTEST
[6]  FOUND:Z_Z[@GUZ]
    @DL
\endtt
}

\hskip\parskip\vbox{\hsize=15truecm
\begintt
    @DL Z_A UNION B;V;@BXIO
[1]   V_(,A),,B
[2]   @BXIO_1
[3]   Z_,CLEAN((@ROV),1)@ROV
    @DL
\endtt
}

The auxiliary function @CLEAN@ was given earlier.
\bigskip

\item{5.}

\hskip\parskip\vbox{\hsize=15truecm
\begintt
    @DL Z_INV G
[1]  " RETURNS THE VECTOR OF INVERSE ELEMENTS OF G
[2]   (@BXIO=,G)/,(@ROG)@ROG[@BXIO;]
    @DL
\endtt
}\smallskip

\item{6.}

\hskip\parskip\vbox{\hsize=15truecm
\begintt
    @DL H_A BGTSGP G;Y
[1]  " RETURNS THE SUBGROUP OF G GENERATED BY A
[2]   H_Y_@BXIO
[3]  B:@GO(0=@ROY_(,G[Y;A])MINUS H)/0
[4]   H_H UNION Y
[5]   @GOB
    @DL
\endtt
}

\hskip\parskip\vbox{\hsize=15truecm
\begintt
    @DL Z_A MINUS B
[1]   Z_(@NTA@EPB)/A
    @DL
\endtt
}\smallskip

\item{7.}  If the elements of $G_i$ have been indexed by the interval
           $[0,n_i-1]$, the elements of $G_1\times G_2$ become indexed
           in a natural way by the elements of the Cartesian product
           $[0,n_1-1]\times[0,n_2-1]$. With the bijection
           $(i,j) \mapsto in_2+j:[0,n_1-1]\times[0,n_2-1]
           \longrightarrow[0,n_1n_2-1]$
           (the inverse $k\mapsto((k-(k \bmod n_2))/n_2,k \bmod n_2)$
           selects the quotient and remainder in the division by $n_2$)
           we get $[0,n_1n_2-1]$ as the index set.

\vfill\eject
\hskip\parskip\vbox{\hsize=15truecm
\begintt
    @DL G_G1 PROD G2;@BXIO;I;J;IREM;JREM;N1;N2;N
[1]   N_(N1_(@ROG1)[1])#N2_(@ROG2)[1] @DM I_@BXIO_0
[2]   G_(N,N)@RO0
[3]  JLOOP:J_0
[4]  CORE:G[I;J]_(G1[(I-IREM)%N2;(J-JREM)%N2]#N2)+G2[IREM_N2@ABI;JREM_N2@ABJ]
[5]   @GO(N>J_J+1)/CORE
[6]   @GO(N>I_I+1)/JLOOP
    @DL
\endtt
}

Example:

\hskip\parskip\vbox{\hsize=15truecm
\begintt
      (ZNPLUS 2) PROD ZNPLUS 10
 0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19
 1  2  3  4  5  6  7  8  9  0 11 12 13 14 15 16 17 18 19 10
 2  3  4  5  6  7  8  9  0  1 12 13 14 15 16 17 18 19 10 11
 3  4  5  6  7  8  9  0  1  2 13 14 15 16 17 18 19 10 11 12
 4  5  6  7  8  9  0  1  2  3 14 15 16 17 18 19 10 11 12 13
 5  6  7  8  9  0  1  2  3  4 15 16 17 18 19 10 11 12 13 14
 6  7  8  9  0  1  2  3  4  5 16 17 18 19 10 11 12 13 14 15
 7  8  9  0  1  2  3  4  5  6 17 18 19 10 11 12 13 14 15 16
 8  9  0  1  2  3  4  5  6  7 18 19 10 11 12 13 14 15 16 17
 9  0  1  2  3  4  5  6  7  8 19 10 11 12 13 14 15 16 17 18
10 11 12 13 14 15 16 17 18 19  0  1  2  3  4  5  6  7  8  9
11 12 13 14 15 16 17 18 19 10  1  2  3  4  5  6  7  8  9  0
12 13 14 15 16 17 18 19 10 11  2  3  4  5  6  7  8  9  0  1
13 14 15 16 17 18 19 10 11 12  3  4  5  6  7  8  9  0  1  2
14 15 16 17 18 19 10 11 12 13  4  5  6  7  8  9  0  1  2  3
15 16 17 18 19 10 11 12 13 14  5  6  7  8  9  0  1  2  3  4
16 17 18 19 10 11 12 13 14 15  6  7  8  9  0  1  2  3  4  5
17 18 19 10 11 12 13 14 15 16  7  8  9  0  1  2  3  4  5  6
18 19 10 11 12 13 14 15 16 17  8  9  0  1  2  3  4  5  6  7
19 10 11 12 13 14 15 16 17 18  9  0  1  2  3  4  5  6  7  8
\endtt
}

\end