\documentclass{article}

% \usepackage{amsmath}
% \usepackage{listings}
% \usepackage{framed}
% \usepackage{amssymb}
% \usepackage{graphicx}

\addtolength{\textwidth}{1in}
\addtolength{\evensidemargin}{-0.5in}
\addtolength{\oddsidemargin}{-0.5in}
\addtolength{\textheight}{1in}
\addtolength{\topmargin}{-0.5in}

\begin{document}

\noindent
\centerline{\Large\bf 22C:16 Homework 2}

\medskip

\centerline{\large\bf Due via ICON on Wednesday, Feb 8, 4:59 pm}

\medskip
\hrule

\medskip

\noindent
\textbf{What to submit:} Your submission for this homework will consist of three files.
One of them will be a pdf file called \texttt{homework2.pdf}. This will contain the answers
to Problems 1, 2, 3, 5, 6, and 8.
This pdf file should start with your name, section number and student ID.
The second file should be called \texttt{GCD1.py}.
This is a python program file containing the answer to Problem 4.
This file should also start with your name, section number and student ID appearing at the top
of the file as Python comments.
The third file should be called \texttt{GCD2.py}.
This is a python program file containing the answer to Problem 7.
It should start with your name, section number and student ID appearing at the top
of the file as Python comments.
You will get no credit for this homework if your files are named differently, 
have a different format (e.g., docx),
or if your files are missing your information.
 
\bigskip

