\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{Final Exam}
\date{February 12, 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 \wedge 0)'$
\item $a \vee (a \wedge b)$
\item $a' \vee b' \vee (a \wedge b)$
\end{enumerate}
\hfill(5+5+5)

%\newpage
\item Consider 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 Which number is represented by the bit pattern $1\,100\,111$?
\item Write out the bit pattern for the representation of $5.5$.
\item What is the smallest positive number of the form
$\varepsilon=2^i$ in this floating point representation such that
$1 \oplus \varepsilon>1$?
\end{enumerate}
\hfill(5+5+5)

%\newpage

\item Construct a finite state transducer that reads an input string
which consists of letter characters, as well as \textvisiblespace\
(space) to separate words.  It outputs a string containing only the
first letters of each word.  Assume the sentence is terminated by a
single \verb+.+ (period).

\emph{Example:} Input
\begin{quote}
  \texttt{Smart people enjoy language lessons.}
\end{quote}
should produce output
\begin{quote}
  \texttt{Spell}
\end{quote}
\hfill(10)

%\newpage

\item A web service accepts file upload via ZIP archives, converts the
uploaded files to PDF, and a provides a preview of the converted
files.  Within a short period of time, the service is compromised by
hackers.  What could have possibly gone wrong, given that ZIP archives
can contain symbolic links?  \hfill(5)

%\newpage
\item
\begin{enumerate}
\item Encode the data word $1000$ using the Hamming-(8,4) code.
\item You receive the following Hamming-(8,4)-encoded message:
\[
  11100111
\]
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.
\end{enumerate}
\hfill(5+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) [right of=A]       {C};
  \node[state] (D) [above of=C]       {D};
  \node[state] (B) [below of=C]       {B};
  \node[state] (E) [below right of=C, xshift=1cm] {E};
  \node[state] (F) [above right of=C, xshift=1cm] {F};
\tikzset{mystyle/.style={-}} 
\tikzset{every node/.style={auto}} 
\path (A) edge [mystyle] node {1} (D)
      (A) edge [mystyle] node {2} (C)
      (A) edge [mystyle,swap] node {3} (B)
      (D) edge [mystyle] node {50} (F)
      (C) edge [mystyle] node {30} (F)
      (B) edge [mystyle,swap] node {1} (E)
      (C) edge [mystyle,swap] node {10} (E)
      (E) edge [mystyle,swap] node {3} (F);
\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 State the information that is contained in the link state packet
that router C sends to its neighbors, with the actual data
corresponding to the network shown.
\end{enumerate}
\hfill(10+5)

%\newpage
\item You are given the following library database schema:
\begin{quote}
\ttfamily
Borrower(BorrowerID, Name) \\
Book(BookID, Title) \\
Checkout(BorrowerID, BookID, DueDate)
\end{quote}
\begin{enumerate}
\item Underline the primary keys and dashed-underline all foreign
keys.
\item Write a query, using relational algebra or SQL, to list the
titles of all overdue books
(``$\text{\texttt{DueDate}}<\text{\texttt{TODAY}}$'') together with the
name of the person who borrowed the book.
\end{enumerate}
\hfill(5+5)
%\newpage
%(Solution ctd./scratch paper)
\end{enumerate}



\end{document}