\documentclass[10pt,a4paper]{amsart}
\usepackage[latin1]{inputenc}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{tabularx}
\author{Name: \underline{\hspace{5cm}}}
\title{CSC 340 Homework 1}
\begin{document}
\maketitle
\setlength{\parindent}{0pt}
\setlength{\parskip}{0.2cm}
You must show work that justifies your answers for each of the following problems. Submit by email when done. This homework is due
Friday at the end of Week 3.
\begin{center}\underline{\hspace{6cm}}
\end{center}
{\bf 1.} Consider the following algorithmic problem:
\begin{tabularx}{\textwidth}{lX}
{\bf Input}: & An array $a[0..N-1]$ of integer and an integer $X$.\\ \\
{\bf Output}: & The least integer $k$ such that $a[k] = X$, if such a $k$ exists, or -1 otherwise.\\
\end{tabularx}
Consider the following algorithm for solving this problem.
\begin{quote}
\begin{verbatim}
int k = 0;
bool found = false;
// 0.
while (k < N)
{
// 1.
if (a[k] == X)
{
// 2.
found = true;
// 3.
break;
}
k = k + 1;
// 4.
}
// 5.
\end{verbatim}
\end{quote}
Answer the following questions about this algorithm:
\begin{enumerate}
\item What is the strongest statement (invariant) involving the variables {\tt k} and {\tt found} that you can say holds at the point labeled 0?
\item What is the strongest statement (invariant) involving the variables {\tt k} and {\tt found} that you can say holds at the point labeled 1?
\item What is the strongest statement (invariant) involving the variables {\tt k}, {\tt found}, and elements of the array {\tt a[ ]} that you can say holds at the point labeled 2?
\item What is the strongest statement (invariant) involving the variables {\tt k}, {\tt found}, and elements of the array {\tt a[ ]} that you can say holds at the point labeled 3?
\item What is the strongest statement (invariant) involving the variables {\tt k}, {\tt found}, and elements of the array {\tt a[ ]} that you can say holds at the point labeled 4?
\item What is the strongest statement (invariant) involving the variables {\tt k}, {\tt found}, and elements of the array {\tt a[ ]} that you can say holds at the point labeled 5?
\end{enumerate}
{\bf 2.} Consider the following program fragment, where we assume that
{\tt N} is a positive integer.
\begin{quote}
\begin{verbatim}
int k = 0;
while (k < N)
{
if (k % 2 == 0)
{
k --;
}
else
{
k = k + 2;
}
}
\end{verbatim}
\end{quote}
Prove that the loop in this program fragment will eventually terminate, or give an example of an input value for {\tt N} that will make the program run forever.
{\bf 3.} Consider the following program fragment, where we assume that
{\tt N} is a positive integer.
\begin{quote}
\begin{verbatim}
int k = 0;
while (k != N)
{
if (k % 2 == 0)
{
k --;
}
else
{
k = k + 2;
}
}
\end{verbatim}
\end{quote}
Prove that the loop in this program fragment will eventually terminate, or give an example of an input value for {\tt N} that will make the program run forever.
{\bf 4.} Give two different pairs of values for $(N, K)$, where
$N$ is a positive integer and $K$ is a positive real number, such that
$$ n^3 + 70n^2 + 100 \le K \left( n^3 + 10n\right)$$
for all $n \ge N$.
{\bf 5.} Prove that $ n^3 \in \Omega(100n^2 + 500n + 10).$
{\bf 6.} A certain algorithm performs $n$ iterations while solving
a problem instance of size $n$. Each such iteration requires $n^2$
basic operations.
\begin{enumerate}
\item How many basic operations does the algorithm perform?
\item Can you tell for certain that the problem is the complexity class O$(n^4 + n^2)$?
\item Can you tell for certain that the problem is the complexity class $\Omega(n^2)$?
\end{enumerate}
{\bf 7.} A certain algorithm performs $n$ iterations while solving
a problem instance of size $n$. For each $k = 1, \ldots, n$,
the algorithm performs $2k-1$ basic steps. What is the total number of basic steps performed by the algorithm?
{\bf 8.} Is the problem of determining whether an array of strings is sorted, where the strings have a maximum length of 100 characters NP-Complete?
Justify your answer.
\end{document}