\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{Mock Exam}
\date{January 29, 2025}
\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\vfill\mbox{}


% \newpage
\begin{enumerate}

\item Simplify the following Boolean algebra expressions as much as
possible.
\begin{enumerate}
\item $(a \vee a')'$
\item $a \vee (a' \wedge b)$
\item $(a' \vee b) \wedge (a' \vee b')$
\end{enumerate}
\hfill(5+5+5)

%\newpage
\item Use a 7-bit floating-point representation where a floating point
number has 1 sign bit followed by 3 exponent bits, and 3 bits for the
significant.  According to the IEEE standard, subnormal numbers have
the exponent 000; the bias for a 3-bit exponent is $2^{3-1}-1 = 3$.
Answer the following questions:
\begin{enumerate}
\item Write out the bit pattern for the smallest positive normal
number and determine its value in decimal.
\item Write out the bit pattern for the representation of $-0.125$.
Note that the number may be subnormal!
\item Find three numbers $a$, $b$, and $c$ where
\[
  a \oplus (b \oplus c) \neq (a \oplus b) \oplus c
\]
when computed in this representation.
\end{enumerate}
\hfill(5+5+5)

%\newpage

\item Word processors can often do some spelling correction ``on the
fly''.  Construct a finite state transducer that does this in a very
simple case: change a lower-case \texttt{i} to an
upper-case \texttt{I} in sentences like
\begin{verbatim}
  i am done
  My dog and i go for a walk
  The exam i've written
\end{verbatim}
Specifically, change \texttt{i} to upper case if it is (i) the first
letter in the string or preceded by \textvisiblespace\ (space) and
(ii) followed by \textvisiblespace\ or \texttt{'} (apostrophe).

\emph{Hint:} Three states will suffice to perform this task.
% Moreover, the following sets will be helpful in specifying
% the transition rules: 
% \begin{align*}
%   A & = \{ \text{any character that is not \texttt{i} or \texttt{'}} \} \\
%   B & = \{ \text{any character that is not \textvisiblespace\ or
%   \texttt{'}} \} \\
%   C & = \{ \textvisiblespace, \text{\texttt{'}} \} 
% \end{align*}
\hfill(10)

%\newpage

\item Consider a file system that may contain hard links (i.e.,
contain inodes with a reference count larger than one).  Describe an
algorithm that copies the contents of the entire file system onto
another file system, preserving the hard links without creating
duplicate data on the target file system.

Describe your algorithm in precise language or use Python-like
pseudo-code.
\hfill(10)

%\newpage
\item You receive the following Hamming-(8,4)-encoded message.  
\[
  01101101
\]
Extract the message, if possible, correcting single-bit errors as
appropriate.  The bit-order convention is the one used in class.  Show
all steps in your work.
\hfill(5)

%\newpage
\item Consider the following router network:
\begin{center}
\begin{tikzpicture}[node distance=2.3cm,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=B]       {D};
  \node[state] (E) [right of=C]       {E};
\tikzset{mystyle/.style={-}} 
\tikzset{every node/.style={auto}} 
\path (A) edge [mystyle] node {2} (C)
      (B) edge [mystyle] node {4} (A)
      (C) edge [mystyle] node {1} (B)
      (B) edge [mystyle] node {5} (D)
      (C) edge [mystyle] node {8} (D)
      (C) edge [mystyle] node {10} (E)
      (E) edge [mystyle] node {2} (D);
\end{tikzpicture}
\end{center}
\begin{enumerate}
\item Use Dijkstra's algorithm to compute the shortest path from
router A to every other router in the network.

\item Suppose the link between C and E goes down.  How does the
network adjust to this damage and how does it affect the shortest path
from A to E?

\item In general, which routing algorithm is faster to adjust to
network damage?  Link-state or distance-vector routing?  Explain.
\end{enumerate}
\hfill(10+5+5)
% \newpage
% (Solution ctd./scratch paper)
\end{enumerate}



\end{document}