\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=2cm, % 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 27, 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
\begin{enumerate}
\item Derive a Boolean algebra expression for the
following binary truth table:
\begin{center}
\begin{tabular}{|ccc|c|}
\hline
$a$ & $b$ & $c$ & $z$ \\
\hline
0 & 0 & 0 & 0\vphantom{$\int^1$}\\
0 & 0 & 1 & 1 \\
0 & 1 & 0 & 0 \\
0 & 1 & 1 & 1 \\
1 & 0 & 0 & 1 \\
1 & 0 & 1 & 0 \\
1 & 1 & 0 & 1 \\
1 & 1 & 1 & 0 \\
\hline
\end{tabular}
\end{center}
\item Simplify your expression as much as possible.
\item Draw a circuit diagram representing your (possibly simplified)
expression.
\end{enumerate}
\hfill(5+5+5)

\item Show your work when answering the following questions.
\begin{enumerate}
\item Convert $(17.75)_{10}$ into binary.
\item Convert $(A1.C)_{16}$ into decimal.
\item Which integer is represented by the bit pattern 11110101
interpreted in $8$-bit two's complement representation?
\end{enumerate}
\hfill(5+5+5)

\item Consider the following non-deterministic FSA:
\begin{center}
\begin{tikzpicture}[baseline=(q1.base)]
  \node[state, initial] (q1) {$A$};
  \node[state, right=of q1, yshift=-1.5cm] (q3) {$C$};
  \node[state, accepting, right=of q3, yshift=1.5cm] (q2) {$D$};
  \node[state, right=of q1, yshift=1.5cm] (q4) {$B$};
  \draw (q1) edge[loop above] node{$0, 1$} (q1)
        (q1) edge[below] node{$1$} (q3)
        (q1) edge[above] node{$0$} (q4)
        (q3) edge[below] node{$1$} (q2)
        (q4) edge[above] node{$0$} (q2)
        (q2) edge[loop right] node{$0, 1$} (q2);  
\end{tikzpicture}
\end{center}
\begin{enumerate}
\item Is the input string $01001$ accepted?  Show the possible
transitions of the FSA step-by-step.
\item What strings does this FSA accept?  Answer in words and state a
corresponding regular expression.
\item Convert this non-deterministic FSA into an equivalent
deterministic FSA.
\end{enumerate}
\hfill(5+5+5)

\item Are the following statements true or false?  If true, give a
\emph{brief} explanation.  If false, correct or amend the statement so
that it is true.
\begin{enumerate}
\item Starvation implies deadlock.
\item Deadlock can only occur if processes are in circular waiting.
\item Deadlock may occur when several processes compete for a single
mutually exclusive resource. 
\item Imposing a total ordering on resource acquisition can prevent deadlocks. 
\item Using a smaller page size increases the size of the page tables.
\end{enumerate}
\hfill(2+2+2+2+2)

\item You are asked to set up a RAID array with four 2\,TB
disks. Usable capacity of the entire array must be at least 4\,TB.
You ponder the options RAID 5, RAID 6 and RAID 10.
\begin{enumerate}
\item Compare the three options in the categories usable capacity,
speed of small random writes, and data integrity in case of a drive
failure.
\item Make a recommendation.  If no option is superior in all
respects, state a use case that would favor each.
\end{enumerate}
\hfill(5+5)

\item
\begin{enumerate}
\item Encode the data word $1110$ as a Hamming (7,4) encoded
message. Use the bit ordering convention from class.

\item You want to encode a stream of
data bytes (1 byte = 8 bits) such that each byte to be encoded
corresponds to exactly two bytes in the encoded message stream.  What
are your options within the Hamming $(n,k)$-family of codes?  Explain
your preferred choice.
\end{enumerate}
\hfill(5+5)

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



\end{document}