\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{Makeup Exam}
\date{April 10, 2024}
\maketitle

% \vspace*{\fill}
% {\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} \\
% \end{tabbing}}
% \vspace*{\fill}\vspace*{\fill}



% \newpage
\begin{enumerate}
\item Are the following identities true or false?  If true, give a
proof.  If false, give a counterexample.
\begin{enumerate}
\item $a \vee (a \wedge b) = a$
\item $a \vee (a' \wedge b) = a \vee b$
\end{enumerate}
\hfill(5+5)


\item
\begin{enumerate}
\item What is the largest number you can represent in $6$-bit two's
complement binary representation?  What is the smallest such number?
\item Convert the decimal number $9.5625$ to binary.
\item Compute
\[
  (1.2 \cdot 10^{-2} - 7 \cdot 10^2) + 6.99 \cdot 10^2
\]
in \emph{decimal} floating point arithmetic with $4$
significant digits.  Can you reduce the relative error by reordering
the operations?

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


\item
\begin{enumerate}
\item Which strings does the following finite state machine accept?
\begin{center}
\begin{tikzpicture}[baseline=(q1.base)]
  \node[state, accepting, initial] (q1) {A};
  \node[state, accepting, above right of=q1] (q2) {B};
  \node[state, accepting, below right of=q1] (q3) {C};
  \node[state, below right of=q2] (q4) {D};
  \draw (q1) edge[above] node{$0$} (q2)
        (q1) edge[below] node{$1$} (q3)
        (q2) edge[bend right, left] node{$1$} (q3)
        (q3) edge[bend right, right] node{$0$} (q2)
        (q2) edge[above] node{$0$} (q4)
        (q3) edge[below] node{$1$} (q4)
        (q4) edge[loop right] node{$0,1$} (q4);
\end{tikzpicture}
\end{center}

\item State a regular expression that is equivalent to the machine
from part (a).
\item Convert the following non-deterministic finite state machine
into a deterministic one.
\begin{center}
\begin{tikzpicture}[baseline=(q1.base)]
  \node[state, initial] (q1) {A};
  \node[state, right of=q1] (q2) {B};
  \node[state, accepting, right of=q2] (q3) {C};
  \draw (q1) edge[loop above, above] node{$0,1$} (q1)
        (q1) edge[above] node{$1$} (q2)
        (q2) edge[above] node{$1$} (q3)
        (q3) edge[loop right] node{$0,1$} (q3);
\end{tikzpicture}
\end{center}
\end{enumerate}
\hfill(5+5+5)



\item 
\begin{enumerate}
\item Encode the string $0110$ as a Hamming-(8,4) encoded message.
Your answer should have a clear indication of the bit ordering of the
code word.
\item Can you design a code that can detect and correct a single-bit
error for 16 bits of data in a message of 20 bits total length?
Explain!
\end{enumerate}
\hfill(5+5)


\item
\begin{enumerate}
\item Explain the difference between a soft link and a hard link in a
file system.
\item What do you think if you find a USB drive with a Unix file
system on it which contains a file named \verb+Funny_Cat_Picture.jpg+
which is a symbolic link to \verb+/etc/passwd+?
\end{enumerate}

\hfill(5+5)


\item Consider the following router network which uses distance vector
routing.

\begin{center}
\begin{tikzpicture}[node distance=2cm,on grid,initial/.style    ={}]
  \node[state] (A)                    {A};
  \node[state] (C) [above right of=A] {C};
  \node[state] (B) [below right of=A] {B};
  \node[state] (D) [right of=C]       {D};
  \node[state] (E) [right of=B]       {E};
  \node[state] (F) [below right of=D] {F};
\tikzset{mystyle/.style={-}} 
\tikzset{every node/.style={auto}} 
\path (A) edge [mystyle] node {2} (C)
      (A) edge [mystyle] node {1} (B)
      (C) edge [mystyle] node {2} (B)
      (E) edge [mystyle] node {1} (D)
      (C) edge [mystyle] node {1} (D)
      (D) edge [mystyle] node {3} (F)
      (E) edge [mystyle] node {4} (F)
      (B) edge [mystyle] node {1} (E);
\end{tikzpicture}
\end{center}

\begin{enumerate}
\item State the optimal distance vector and routing table for
router~A.  You do not need to compute anything as the network is
simple enough to spot the answer directly.

\item Now suppose that router A is malicious and wants to intercept
traffic destined for router F.  Which routers can A prevent from
communicating with F by advertising a false link?  Assume that link
costs must be positive integers.

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


\item You are given the following relational database schema of an
online shop:
\begin{verbatim}
ITEM(ITEM_ID, DESCRIPTION)
CUSTOMER(CUSTOMER_ID, NAME, ADDRESS) 
ORDER(CUSTOMER_ID, ITEM_ID)
\end{verbatim}

\begin{enumerate}
\item Write a query, either using relational algebra or SQL, to 
find the names of all customers who bought a ``Superbike''
(\texttt{DESCRIPTION='Superbike'}).
\item In a real online shop, an order can contain any number of items.
Modify the given schema to represent such orders.
\end{enumerate}
\hfill(5+5)

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



\end{document}