\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 20, 2024}
\maketitle

% \vspace*{\fill}
% {\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} \\
% \end{tabbing}}
% \vspace*{\fill}\vspace*{\fill}


\begin{enumerate}
\item Are the following identities true or false?  If true, give a
proof.  If false, give a counterexample.
\begin{enumerate}
\item $(a \wedge b)' \wedge c = (a \vee b) \vee c'$
\item $((a \vee b) \wedge c)' = (a \wedge c)' \wedge (b \wedge c)'$
\end{enumerate}
\hfill(5+5)


\item
\begin{enumerate}
\item Convert the decimal number 433 to hexadecimal.
\item Add the 4-bit two's complement binary numbers $1110$ and $1011$.
\item Confirm your result by converting all three numbers
from (b) to decimal.
\item How do you detect overflow when adding two's complement binary
numbers?
\end{enumerate}
\hfill(5+5+5+5)


\item
\begin{enumerate}
\item Draw a finite state machine that can recognize whether a 3-bit
binary string is a palindrome, i.e., reads the same backwards as
forwards.
\item State a regular expression that is equivalent to the machine
from part (a).
\item Is it possible to design a finite state machine that recognizes
palindromes of arbitrary length?  Explain!
\end{enumerate}
\hfill(5+5+5)


\item The following bit strings of a Hamming-(8,4) encoded message are
received. Correct single-bit errors or detect double-bit errors as
appropriate.
\begin{enumerate}
\item $11001011$
\item $00010100$
\end{enumerate}
\hfill(5+5)


\item Suppose you have a file \verb+data_A+.  You create a hard link
\verb+data_B+ and a soft link \verb+data_C+ to it.  Now you delete
\verb+data_A+.  Is the data lost?  Can you still access it via
\verb+data_B+?  Via \verb+data_C+?  \hfill(5)


\item Consider the following router network which uses distance vector
routing.

\begin{center}
\begin{tikzpicture}[node distance=2cm,on grid,initial/.style    ={}]
  \node[state] (A)                    {A};
  \node[state] (C) [above right of=A] {C};
  \node[state] (B) [below right of=A] {B};
  \node[state] (D) [right of=C]       {D};
  \node[state] (E) [right of=B]       {E};
  \node[state] (F) [below right of=D] {F};
\tikzset{mystyle/.style={-}} 
\tikzset{every node/.style={auto}} 
\path (A) edge [mystyle] node {2} (C)
      (A) edge [mystyle] node {1} (B)
      (C) edge [mystyle] node {2} (B)
      (E) edge [mystyle] node {1} (D)
      (C) edge [mystyle] node {1} (D)
      (D) edge [mystyle] node {3} (F)
      (E) edge [mystyle] node {4} (F)
      (B) edge [mystyle] node {1} (E);
\end{tikzpicture}
\end{center}

\begin{enumerate}
\item State the optimal distance vector and routing table for
router~C.  You do not need to compute anything as the network is
simple enough to spot the answer directly.

\item Now suppose that router C is malicious and wants to cut router F
off the network.  Can it do this?  If so, what distance vector does it
need to broadcast to its neighbors to attract all traffic destined
for~F?
\end{enumerate}
\hfill(5+5)


\item Suppose you have three identical disks. The most natural way to
create redundant storage from these three disks is a RAID-5 array.
Your remember from class that RAID-5 with large capacity drives has a
high probability of hitting an unrecoverable error during rebuild
after a single-drive failure, so you ponder if it's worth investing in
a fourth disk and using RAID-10 (``stripe of mirrors'') instead.  To
help making this decision, rate the performance of the four-disk
RAID-10 \emph{relative} to the three-disk RAID-5, with a brief
explanation, in each of the following categories:
\begin{enumerate}
\item Usable capacity (\emph{not} raw capacity!)
\item Read speed when sequentially reading a large file
\item Write speed when sequentially writing a large file
\item Write speed when writing random blocks
\item Probability of hitting an error during rebuild after a
single-drive failure
\end{enumerate}
\emph{Extra credit:} Based on these numbers, write a recommendation
whether or not to purchase the extra drive and use it in RAID-10
configuration.
\hfill(2+2+2+2+2\textit{+5})

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



\end{document}