\documentclass[11pt]{article}
 

\usepackage{pslatex}

\setlength {\topmargin}{0in}
\setlength {\headheight}{0in}
\setlength {\headsep}{0cm}
\setlength {\textheight}{9in}
\setlength {\oddsidemargin}{0in}
\setlength {\evensidemargin}{0in}
\setlength {\textwidth}{6.5in}
\setlength {\parskip}{0cm} 


\setlength{\parskip}{1ex plus 0.5ex minus 0.2ex}

\begin{document}
\thispagestyle{empty}

\begin{center}
{\bf \large ECE G205 Fundamentals of Computer Engineering} \\
{\bf Fall 2004} \\[0.5cm]
{\large \bf Homework 1: Due in class Wednesday September 15 2004} \\
\end{center}

{\large
\vspace*{2cm}\noindent
\begin{itemize}

\item This test contains $10$ problems. They allow you to earn
$100$ points.

\item Show your work, as partial credit can be given. You will be
graded not only on the correctness of your answer, but also on the
clarity with which you express it. \textbf{Be neat}.

\item {\bf No late submissions will be accepted.}

\item Only homework returned in a 9in $\times$ 12in envelope
will be accepted. (If you cannot find such envelope, ask the
Instructor.) Please, write your name and the class name (ECE
G205) on the envelope (write clearly, please).

\end{itemize}


\vspace*{3cm}
Write your name here:\ 
\hrulefill
}


\setcounter{page}{0}

%----------------------------------------------------------------------
\newpage

\begin{enumerate}

\item \emph{Concept: Mathematical Induction and Summations}

\begin{enumerate}

\item Prove the following:

\[
  \sum_{i = 1}^{n} i = \frac{n(n+1)}{2}.
\]

\item What is wrong with the following theorem and proof? 

\noindent
\emph{Theorem: All babies have the same color eyes.} 

\noindent
\textbf{Proof.} The base case of induction, when $n=1$, is obvious.
Suppose now that every set of $n$ babies have the same color eyes
(inductive step). Consider a set of $n+1$ babies.

We may assume by induction that the set $L$ of $n$ babies
has babies with the same color eyes.  Similarly all the $n$
babies in the set $R$ have the same color eyes.  But then,
evidently, all the $n+1$ babies in the figure have the same
color eyes, for the leftmost and the rightmost babies have
the same color eyes as the babies in between.  Therefore, by
mathematical induction, for every natural number $n$, for
every set of $n$ babies, all have the same color eyes. Since
the set of all babies is such a set, the theorem is proved.

\end{enumerate}


%----------------------------------------------------------------------
\newpage
\item \emph{Concept: Basic Set Theory}

\begin{enumerate}

\item Given two finite sets $A$ and $B$ define their union
$A \cup B$ and their intersection $A \cap B$.

\item Show that for every finite set $S$ with $n$ elements, 
the set $2^{S}$ (i.e., the set of all possible subsets of $S$) has 
$2^{n}$ elements (i.e., that there are $2^{n}$ distinct subsets of
$S$).

\item Show that there are as many odd numbers as natural numbers
(i.e., show that the set of odd number is \emph{countable}).

\end{enumerate}


%----------------------------------------------------------------------
\newpage
\item \emph{Concept: Asymptotic Notation}

\begin{enumerate}

\item Given a function $f: \mathbf{N} \rightarrow \mathbf{N}$, what is 
the meaning of $O(f(n))$?

\item \emph{True or False}. Answer the following questions.

\begin{itemize}

\item $n+3 \in \Omega(n)$
\item $n+3 \in O(n^{2})$.
\item $n+3 \in \Theta(n^{2})$.
\item $2^{n+1} \in O(n+1)$.
\item $2^{n+1} \in \Theta(2^{n})$.

\end{itemize}

\end{enumerate}


%----------------------------------------------------------------------
\newpage
\item \emph{Concept: Basic Graph Theory}

\begin{enumerate}

\item Consider the definition of \emph{undirected graph},
i.e., the couple $G=(V,E)$ where $V$ is the a set of
\emph{vertices} and $E \subseteq V \times V$.
Based on this definition define what is a \emph{tree}.

\item What is the maximum possible length of a \emph{path} in 
a tree?

\end{enumerate}


%----------------------------------------------------------------------
\newpage
\item \emph{Concept: Basic Data Structures}

\begin{enumerate}

\item Define and compare the data structures \emph{array} and 
\emph{linked lists}.

\item Describe how given two linked lists $\ell_{1} = \langle a_{1}, a_{2},
\ldots, a_{n} \rangle$  and $\ell_{2} = \langle b_{1}, b_{2}, \ldots, b_{m}
\rangle$ these can be concatenated to form a single list
$\ell_{1,2} = \langle  a_{1}, a_{2}, \ldots, a_{n}, b_{1}, b_{2}, 
\ldots, b_{m} \rangle$.

\end{enumerate}

%----------------------------------------------------------------------
\newpage
\item \emph{Concept: Sorting and Searching}

\begin{enumerate}

\item Describe and implement a sorting algorithm for 
arrays of $n$ integers.

\item Describe and implement the searching for the 
\emph{minimum} element in an array of $n$ integers. Assume 
the array is \emph{not} sorted. What changes if the array
is sorted?
 
\end{enumerate}

%----------------------------------------------------------------------
\newpage
\item \emph{Concept: Basic C commands and Their Computational Cost
(with a hint of discrete math to boot)}

\begin{enumerate}

\item 
What is the value returned
  by the following function? Express your answer as a function of
  $n$. 

\begin{verbatim}
int pesky( int n ) {
  int r = 0;
  for( int i = 1; i < n; i++ )
    for( int j = 1; j < i + 1; j++ )
      for( int k = j; k < i + j + 1; k++ )
        r++;
  return r;
}
\end{verbatim}

\item Using the ``big O'' notation give the worst-case running time 
of function \texttt{pesky}.

\end{enumerate}

%----------------------------------------------------------------------
\newpage
\item \emph{Concept: Functions and Parameter Passing in C}

\begin{enumerate}

\item What is a C function \emph{prototype}, and why is it needed?

\item Describe all possible ways of passing parameters to a C function,
and illustrate their differences.

\end{enumerate}


%----------------------------------------------------------------------
\newpage
\item \emph{Concept: Scope of identifiers in C}

\begin{enumerate}

\item What is the scope of an identifier in C?

\item For the following program, state the scope (either 
function scope, file scope, block scope, or function prototype scope)
of each of the following elements.

\begin{enumerate}

\item The variable $x$ in main.

\item The variable $y$ in cube.

\item The function cube.

\item The function main.

\item The function prototype for cube.

\item The identifier $y$ in the function prototype for cube.

\end{enumerate}

\begin{verbatim}
#include <stdio.h>
int cube( int y );
int main() {
  int x;
  for( x = 1; x <= 10;  x++ )
    printf( "%d\n", cube( x ) );
  return 0;
}
int cube( int y ) {
  return y * y * y;
}
\end{verbatim}

\end{enumerate}


%----------------------------------------------------------------------
\newpage
\item \emph{Concept: Logical Expressions in C}

\begin{enumerate}

\item In the following C logical expression:

\begin{verbatim}
( a == b ) || ( a + b > 32 )
\end{verbatim}

which of the two Boolean conditions is evaluated first? If the first
condition evaluates to true, is the second condition evaluated at all?

\item Based on the previous answer what would be a good performance
tip for those who write C code?

\item What is the value of this expression if $a$ equals $1$ and $b$
equals $2$?

\end{enumerate}
\end{enumerate}
\end{document}
