\documentclass[11pt]{article}
\usepackage{fullpage,amsmath,amssymb}
\usepackage[pdftex]{graphicx}
\usepackage[pdftex,colorlinks=true,plainpages=false]{hyperref}
\newcommand{\fl}{\mathit{fl}}
\begin{document}
\begin{center}
{\Large COMPUTER SCIENCE 314}\\
{\Large Numerical Methods} \\
{\large SPRING 2013} \\
 ASSIGNMENT \# 1 (25 points) \\
{\small January 8}
\end{center}

\subsection*{Announcements}
\begin{itemize}
\item
\begin{tabbing}
mmmmmmmmmmmmm\=mmmmmmmmmmmmmmmmm\=mmmmmmmmmmmmmmmmm \kill
Office hours:\> Instructor \>  Teaching Assistant \\
Monday \> \> 4:00--5:00 \\
Tuesday \> 2:30--3:00 \> 4:00--5:00 \\
Wednesday \> 2:30--3:00 \> 4:00--6:00
\end{tabbing}
\item Exam 1 is Thursday, January 31st from noon to 12:25 pm.
 It covers material from this homework and Sections 1.1--1.6 of the textbook,
 except for the details of the encryption technique in Section~1.5.
 You can use only pens, pencils, and erasers;
 in particular, no written material nor electronic devices is permitted.
\end{itemize}

\subsection*{Due Thursday, January 24 at noon.}

\paragraph{Hand in hard copies}
 Type or neatly print your solutions.
 For Problem 1 include a printout of code and of results.
 For Problem 3 include a printout of code and a plot.

\begin{enumerate}

\item[0.] (essential)
 \begin{enumerate}
 \item Read course policy on cheating and acknowledge that you understand it.
 \item State whether you are using Matlab, Octave, Julia, or Python.
  (For plotting you may switch to another language.)
 \end{enumerate}
 Read Sections 1.0-1.6 of the textbook
 {\em omitting details of the encryption technique in Section~1.5.}

\item (8 points)
 Complete and execute the following M-file:
{\small\begin{verbatim}
function hw1_1()  % file name is hw1_1.m
   ...
end
function frac = contdfrac(a)
   ...
end
\end{verbatim}}\noindent
 The function {\tt contdfrac}
 returns the value of a truncated continued fraction where {\tt a} is
 a row vector containing leading coefficients $a_0$, $a_1$,\ldots, $a_{n-1}$.
 See page~6 of the textbook.
 For Euler's number e,
 the $a_k$ take the values 2, 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8,\ldots.
 The function {\tt hw1\_1} applies {\tt contdfrac} to this sequence
 for each of $n = 20, 21,\dots, 24$ and
 prints each value to 17 digits.
 {\it Note.}
 You can execute your M-file by entering {\tt hw1\_1()}.

\item (5 points) Do Exercise~1.5 from the textbook.
 By all means, create the plot, but do {\em not} turn it in.
 Instead, give a mathematical derivation of the result.
 The question may seem to be vague.
 However, only one interpretation yields a well defined slope:
 take the exponents 0, 1,\ldots, 4 (not $10^0$, $10^1$,\ldots, $10^4$)
 to be the values of vertical axis.
 Your argument need not be completely rigorous,
 but it should be {\em reasonably} convincing.
 Do not attempt to use L'H\^opital's rule!

