\documentclass[12pt,a4paper]{article}

\usepackage{fullpage,amsmath,amsfonts,graphicx}

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

\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{Final Exam}
\date{February 17, 2026}
\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 & 0 \\
0 & 1 & 0 & 1 \\
0 & 1 & 1 & 1 \\
1 & 0 & 0 & 0 \\
1 & 0 & 1 & 0 \\
1 & 1 & 0 & 0 \\
1 & 1 & 1 & 1 \\
\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 $(60.625)_{10}$ into hexadecimal.
\item Convert $(10100.011)_{2}$ into decimal.
\item Add the $8$-bit two's complement integers $0101\,0001$ and
$0101\,1101$.  Do you get overflow?
\end{enumerate}
\hfill(5+5+5)
\item Consider the following FSA:
\begin{center}
\begin{tikzpicture}[baseline=(q1.base)]
  \node[state, initial, accepting] (q1) {$A$};
  \node[state, right=of q1, accepting] (q2) {$B$};
  \node[state, accepting, right=of q2] (q3) {$C$};
  \node[state, right=of q3] (q4) {$D$};
  \draw (q1) edge[loop above] node{$1$} (q1)
        (q2) edge[loop above] node{$0$} (q2)
        (q4) edge[loop above] node{$0,1$} (q4)
        (q1) edge[below] node{$0$} (q2)
        (q2) edge[below] node{$1$} (q3)
        (q3) edge[below] node{$0$} (q4)
        (q3) edge[bend left=45, below] node{$1$} (q1);  
\end{tikzpicture}
\end{center}
\begin{enumerate}
\item Is the input string $110100$ accepted?  List the sequence of
states that the FSA takes when parsing this string.
\item What strings does this FSA accept?  Answer in words and state a
corresponding regular expression.
\end{enumerate}
\hfill(5+5)
\item Are the following statements true or false?  Give a
\emph{brief} explanation for each.  (True/False answers without explanation
will not earn credit!)
\begin{enumerate}
\item In an operating system with dynamically managed virtual memory,
every page of memory allocated to a process has a page table entry.
\item In an operating system with dynamically managed virtual memory,
every page of memory addressable by a process has a page table entry.
\item In an operating system with dynamically managed virtual memory,
physical memory must be at least as large as the combined size of all
pages allocated to processes.
\item To avoid deadlock, it is necessary to design a system such that
none of the following four conditions may occur: mutual exclusion,
circular wait, no preemption, holding while waiting.
\item Deadlock implies Starvation. 
\item Deadlock is possible in the following resource allocation
graph. (Solid edges: Resource $R_i$ is held by Process $P_j$. Dashed
edges: Process $P_k$ is waiting for resource $R_\ell$.)
\begin{center}
\begin{tikzpicture}[
    >=stealth,
    process/.style={circle, draw, thick, minimum size=9mm},
    resource/.style={rectangle, draw, thick, minimum width=10mm, minimum height=8mm},
    edge/.style={-stealth, thick}
]

% Nodes
\node[process] (P1) {$P_1$};
\node[process, right=of P1] (P2) {$P_2$};
\node[resource, right=of P2] (R3) {$R_3$};

\node[resource, below=of P1] (R1) {$R_1$};
\node[resource, right=of R1] (R2) {$R_2$};
\node[resource, right=of R2] (R4) {$R_4$};

\node[process, below=of R1] (P3) {$P_3$};
\node[process, below=of R2] (P4) {$P_4$};
\node[resource, right=of P4] (R5) {$R_5$};

\draw[edge, dashed] (P1) -- (R1);
\draw[edge] (R1) -- (P3);
\draw[edge, dashed] (P2) -- (R1);
\draw[edge, dashed] (P2) -- (R2);
\draw[edge] (R3) -- (P2);
\draw[edge] (R4) -- (P2);
\draw[edge, dashed] (P3) -- (R2);
\draw[edge] (R2) -- (P4);
\draw[edge] (R5) -- (P4);
\draw[edge, dashed] (P4) -- (R4);

\end{tikzpicture}
\end{center}
\end{enumerate}
\hfill(2+2+2+2+2+2)


\item
\begin{enumerate}
\item Explain the good advice that \emph{RAID is not a backup}.

(Mention at least two
different aspects in your answer.)
\item If
it's not a backup, what is it good for then? 
\end{enumerate}
\hfill(5+3)
\item
\begin{enumerate}
\item The following message is received in Hamming-(8,4) encoding.
Decode, correcting a single-bit error or reporting double-bit error as
appropriate:
\begin{equation*}
  0101\,1101
\end{equation*}
Use the bit-ordering convention employed in class.

\item Take a correctly encoded Hamming-(7,4) message and flip any two
bits.  What state is the message in when you then try to decode?
\end{enumerate}
\hfill(5+5)

\item Consider the following router network:
\begin{center}
\begin{tikzpicture}
  \foreach \i [count=\n] \txt in {A, B, C, D, E, F} {
    \node[state] (n\n) at ({(\n+2)*60}:3) {\txt};
  }
  \tikzset{mystyle/.style={-}} 
  \tikzset{every node/.style={auto}} 
  \path (n1) edge [mystyle, swap] node {1} (n2)
        (n2) edge [mystyle, swap] node {1} (n3)
        (n3) edge [mystyle, swap] node {3} (n4)
        (n4) edge [mystyle, swap] node {1} (n5)
        (n5) edge [mystyle, swap] node {6} (n6)
        (n6) edge [mystyle, swap] node {2} (n1)
        (n1) edge [mystyle] node {4} (n3)
        (n1) edge [mystyle] node {5} (n5)
        (n3) edge [mystyle] node {1} (n5); 
\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)
% \newpage
% (Solution ctd./scratch paper)
\end{enumerate}



\end{document}