\documentclass[12pt,a4paper]{article}

\usepackage{fullpage,amsmath,amsfonts,graphicx}

\usepackage{tikz}
\usetikzlibrary{automata, positioning, arrows}

\tikzset{->, % makes the edges directed
         >=stealth', % makes the arrow heads bold
         node distance=3cm, % specifies the minimum distance between
                            % two nodes. Change if necessary.
         every state/.style={thick, fill=gray!10}, % sets the
                            % properties for each `state` node
         initial text=$ $,  % sets the text that appears on the start arrow
}

\begin{document}

\title{Foundations of Information Systems}
\author{Final Exam}
\date{February 21, 2023}
\maketitle

% \vfill
% {\baselineskip=40pt
% \begin{tabbing}\
% Student ID Number: \= \kill
% Last Name: \> \rule[-2pt]{10cm}{0.3pt} \\
% First Name:  \> \rule[-2pt]{10cm}{0.3pt} \\
% Signature: \> \rule[-2pt]{10cm}{0.3pt} \\
% %Code: \> \fbox{\rule{0pt}{1.5em}\rule{1.5ex}{0pt}}
% %\fbox{\rule{0pt}{1.5em}\rule{1.5ex}{0pt}}
% %\fbox{\rule{0pt}{1.5em}\rule{1.5ex}{0pt}}
% %\fbox{\rule{0pt}{1.5em}\rule{1.5ex}{0pt}}
% \end{tabbing}}
% \vfill



% \newpage
\begin{enumerate}

\item Determine whether the following statements are true or false.
If true, state the name of the respective Boolean algebra axiom or
elementary theorem (a proof is not required).  If false, state a
counterexample.
\begin{enumerate}
\item $a \wedge b = b \wedge a$
\item $a \vee 0 = 0$
\item $a \wedge (b \vee c) = (a \vee b) \wedge (a \vee c)$
\item $a \vee (b \wedge c) = (a \vee b) \wedge (a \vee c)$
\item $(a \vee b)' = a' \wedge b'$
\end{enumerate}
\hfill(2+2+2+2+2)
%\newpage

\item
\begin{enumerate}
\item Interpret the hexadecimal number 0xCB as an 8-bit two's
complement signed integer and convert to decimal.
\item Perform the following binary addition:
\begin{equation*}
   0110 \, 1111 + 0110 \, 1010
\end{equation*}
\item Does the result of the computation in (b) cause an overflow if
the two numbers are interpreted as (i) 8-bit unsigned integers and
(ii) as 8-bit two's complement signed integers?
\end{enumerate}
\hfill(4+3+3)
%\newpage


\item 
\begin{enumerate}
\item Perform the following computation in decimal floating point with
five significant digits:
\begin{equation*}
  (1.0000 \cdot 10^0 + 3.3333 \cdot 10^{-3})
  - 1.0000 \cdot 10^0
\end{equation*}
Suggest a different ordering of arithmetic operations that improves
the accuracy of the computation.

\item Consider the evaluation of the following expression in floating
point arithmetic:
\[
  \frac{1-(1-x)^3}{x}
\]
Identify values of $x$ for which there is a substantial growth of
relative error and suggest an alternate formula that improves accuracy
for the problematic range of $x$.
\end{enumerate}
\hfill(5+5)
%\newpage


\item Consider the following FSA:

\begin{center}
\begin{tikzpicture}[baseline=(q1.base)]
  \node[state, initial] (q1) {$A$};
  \node[state, right of=q1] (q2) {$B$};
  \node[state, right of=q2] (q3) {$C$};
  \node[state, accepting, right of=q3] (q4) {$D$}; 
  \draw (q1) edge[loop above] node{$0,1$} (q1)
        (q4) edge[loop above] node{$0,1$} (q4)
        (q1) edge[above] node{$1$} (q2) 
        (q2) edge[above] node{$0$} (q3) 
        (q3) edge[above] node{$1$} (q4);
\end{tikzpicture}
\end{center}

\begin{enumerate}
\item Which strings are recognized by this FSA?  Give a plain language
answer and also state the corresponding regular expression.

\item Convert this nondeterministic FSA into a deterministic FSA.

\end{enumerate}
\hfill(5+5)
%\newpage

\item
\begin{enumerate}
\item Process $P_1$ holds resource $R_1$ and needs resource $R_2$.
Process $P_2$ holds resource $R_2$ and needs resource $R_3$.  Process
$P_3$ holds resource $R_3$ and needs resource $R_1$.  Draw a resource
allocation graph and argue that this is a deadlock situation.

\item Now impose the following ordering constraint: \emph{A process
may hold resource $R_i$ only if it already holds all $R_j$ with $j<i$
that it needs.}

Illustrate that this rule breaks the deadlock situation in (a).  Does
this rule prevent deadlock in general?  Does it prevent starvation in
general?

\end{enumerate}
\hfill(5+5)
%\newpage

\item On a filesystem that allows soft links and hard links, you
create \verb|file_1|, hard-link \verb|file_2| to \verb|file_1|, and
soft-link \verb|file_3| to \verb|file_1|.  Then you delete
\verb|file_1|.  What happens if you access \verb|file_2|?  What
happens if you access \verb|file_3|?  Explain.  \hfill(5)
%\newpage

\item
\begin{enumerate}
\item In a RAID-5 array, one disk out of 4 has failed. The others
contain the bit sequences $0000\,1111\ldots$, $0101\,0101\ldots$,
$0100\,0010\ldots$.  Reconstruct the beginning of the bit sequence of
the failed disk.
\item An IBAN is checked by verifying that, after suitable
rearrangement, replacement of letters by number digits, and conversion
to integer, the given number modulo $97$ equals $1$.  What is the
rationale behind the convention that $1$ rather than $0$ indicates
correctness?

\end{enumerate}
\hfill(5+5)
%\newpage

\item The $(3,1)$-Hamming code is the shortest code in the Hamming
family of codes.
\begin{enumerate}
\item Explain the construction of the 3-bit codeword from the single
data bit.  Then explain how a single-bit error is corrected.
\item Draw a truth table which describes the mapping from arbitrary
3-bit messages (valid code-words possibly corrupted by single-bit
errors) to the \emph{corrected} single data bit.
\item Convert the truth table from part (b) into a Boolean algebra
expression, simplify if possible, then draw the resulting Boolean
function as an array of logic gates.
\item \emph{(Extra credit.)} Draw an FSA that reads three data bits of
a $(3,1)$-Hamming-encoded message and has two final states, $1$ and
$0$, representing the \emph{corrected} single data bit.
\end{enumerate}
\hfill(5+5+5\emph{+5})


%\newpage
%(Solution ctd./scratch paper)
\end{enumerate}



\end{document}