\item (8 points) Do Exercise~1.17 from the textbook.
 You may use the following trimmed version of {\tt finitefern.m}
 as a starting point.
{\small\begin{verbatim}
function F = myfinitefern(n)  % file name is myfinitefern.m
%FINITEFERN   MATLAB implementation of the Fractal Fern.
%   Michael Barnsley, "Fractals Everywhere", Academic Press, 1993.
%   FINITEFERN(N) plots N points.

clf
shg
set(gcf,'color','white','doublebuffer','on')
darkgreen = [0 2/3 0];

p  = [ .85  .92  .99  1.00];
A1 = [ .85  .04; -.04  .85];  b1 = [0; 1.6];
A2 = [ .20 -.26;  .23  .22];  b2 = [0; 1.6];
A3 = [-.15  .28;  .26  .24];  b3 = [0; .44];
A4 = [  0    0 ;   0   .16];

x = [.5; .5];
xs = zeros(2,n);
xs(:,1) = x;
for j = 2:n
   r = rand;
   if r < p(1)
      x = A1*x + b1;
   elseif r < p(2)
      x = A2*x + b2;
   elseif r < p(3)
      x = A3*x + b3;
   else
      x = A4*x;
   end
   xs(:,j) = x;
end

plot(xs(1,:),xs(2,:),'.','markersize',1,'color',darkgreen);
axis([-3 3 0 10])
axis off
\end{verbatim}}\noindent
 Readjust the range of the x- and y-axis
 so that the triangle fills (or nearly fills) the plot, and
 apply the command ``{\tt axis equal}'' to obtain the correct shape.
 Execute your function for at least 20\,000 points.

\item (4 points)
 Do the following adaptation of Exercise~1.19 from the textbook:
\begin{quote}
{\tt A = magic(4)} is singular. Its columns are linearly dependent.
What do each of {\tt null(A)} and {\tt rref(A)} tell you about that dependence?
\end{quote}
\end{enumerate}

\subsection*{Problems not to hand in}

However, solutions will be provided.
\begin{enumerate}
\setcounter{enumi}{3}
\item
 Do Exercise~1.2 from the textbook.  Then do the following:
 Consider a rectangle such that if it is divided equally across its width
 into two smaller rectangles, the aspect ratio of each smaller rectangle
 is identical to that of its parent.
 Determine this aspect ratio mathematically.
\item
 Here are two algorithms for computing the function $f(x) = 1/x - 1$:
\begin{center}
\begin{tabular}{ll@{\qquad}ll}
Algorithm 1: & $1/x - 1$ & Algorithm 2: & $(1 - x)/x$
\end{tabular}
\end{center}
Express each of these algorithms as the composition of two functions:
$f = f_2\circ f_1$ and $f = f_4\circ f_3$.
In particular, define $f_1$, $f_2$, $f_3$, and $f_4$.

\item
 Determine values $w_1$ and $x_1$ so that
 \[\int_{-1}^1 f = w_1 f(x_1)\quad\mbox{for }f(x) = 1, x.\]

\item
 Assuming $-1 < x < 1$, solve the difference equation
 \[T_n = 2xT_{n-1} - T_{n-2}\quad\mbox{with } T_0 = 1, T_1 = x.\]

\item
 Do Exercise~1.14 from the textbook.

\item
 Do Exercise~1.32 from the textbook except for the last plot.
\end{enumerate}

\subsection*{Learning objectives}
Write programs in one of MATLAB, Octave, Julia, or Python:
\begin{itemize}
\item Read basic MATLAB code.
\item Implement algorithms using variables, selection, repetition,
 and function calls.
\item Convert a numerical value to a string of specified format:
 {\tt d}, {\tt f}, {\tt e}, {\tt g}.
\item Use array level operations to avoid explicit loops.
\item Implement a recursive algorithm.
\end{itemize}
Some basic mathematics:
\begin{itemize}
\item Define matrix concepts
 (matrix operations, determinant, inverse, eigenvalue, eigenvector)
 and reason about them.
\item Define elementary linear algebra concepts
 (linear independence, rank, null space, span, basis,
 elementary row operations, reduced row echelon form)  and reason about them.
\item Perform substitution.
\item Define what a function is. Perform operations on a function such
 a function composition and evaluation, translation, scaling.
\item Determine the limit of a sequence.
\item Solve a homogeneous constant-coefficient linear difference equation.
\item Generate a discrete probability distribution.
\end{itemize}

\end{document}