\documentclass[12pt,a4paper]{article}

\usepackage{fullpage,amsmath,amsfonts,graphicx,enumitem}


\usepackage{tikz}
\usetikzlibrary{graphs, positioning, automata, arrows}

\begin{document}

\title{Foundations of Information Systems}
\author{Makeup Final Exam}
\date{April 16, 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 \vee 0) \wedge (a' \vee 1)$
\item $a \vee (a' \wedge b)$
\item $((a \vee b) \wedge (a' \vee c)) \wedge ((a' \wedge b') \vee (a
\wedge c'))$
\end{enumerate}
\hfill(5+5+5)

%\newpage
\item Suppose you evaluate the expression
\[
  f(x) = \frac1{x-1} - \frac1{x+1} 
\]
in floating point arithmetic for large values of $x$.
\begin{enumerate}
\item Is the absolute error large?  Is the relative error large?  Explain!
\item Can you reduce the floating point error when $x$ is large by
rewriting the expression?  Explain!
\end{enumerate}
\hfill(5+5)

%\newpage

\item Consider the following tasks.
\begin{enumerate}[label={\upshape(\roman*)}]
\item Take two arbitrary length integers as binary strings written
right-to-left and output their sum, also as a binary string
right-to-left.
\item Take two arbitrary length integers as binary strings written
left-to-right and output their sum, also as a binary string written
left-to-right.
\item Count the number of zeros in a binary string or arbitrary
length.
\item Read a binary string whose length is divisible by four and
output the parity of every group of four bits.
\end{enumerate}
Answer the following questions:
\begin{enumerate}
\item Which of the tasks above can be performed by a finite state
transducer?  Give a concise justification in each case.
\item Pick one of the tasks that can be performed by a finite state
transducer and draw the transducer that solves the task.
\end{enumerate}
\hfill(8+7)

%\newpage

\item Consider the dining philosopher's problem with six philosophers
sitting around a table.  They follow the Chandy--Misra protocol.  A
chopstick is either \emph{dirty} (``D'') or \emph{clean} (``C''), and
held by the philosopher closest to it in the following initial
configuration:
\begin{center}
\begin{tikzpicture}[every edge/.style={draw, thick}]

    % Define positions of nodes in a circle
    \foreach \i/\label in {1/1, 2/2, 3/3, 4/4, 5/5, 6/6} {
        \node[draw, circle, minimum size=1cm] (\label) at (\i*360/6:3cm) {\label};
    }

    % Add straight edges with random labels
    \draw (2) -- node[near start, above] {D} (1);
    \draw (2) -- node[near start, above left] {C} (3);
    \draw (3) -- node[very near end, left] {D} (4);
    \draw (4) -- node[near end, below] {D} (5);
    \draw (6) -- node[near end, below right] {D} (5);
    \draw (1) -- node[near end, above right] {C} (6);

\end{tikzpicture}
\end{center}
Assume, for simplicity, that the philosophers ``are running on the
same CPU'', i.e., no two actions (starting to eat, requesting a
chopstick, honoring the request for a chopstick) can happen at the
same time.  You have no control on the ordering of events, except for
the constraints imposed by the Chandy--Misra protocol.

\begin{enumerate}
\item All philosophers are currently hungry.  Which
philosopher is the first to eat?  If there is ambiguity, state all
possibilities.

\item Argue that Philosopher~3 cannot starve, i.e., eventually gets to
eat.

\item Give a high-level summary of the proof that the Chandy--Misra
protocol always works, i.e., that the philosophers cannot deadlock,
and that every philosopher who wants to eat will eventually get to
eat.

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

%\newpage
\item
How many data bits can you encode in a Hamming code of total
length 20 if additional parity is used?
\hfill(5)

%\newpage
\item Consider the following router network:
\begin{center}
\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{tikzpicture}[node distance=2.3cm,on grid,initial/.style    ={}]
  \node[state] (A)                    {F};
  \node[state] (C) [right of=A]       {D};
  \node[state] (D) [above of=C]       {C};
  \node[state] (B) [below of=C]       {E};
  \node[state] (E) [below right of=C, xshift=1cm] {A};
  \node[state] (F) [above right of=C, xshift=1cm] {B};
\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}
Use Dijkstra's algorithm to compute the shortest path from
router A to every other router in the network.
\hfill(10)

% \item In distance vector routing, the saying goes ``good news travels
% fast, bad news travels slow''.  Give a simple example which
% illustrates the issue of bad news traveling slow.
% \mbox{~~~} \hfill(5)

%\newpage
\item
\begin{enumerate}
\item Design a database schema for a (simplified) employee database.
An \emph{employee} has a name and is a member of exactly one
\emph{team}.  A team has a \emph{team leader} who is an employee and
may have additional members that are also employees.

\item Write a query, using relational algebra or SQL, to find the name
of the leader of the team where employee ``Susie Miller'' is a member.
\end{enumerate}
\hfill(5+5)
%\newpage
%(Solution ctd./scratch paper)
\end{enumerate}



\end{document}