\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 1}

\medskip

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

\medskip
\hrule

\medskip

\noindent
\textbf{What to submit:} Your submssion for this homework will consist of two files.
One of them will be a pdf file called \texttt{homework1.pdf}. This will contain the answers
to Problems 1, 2, 3, 4, and 6.
This pdf file should start with your name, section number, and student ID.
The second file should be called \texttt{intToTernary.py}.
This is a python program file containing the answer to Problem 5.
This file should also 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),
and if your files are missing your information.
 

\bigskip

\paragraph{Ternary numbers.} 
We are all familiar with the notion of expressing numbers in the \textit{decimal} system (i.e., base-10 system), using 
the 10 digits $0, 1, 2, \ldots, 9$.
In class, we discussed the \textit{binary} system (i.e., the base-2 system) that uses the 2 digits
0 and 1.
The decimal and binary systems for representing numbers are not the only 
number representation systems that use place values.
The same principles that are used to represent numbers in base-10 or base-2, can be used
to represent numbers in a base-$b$, for any integer $b \ge 2$.
In this homework, we will help you understand how numbers can be represented in the \textit{ternary} (i.e., base-3)
system.

First of all, place values in the ternary system are powers of 3.
So starting from the rightmost place, the place values are $3^0 = 1$, $3^1 = 3$, $3^2 = 9$, $3^3 = 27$, etc.
As you can guess, the ternary system uses 3 digits: 0, 1, and 2.
For example, consider the ternary number 20122.
The value of this number is $2 \times 3^0 + 2 \times 3^1 + 1 \times 3^2 + 0 \times 3^3 + 2 \times 3^4$.
You can check that this evaluates to $2 + 6 + 9 + 162 = 179$.
Thus the value of the ternary number 20122 expressed in the decimal system is 179.
In other words, the \textit{ternary equivalent} of 179 is 20122.


\begin{enumerate}
\item
The following is an incomplete table of the first twenty whole numbers in decimal and their ternary equivalents.
Your task is to complete this table.

\medskip

\begin{center}
\begin{tabular}{|c|c|}\hline
Decimal & Ternary\\ \hline
0 & 0\\ \hline
1 & 1\\ \hline
2 & 2\\ \hline
3 & 10\\ \hline
4 & \\ \hline
5 & \\ \hline
6 & \\ \hline
7 & \\ \hline
8 & 22\\ \hline
9 & 100\\ \hline
10 & \\ \hline
11 & \\ \hline
12 & \\ \hline
13 & \\ \hline
14 & 112\\ \hline
15 & \\ \hline
16 & \\ \hline
17 & \\ \hline
18 & 200\\ \hline
19 & \\ \hline
\end{tabular}
\end{center}

\item 
Based on what you see in this table, what can you say about the last digit of the ternary equivalent of a decimal number $n$?
In other words, make a precise observation about what the last digit of the ternary equivalent of the decimal number $n$ is, 
as a function of the value of $n$.
Answer in one sentence.

\item
The above observation helps you get the last digit of the ternary equivalent of a number $n$. To get the rest of the digits
observe a relationship between the ternary equivalent of a decimal number $n$ and the ternary equivalent of a number roughly
one-third of $n$.
State this observation precisely.
Answer in 1-2 sentences.

\item
Use the above two observations to derive an algorithm to compute the ternary equivalent of a given, nonnegative decimal integer $n$.
Write this algorithm in \textit{pseudocode} similar to the one used in class to describe the algorithm for translating
a decimal number into its binary equivalent.

\item
Turn the algorithm you wrote for the above problem into a Python program that reads as input a nonnegative decimal integer $n$ and
and produces as output the ternary equivalent of $n$.
Your program may assume that the user will input a nonnegative decimal integer and it does not have to perform an ``error checking,''
i.e., deal with unexpected situations such as when the user types as input \texttt{7.68}.
Type this program into a Python IDE and save it as a file called
\texttt{intToTernary.py}. 

Recall that instructions on how to
use the Wing IDE on DIVMS machines are posted on the course website.
Also, instructions on how to install Python and the Wing IDE onto Windows PCs and Macs are also posted
on the course website.


\item 
As a way of testing your program, use it to turn your birthdate into equivalent ternary representation.
More precisely, write down your birthdate in the form \texttt{yyyymmdd}. For example, if you were born on June 9th 1995
you would write down \texttt{19950609}.
Use your birthdate as input to your program and find its ternary equivalent.
To answer this question write down your birthdate and its ternary equivalent.
\end{enumerate}

\hrule

\end{document}