\paragraph{Euclid's algorithm for the greatest common divisor.} 
The greatest common divisor (GCD) of two numbers is the largest number that 
divides evenly (i.e., without a remainder) into both numbers. 
For example, the GCD of 12 and 16 is 4. 

\begin{enumerate}
\item
Euclid's algorithm computes the GCD of two numbers. 
It is based on the principle that the GCD of two numbers does not change when the 
smaller number is subtracted from the larger number. 
For example, the GCD of 35 and 14 is also the GCD of 21 and 14. 
Explain briefly why this is true.

Hint: Suppose that d is the greatest common divisor of the two input numbers. 
Then the larger number can be written as a$\times$d for some positive
integer a and the smaller number can be written as b$\times$d for some 
positive integer b. Now consider the expression for the larger number 
minus the smaller integer.

Assume d is the greatest common divisor of the two integers such that the larger number can be written as a$\times$d for some positive
integer a and the smaller number can be written as b$\times$d for some 
positive integer b. Then their difference is (a-b)$\times$d, showing that d is also the GCD of either number and their difference.

\item 
The property described in problem 1 can be applied repeatedly until the two numbers are equal. 
This number is the GCD of the original two numbers. 
An execution tree of this algorithm for 35 and 14 is shown below. 
Construct similar trees to find the GCD of 96 and 36 and the GCD of 63 and 27.

\begin{picture}(500,250)
\put(95,205){\oval(40,20)}
\put(85,200){35,14}
\put(80,175){\line(2,3){12}}
\put(80,165){\oval(40,20)}
\put(70,160){21,14}
\put(65,135){\line(2,3){12}}
\put(65,125){\oval(40,20)}
\put(55,120){14,7}
\put(50,095){\line(2,3){12}}
\put(50,085){\oval(40,20)}
\put(44,080){7,7}
\put(75,060){\line(-5,4){18}}
\put(75,052){\line(1,0){16}}
\put(75,052){\line(0,1){16}}
\put(91,052){\line(0,1){16}}
\put(75,068){\line(1,0){16}}
\put(80,056){7}

\put(195,205){\oval(40,20)}
\put(185,200){96,36}
\put(180,175){\line(2,3){12}}
\put(180,165){\oval(40,20)}
\put(170,160){60,36}
\put(165,135){\line(2,3){12}}
\put(165,125){\oval(40,20)}
\put(155,120){36,24}
\put(150,095){\line(2,3){12}}
\put(150,085){\oval(40,20)}
\put(135,055){\line(2,3){12}}
\put(140,080){24,12}
\put(135,045){\oval(40,20)}
\put(160,020){\line(-5,4){18}}
\put(124,040){12,12}
\put(160,012){\line(1,0){16}}
\put(160,012){\line(0,1){16}}
\put(177,012){\line(0,1){16}}
\put(160,028){\line(1,0){16}}
\put(164,017){12}

\put(295,205){\oval(40,20)}
\put(285,200){63,27}
\put(280,175){\line(2,3){12}}
\put(280,165){\oval(40,20)}
\put(270,160){36,27}
\put(265,135){\line(2,3){12}}
\put(265,125){\oval(40,20)}
\put(255,120){27,9}
\put(250,095){\line(2,3){12}}
\put(250,085){\oval(40,20)}
\put(235,055){\line(2,3){12}}
\put(244,080){18,9}
\put(235,045){\oval(40,20)}
\put(260,020){\line(-5,4){18}}
\put(230,040){9,9}
\put(260,012){\line(1,0){16}}
\put(260,012){\line(0,1){16}}
\put(277,012){\line(0,1){16}}
\put(260,028){\line(1,0){16}}
\put(266,017){9}

\end{picture}


\item
Write the pseudo code for the algorithm described in problem 2. 

Hint: If you need help getting started, look at the pseudo code for problem 6.

\begin{verbatim}
    Enter the first integer as a
    Enter the second integer as b
    While a is not equal to b
        If a > b
            Subtract b from a
        else
            Subract a from b
    Output a as the GCD
\end{verbatim}


\item
Turn the pseudo code of problem 3 into a Python program that reads in two non-negative integers 
and produces their GCD. 
Type this program into a Python IDE and save it as a file called GCD1.py.  
Your program should include comments as discussed in the class lecture, 
including a section at the start 
that includes your full name, section, and student ID. 
Your program may assume that the user will input only non-negative integers and does not have 
to do any error checking, 
but it should not require the larger number to be entered first.

\item
Test your program by turning your birthdate into a decimal number.
For example, if you were born on June 9th, 1995 you would use the number 19950609. 
To answer this question, write down your birthdate and the GCD of it and the numbers 75, 144, and 390.

GCD(19950609,75)=3     GCD(19950609,144)=3      GCD(19950609,390)=3           

\vspace{1.0in}

\item
The pseudo code for a more efficient implementation of Euclid's algorithm is given below:

\begin{verbatim}
    Enter the larger number (the dividend)
    Enter the smaller number (the divisor)
    Calculate the remainder of dividing the dividend by the divisor
    While the remainder is greater than zero
        Set the dividend to the value of the divisor
        Set the divisor to the value of the remainder
        Calculate the remainder of dividing the new dividend by the new divisor
    Output the divisor as the GCD
\end{verbatim}

Describe briefly the principle (similar to the one described in problem 2) on which this algorithm is based.

This algorithm is based on the principle that if d is the GCD of two numbers, it is also the GCD of either number and 
the remainder of dividing the larger number by the smaller number. 

Assume d is the greatest common divisor of the two integers such that the larger number can be written as a$\times$d for some positive
integer a and the smaller number can be written as b$\times$d for some 
positive integer b. Then the remainder of dividing the larger number by the smaller number is (a$\times$d) -
k$\times$(b$\times$d) for some positive integer k, or (a-(k$\times$b))$\times$d,
showing that d is also the GCD of either number and their remainder.

\item 
Turn the pseudo code of problem 6 into a Python program that reads in two non-negative integers and 
produces their GCD. 
Type this program into a Python IDE and save it as a file called GCD2.py. 
Your program should include appropriate comments as described in problem 4. 
Your program may assume that the user will input only non-negative integers and 
does not have to do any error checking. 
Test your program on the same numbers you used in problem 5 to see if it returns the same GCDs.

\item
Use your program to compute the GCD of February 8, 2012 and the numbers 75, 144, and 390. 

GCD(20120208,75)=3    GCD(20120208,144)=48    GCD(20120208,390)=6

\end{enumerate}

\hrule

\end{document}
