\documentclass[12pt,a4paper]{article}

\usepackage{fullpage,amsmath,amsfonts,graphicx}

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

\tikzset{
}

\begin{document}

\title{Foundations of Information Systems}
\author{Makeup Final Exam}
\date{April 13, 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 \wedge c) = (a \wedge b) \wedge c$
\item $a \wedge (b \vee c) = (a \wedge b) \vee c$
\item $a \wedge (b \vee c) = (a \wedge b) \vee (a \wedge c)$
\item $a \vee (b \wedge c) = (a \vee b) \wedge (a \vee c)$
\item $(a \wedge b)' = a' \vee b'$
\end{enumerate}
\hfill(2+2+2+2+2)
%\newpage

\item
\begin{enumerate}
\item Convert the decimal number $7.1875$ to binary.
\item Using an 8-bit allocation, first convert each of the following
integers to the two's complement binary representation, perform the
operation, then convert the result back to decimal:
\[
  (-23) + 19
\]
\end{enumerate}
\hfill(5+5)
%\newpage


\item Consider the following finite state transducer:

\begin{center}
\begin{tikzpicture}[baseline=(q1.base),
                    ->, % 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
                   ]
  \node[state, initial] (q1) {$A$};
  \node[state, right of=q1] (q2) {$B$};
  \draw (q1) edge[loop above] node{$0:0$} (q1)
        (q2) edge[loop right] node{$1:1$} (q2)
        (q1) edge[bend right, below] node{$1:0$} (q2) 
        (q2) edge[bend right, above] node{$0:1$} (q1);
\end{tikzpicture}
\end{center}

\begin{enumerate}
\item Describe the function that is performed by this transducer.

\item The transducer can be used as a ``multiply-by-two'' machine.
How do you need to organize input and output of the transducer so that
it performs this function correctly?

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

\item
\begin{enumerate}
\item State the four necessary conditions for deadlock.

\item Describe the difference between deadlock and starvation.

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

\item On a filesystem that allows soft links and hard links, you
create \verb|file_1|, soft-link \verb|file_2| to \verb|file_1|, and
hard-link \verb|file_3| to \verb|file_2|.  Then you delete
\verb|file_1|.  Is there a way to still access the data?  Explain.
\hfill(5)
%\newpage

\item RAID-10, also called RAID 1+0, is a RAID arrangement in which
four (in the simplest case) disks are grouped in pairs.  Each pair is
operated as a RAID-1 (``mirroring'') pair, the two pairs are then
grouped together in a RAID-0 (``striping'') configuration.  Describe
the characteristics of a RAID-10 configuration consisting of four
identical disks, in the following categories:
\begin{enumerate}
\item storage capacity (relative to the capacity of a single
disk),
\item protection against disk failure,
\item read and write performance (compare with bare RAID-0 and bare
RAID-1).
\end{enumerate}
\hfill(3+3+4)
%\newpage

\item The following questions refer to the $(8,4)$-Hamming code with
parity, using the bit ordering convention adopted in class.

\begin{enumerate}
\item Detect double-bit errors and correct single-bit errors in the
following Hamming $(8,4)$-encoded bit streams: $00000111$ and
$10010101$.

\item Encode the message $1011$ as an $(8,4)$-Hamming code.
\end{enumerate}
\hfill(5+5)
%\newpage

\item Consider the following router network, where the numbers on each
edge indicate the cost of the link.
\begin{center}
\begin{tikzpicture}[node distance = 1.5cm and 1cm,
                    initial/.style ={}]
  \node[state] (A)                    {A};
  \node[state] (B) [below right= of A] {B};
  \node[state] (C) [above right= of B] {C};
  \node[state] (D) [below right= of C] {D};
  \node[state] (E) [above right= of D] {E};
\tikzset{mystyle/.style={-}} 
\tikzset{every node/.style={auto}} 
\path (A) edge [mystyle] node {7} (C)
      (A) edge [mystyle] node {3} (B)
      (B) edge [mystyle] node {2} (C)
      (B) edge [mystyle] node {5} (D)
      (C) edge [mystyle] node {1} (E)
      (D) edge [mystyle] node {9} (E);
\end{tikzpicture}
\end{center}
\begin{enumerate}
\item Use distance-vector routing to compute the routing tables: Fill,
for each router, a table of the form
\begin{center}
\begin{tabular}{|c|c|c|}
\hline
\multicolumn{3}{|c|}{\textbf{Router A}} \\
\hline
\textbf{Dest.}$\vphantom{1^{1^1}}$ & 
  \textbf{Next Hop} & \textbf{Cost} \\
\hline
A$\vphantom{1}^{\vphantom{\tfrac11}}$ & \hspace*{2.1cm} & \hspace*{2.1cm}\\
B && \\
C && \\
D && \\
E && \\
\hline
\end{tabular}
\begin{tabular}{|c|c|c|}
\hline
\multicolumn{3}{|c|}{\textbf{Router B}} \\
\hline
\textbf{Dest.}$\vphantom{1^{1^1}}$ & 
  \textbf{Next Hop} & \textbf{Cost} \\
\hline
A$\vphantom{1}^{\vphantom{\tfrac11}}$ & \hspace*{2.1cm} & \hspace*{2.1cm}\\
B && \\
C && \\
D && \\
E && \\
\hline
\end{tabular}
\begin{tabular}{|c|c|c|}
\hline
\multicolumn{3}{|c|}{\textbf{Router C}} \\
\hline
\textbf{Dest.}$\vphantom{1^{1^1}}$ & 
  \textbf{Next Hop} & \textbf{Cost} \\
\hline
A$\vphantom{1}^{\vphantom{\tfrac11}}$ & \hspace*{2.1cm} & \hspace*{2.1cm}\\
B && \\
C && \\
D && \\
E && \\
\hline
\end{tabular}
\begin{tabular}{|c|c|c|}
\hline
\multicolumn{3}{|c|}{\textbf{Router D}} \\
\hline
\textbf{Dest.}$\vphantom{1^{1^1}}$ & 
  \textbf{Next Hop} & \textbf{Cost} \\
\hline
A$\vphantom{1}^{\vphantom{\tfrac11}}$ & \hspace*{2.1cm} & \hspace*{2.1cm}\\
B && \\
C && \\
D && \\
E && \\
\hline
\end{tabular}
\begin{tabular}{|c|c|c|}
\hline
\multicolumn{3}{|c|}{\textbf{Router E}} \\
\hline
\textbf{Dest.}$\vphantom{1^{1^1}}$ & 
  \textbf{Next Hop} & \textbf{Cost} \\
\hline
A$\vphantom{1}^{\vphantom{\tfrac11}}$ & \hspace*{2.1cm} & \hspace*{2.1cm}\\
B && \\
C && \\
D && \\
E && \\
\hline
\end{tabular}
\end{center}
which you should update in steps until it no longer changes.

\item Now the link C--E goes down.  How many update steps does it take
until the distance-vector algorithm has converged to the new solution?
\end{enumerate}
\hfill(10+5)
%\newpage
%(Solution ctd./scratch paper)
\end{enumerate}




\end{document}