%-------------------------------------------------------
% exercise2.tex
%    Exercise 2.
%
% Irit Dinur
%--------------------------------------------------------

\documentclass[12pt]{article}
%\documentclass[twocolumn]{article}
\usepackage{alltt,url,amstext,amsmath,amssymb}

\setlength{\evensidemargin}{.0in}
\setlength{\oddsidemargin}{-0.3in}
\setlength{\textwidth}{6.8in}
\setlength{\textheight}{8.7in}

\newcommand{\sep}[1]{\,\left|\, {#1} \MakeBig\right.}
\newcommand{\brc}[1]{\left\{ {#1} \right\}}
\newcommand{\pth}[1]{\left( {#1} \right)}
\newcommand{\ceil}[1]{\left\lceil {#1} \right\rceil}
\newcommand{\floor}[1]{\left\lfloor {#1} \right\rfloor}

\newcommand{\remove}[1]{}
\newtheorem{theorem}{Theorem}[section] % section
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{example}[theorem]{Example}
\newtheorem{defn}[theorem]{Definition}
\newcommand{\ctrl}{{\symbol{'136}}}
\newcommand{\examplex}[3]{
    \vspace{0.2cm}
    \noindent{\tt #1}

    \noindent{\bf \large Input:}
    {\tt #2}

    \noindent{\bf \large Output:}{\tt #3}

    \vspace{0.2cm}
}
\newcommand{\exmpinp}{\noindent{\bf \large Input:}\vspace{-0.3cm}}
\newcommand{\exmpout}{\noindent{\bf \large Output:}\vspace{-0.3cm}}
\newcommand{\MakeBig}{\rule[-.2cm]{0cm}{0.6cm}}
\newcommand{\unix}{{\tt UNIX}}
\newcommand{\dos}{{\tt DOS}}

\newcommand{\exercise}[2]{\section*{Ex {#1} ~ {#2}}}

\newcommand{\tildegen}{\protect\raisebox{-0.12cm}{\symbol{'176}}}
\newcommand{\atgen}{\symbol{'100}}
\newcommand{\email}{{\tt sariel\atgen{}math.tau.ac.il}}
\newcommand{\homepage}{{\tt http://www.math.tau.ac.il/\tildegen{}sariel/}}


% Title
\title{Introduction to Computer Science - Fall Semester 1998/9\\
   { {{Exercise}} 6}}

\author{{\bf Due:} 4/2/1999}

\date{}

\begin{document}
\maketitle

\exercise{6.1}{LARGE numbers}
The largest number fitting into a long int is 4 billion. In this
exercise we do arithmetic with $n$ digit numbers (implemented by
arrays of integers).

\begin{enumerate}
\item Write a function {\tt void add(int sum[], int a[], int b[])}
that adds two LARGE numbers. (don't forget the carry!).

\item Write a program that reads two large numbers from the user, adds
them, and prints the result on the screen. 
\end{enumerate}

For example, your output may look like this:
\begin{verbatim}
Please enter two integers with < 20 digits,
First integer:  88099005798957
Second integer:   776988213577
Sum:            88875994012534
\end{verbatim}



\exercise{6.2}{Euclid's gcd Algorithm}
Write a program that computes the gcd (greatest common divisor) of two
positive integers. 
\begin{verbatim}
int gcd(int p, int q)
{
   int r;

   if ((r = p % q) == 0)
      return q;
   else
      return (gcd(q,r));
}
\end{verbatim}
First, write a program to test the function (notice that it works only
if $p>q$). Then write and test an equivalent iterative function.


\exercise{6.3}{Merge Sort* - bonus}
Write a recursive algorithm implementing the following merge sort algorithm:

Given an array n[0..l],
\begin{enumerate}
\item Independently sort n[0..l/2-1] and n[l/2..l]
\item Merge the two arrays.
\end{enumerate}

\exercise{6.4}{Lexicographically comparing two strings}
Implement the function {\tt int strcmp(char s1[], char s2[])}, that
receives two strings and outputs: \\
0 if s1 equals s2 (as strings) \\
1 if s1 appears after s2 in the dictionary\\ 
-1 otherwise.

\end{document}
%%% Local Variables:
%%% mode: latex
%%% TeX-master: t
%%% End:
