\documentclass[12pt,a4paper]{article}

\usepackage{fullpage,amsmath,amsfonts,graphicx}

\usepackage{tikz}
\usetikzlibrary{automata, positioning, arrows, shapes, calc}
\usetikzlibrary{decorations.pathreplacing,calligraphy}

\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{Makeup Exam}
\date{April 7, 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 Are the following Boolean algebra expressions true or false?  If
true, provide a proof.  If false, provide a counterexample.
\begin{enumerate}
\item $a' \vee b' = (a \vee b)'$
\item $a \vee (a \wedge b) = a$
\item $(a \wedge c) \vee (a \wedge b \wedge c) = a \wedge c$
\end{enumerate}
\hfill(5+5+5)

%\newpage
\item \textsf{bfloat16} is a 16-bit floating point format where the
bits are allocated as follows.
\begin{center}
\begin{tikzpicture}[
  bit/.style={draw,
              minimum width=0.5cm,
              minimum height=0.7cm,
              align=center},
  lab/.style={font=\small}
]

% --- Bit boxes: bfloat16 = 1 sign, 8 exponent, 7 fraction ------------------
% We'll place 16 boxes from left (MSB) to right (LSB15 ... b0
\def\bitsep{0.85} % <--- smaller = closer together

\foreach \i [evaluate=\i as \x using (15-\i)*\bitsep] in {15,14,...,0} {
  \node[bit] (b\i) at (\x,0) {\i};
}

\def\bracegap{2pt} % space between boxes and braces (increase if
                   % needed)
                   
% --- Field grouping braces --------------------------------------------------
\draw[{}-{},decorate, decoration={calligraphic brace, amplitude=5pt}, thick]
  ([yshift=\bracegap]b15.north west) -- ([yshift=\bracegap]b15.north east)
  node[midway, above=6pt, lab] {sign};

\draw[{}-{},decorate, decoration={calligraphic brace, amplitude=5pt}, thick]
  ([yshift=\bracegap]b14.north west) -- ([yshift=\bracegap]b7.north east)
  node[midway, above=6pt, lab] {exponent (8 bits)};

\draw[{}-{},decorate, decoration={calligraphic brace, amplitude=5pt}, thick]
  ([yshift=\bracegap]b6.north west) -- ([yshift=\bracegap]b0.north east)
  node[midway, above=6pt, lab] {significant (7 bits)};

\end{tikzpicture}
\end{center}
Per IEEE\,754 convention, the exponent bias is $127$.

\begin{enumerate}
\item Convert the data word
\[
  1\,01111111\,0100000
\]
from \textsf{bfloat16} to decimal.
\item What is the maximal relative error when converting an arbitrary
decimal to \textsf{bfloat16}?

(You may state your answer as a
fraction or in terms of a power of $2$; no need to convert to
decimal.)
\item What is special about \textsf{bfloat16} and why is it getting
popular in neural network architectures?
\end{enumerate}
\hfill(5+5+5)
%\newpage

\item Draw a deterministic (!) finite state machine that accepts input
strings if and only if they contain the substring $1010$.
\hfill(10)
%\newpage

\item
\begin{enumerate}
\item In a RAID-5 array, one disk out of 5 has failed.  The others
contain the bit sequences $11111111\ldots$, $01101000\ldots$,
$00000000\ldots$, $11100001\ldots$.  Reconstruct the beginning of the
bit sequence of the failed disk.
\item The RAID-5 array consists of disks with a capacity of 1\,TB each
and a rate of \emph{unrecoverable read errors} (URE), defined as the
the probability of a single bit error during read, of
$\text{URE} = 10^{-14}$.  Assuming that single-bit errors are
statistically independent, estimate the probability that the array can
be fully recovered.

(Simplify your answer as much as reasonably possible, but you do not
need to evaluate to a number; take
$1\,\mathrm{TB} = 2^{40} \, \mathrm{B}$.)

\item Assume that the hard drives have a native block size of
$4\,\mathrm{kB} = 2^{12}\,\mathrm{B}$.  A block can only be read
fully, or not at all.  What is the rate of unrecoverable block reads?
Use this number to explain why adding another disk and running the
array in RAID-6 mode makes the recovery process much safer.
\end{enumerate}
\hfill(5+5+5)
%\newpage
\item Encode the data word
\[
  1001\,0111\,010
\]
in Hamming-(16,11) encoding.

Use the bit-ordering convention employed
in class.
\hfill(5)

%\newpage
\item Give a simple example of a network with distance vector routing
that illustrates the saying ``good news travels fast, bad news travels
slow''.

Your answer should provide details of a ``good news'' and a ``bad
news'' event.
\hfill(10)
%\newpage

\item You are given the following simplified library database schema:
\begin{quote}
\ttfamily
Book(BookID, Title, Author) \\
Patron(PatronID, Name, Address) \\
Loan(DueDate, PatronID, BookID) \\
\end{quote}
\begin{enumerate}
\item Underline the primary keys and dashed-underline all foreign
keys.
\item 
Write the following queries either in relational algebra or in SQL.
\begin{enumerate}
\item Find the names of all patrons who have borrowed at least one
book. 
\item Find the names of all authors that patron Jane Smith is
currently reading.
\end{enumerate}
\end{enumerate}
\hfill(3+3+4)
%\newpage

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

\end{document}