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

% {\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}}
% \vspace*{-2cm}
% \begin{center}
% \includegraphics[width=0.63\textwidth]{ascii-table.pdf}
% \end{center}


% \newpage
\begin{enumerate}

\item
\begin{enumerate}
\item Evaluate the following Boolean expression, showing all
intermediate results in your computation:
\begin{equation}
  (0 \wedge 1)' \vee (1 \wedge 1)'
\end{equation}
\item State the two distributive laws of Boolean algebra.

\item Simplify the following Boolean expression:

\begin{equation}
  (a' \wedge b \wedge c)
  \vee (a \wedge b' \wedge c')
  \vee (a \wedge b' \wedge c)
  \vee (a \wedge b \wedge c')
  \vee (a \wedge b \wedge c)
\end{equation}
% See lecture notes 01

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

\item
\begin{enumerate}
\item Translate the following computation, written in decimal integer
representation, term-by-term into binary.  Use a 6-bit two's
complement representation for the negative integers.
\begin{equation}
  23 + (- 28) = -5
\end{equation}
\item Translate the following binary rational number into decimal:
\begin{equation}
  1011.101
\end{equation}
\end{enumerate}
\hfill(5+5)
%\newpage


\item Which of the following expressions leads to unbounded growth of
the relative rounding error when computed in finite-precision (IEEE)
floating point?  Identify the value of $x \neq 0$ near which the
problem occurs.  Rewrite the expression, if necessary, in a form that
avoids this loss of accuracy.
\begin{enumerate}
\item $\displaystyle \frac{1+(1+x)^2}x$
\item $\displaystyle \frac{2x - \sqrt{x^2+1}}{\sqrt3 \, x - 1} $ 
\end{enumerate}
\hfill(5+5)
%\newpage


\item
\begin{enumerate}
\item
Write out a regular expression that recognizes strings that contain
the substring \texttt{aa} anywhere within.

\item Describe which strings are recognized by the following finite
state machine:

\begin{center}
\begin{tikzpicture}[baseline=(q1.base)]
  \node[state, initial] (q1) {$A$};
  \node[state, accepting, right of=q1] (q3) {$B$};
  \draw (q1) edge[loop above] node{$0$} (q1)
        (q3) edge[loop above] node{$0$} (q3)
        (q1) edge[bend right, below] node{$1$} (q3)
        (q3) edge[bend right, above] node{$1$} (q1);  
\end{tikzpicture}
\end{center}

\item Draw a finite state machine that checks if a given 7-bit input
corresponds to a number digit (``0'', \ldots, ``9'') encoded in ASCII.

For reference, an ASCII table is enclosed.  You may assume that the
binary input stream consists of exactly 7 bits.
\end{enumerate}
\hfill(5+5+5)

\begin{center}
\includegraphics[width=0.63\textwidth]{ascii-table.pdf}
\end{center}
%\newpage


\item Recall the ``simple language'' from class, which has
non-negative integer variables, the statements \texttt{incr(X)} and
\texttt{decr(X)}, as well as while loops of the form
\begin{verbatim}
while(X):
    loop body
\end{verbatim}
Write code in simple language that takes as input two variables
\texttt{X} and \texttt{Y} and yields a variable \texttt{Z} containing
the sum of \texttt{X} and \texttt{Y}.

It is permitted to alter the values of \texttt{X} and \texttt{Y}
as a result of this computation.
\hfill(5)
%\newpage

\item
\begin{enumerate}
\item Process $P_1$ holds resource $R_2$ and needs resource $R_1$.
Process $P_2$ holds resource $R_1$ and needs resource $R_2$.  Draw a
resource allocation graph.  Is this a deadlock situation?

\item Now suppose that there are two copies of each resource, the
second copy of $R_1$ is held by $P_3$, the second copy of $R_2$ is
held by $P_4$.  Is this a deadlock situation?
\end{enumerate}
\hfill(5+5)
%\newpage


\item The following questions refer to the $(7,4)$-Hamming code, using
the bit ordering convention adopted in class.
\begin{enumerate}
\item You receive transmissions of two $(7,4)$-Hamming code words,
$1000011 \, 0101100$, which encode one data byte.  It is known that
exactly one transmitted bit is wrong.  Which bit is it, and what is
the binary representation of the transmitted byte after the error is
corrected?
% 0011 1100
\item What is the 7-bit codeword corresponding to the data word
$0000$?

\item Show that every codeword representing a data word different
from $0000$ contains at least three ones.

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



\end{document}