\documentclass[11pt]{article}
\usepackage{amsthm}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{algorithm}
\usepackage{fullpage}
%\usepackage[]{algorithm2e}
\usepackage[normalem]{ulem}
\usepackage{xcolor}
\usepackage{tcolorbox}
\usepackage{latexsym}              % Additional LaTeX Symbols
\usepackage{amssymb}               % AMS Fonts
\usepackage{enumitem}
\usepackage{pseudocode}
\newcommand{\nats}{\ensuremath{\mathbb N}}
\newcommand{\Real}{\ensuremath{\mathbb R}}
\newcommand{\ind}[1]{\hspace*{#1em}}
\newcommand{\Algorithm}{{\bf Algorithm\ }}
\newcommand{\Subroutine}{{\bf Subroutine\ }}
\newcommand{\Comment}{{\bf Comment\ }}
\newcommand{\Note}{{\bf Note:\ }}
\newcommand{\Assert}{{\bf assert:\ }}
\newcommand{\Input}{{\bf Input:\ }}
\newcommand{\Output}{{\bf Output:\ }}
\newcommand{\Caveat}{{\bf Caveat:\ }}
\newcommand{\Condition}{{\bf Condition:\ }}
\newcommand{\For}{{\bf for\ }}
\newcommand{\From}{{\bf from\ }}
\newcommand{\Downto}{{\bf downto\ }}
\newcommand{\To}{{\bf to\ }}
\newcommand{\By}{{\bf by\ }}
\newcommand{\Do}{{\bf do\ }}
\newcommand{\Od}{{\bf od}}
\newcommand{\While}{{\bf while\ }}
\newcommand{\If}{{\bf if\ }}
\newcommand{\Then}{{\bf then\ }}
\newcommand{\Else}{{\bf else\ }}
\newcommand{\Elif}{{\bf elif\ }}
\newcommand{\Fi}{{\bf fi}}
\newcommand{\myAnd}{{\bf and\ }}
\newcommand{\Or}{{\bf or\ }}
\newcommand{\Break}{{\bf break}}
\newcommand{\Next}{{\bf next}}
\newcommand{\Return}{{\bf return\ }}
\newcommand{\bigO}{{O\tilde{\phantom{\imath}}}}
\newcommand{\Z}{\ensuremath{\mathbb Z}}
\newcommand{\Q}{\ensuremath{\mathbb Q\mskip1mu}}
\newcommand{\K}{{\mathsf{K}}}
\newcommand{\F}{{\mathsf{F}}}
\newcommand{\R}{{\mathsf{R}}}
\newcommand{\B}{{\mathsf{B}}}
\newcommand{\M}{{\mathsf{M}}}
\newcommand{\MM}{{\mathsf{MM}}}
\newcommand{\remove}[1]{{}}
\newcommand{\ignore}[1]{{}}
\newcommand{\rednote}[1]{{\color{red} #1}}
\newcommand{\bluenote}[1]{{\color{blue} #1}}

\newif\ifmarking
\markingfalse
\markingtrue
\newcommand{\markscheme}[1]{\ifmarking{\tcbset{colframe=red,colback=white,colupper=red}
\begin{tcolorbox}[size=small,arc=0mm]#1\end{tcolorbox}}\fi}

\newif\ifsoln
\solnfalse

\newcommand{\solution}[1]{\ifsoln{\tcbset{colframe=blue,colback=white,colupper=blue}
\begin{tcolorbox}[size=small,arc=0mm]#1\end{tcolorbox}}\fi}

%\solntrue
\markingtrue

% for typesetting code
\definecolor{commentsColor}{rgb}{0.497495, 0.497587, 0.497464}
\definecolor{keywordsColor}{rgb}{0.000000, 0.000000, 0.635294}
\definecolor{stringColor}{rgb}{0.558215, 0.000000, 0.135316}

\usepackage{xcolor}
\definecolor{stringColor}{rgb}{0.497495, 0.497587, 0.497464}
\definecolor{keywordsColor}{rgb}{0.000000, 0.000000, 0.635294}
\definecolor{commentsColor}{rgb}{0.558215, 0.000000, 0.135316}

\usepackage{listings}
\usepackage{hyperref}
\lstset{
  language=C++,
  columns=fullflexible,
  basicstyle=\ttfamily,
  commentstyle=\mycommentstyle,
  breaklines=true,
  escapechar=\$,
  rulecolor = \color{gray},
  frame=none,
  keywordstyle=\color{blue},
  stringstyle=\color{stringColor},
  commentstyle=\color{commentsColor}\textit,
  numbers = none,
  xleftmargin=0.5in
}
\hypersetup{
  colorlinks,
  linkcolor=blue,
}

\begin{document}

\noindent
{CS 341, Fall 2025 \hfill  T. Brown, É. Schost}

\begin{center}
\ifsoln{\large\bf ASSIGNMENT 3 SOLUTIONS}
\else{\large\bf ASSIGNMENT 3}
\fi
\end{center}

\ifsoln{\noindent\bf 
These solutions are for students currently enrolled in the Fall 2025 offering of CS 341 only.  You may not share or distribute them with anyone outside the course without explicit written permission from the instructors. (To do so is a violation of academic conduct.)}
\fi

\bigskip
\noindent
DUE: Wed Oct 29, 11:59 PM.
DO NOT COPY.  ACKNOWLEDGE YOUR SOURCES.

\medskip
\noindent
Please read \verb|http://www.student.cs.uwaterloo.ca/~cs341| for
general instructions and policies.

{\bf Note:} All logarithms default to base 2 (i.e.,  $\log x$ is defined as $\log_2 x$).
{\bf Note:}  ``Giving'' an algorithm means doing the four parts (i)--(iv) as described on the course web page.  %This goes without saying for all future assignments and exams.

\bigskip
\noindent



\begin{enumerate}

\item{[20 marks]} \textbf{Dynamic Programming + programming question.}
In this question, we consider special directed graphs $G=(V,E)$, where
for every vertices $a\ne b$ in $V$, the edge $(a,b)$ is in $E$, but we
have no edge of the form $(a,a)$. We will call a {\em simple cycle} a
walk $a \to b \to c \to \dots \to v \to a$, where no vertex is
repeated except for $a$.

We assume that all edges $(a,b)$ have a weight $w[a][b]$ (nonnegative integer),
and we call weight of a walk the sum of the weights of its edges. The
goal is to find a simple cycle that visits all vertices (so there are
$n$ edges on it, $n=|V|$) and has maximal weight. This problem is
NP-complete, so it is likely that there is \textit{no polytime algorithm}. 
Throughout, we use the unit cost model.

\begin{enumerate}
\item{[2 marks]} Give a brute force algorithm with runtime $O(n^k
  n!)$, $k$ constant (you have to find $k$, of course). 

\item{[7 marks]} For $a,b$ two vertices in $V$ (including the case
  $a=b$), and for $S$ a subset of $V-\{a,b\}$, consider all walks
  starting at $a$, going through all vertices of $S$ exactly once (using only vertices from $S$), and
  ending at $b$.  Let $W_{a,b,S}$ be this set, and let $w_{a,b,S}$ be
  the maximum weight of the walks in $W_{a,b,S}$. \textbf{Give a dynamic
  programming algorithm} that computes all $w_{a,b,S}$ (you may want to
  store extra information as well) \textbf{and analyze its runtime}.
  
  Don't
  forget to tell us what data structure you use for $S$, and how you
  access entries in your DP table.

  You will get full credit if the runtime is
  $O(n^\ell 2^n)$, for some constant~$\ell$.
  
\item{[1 mark]} Using the previous question, explain how to find a simple
  cycle of maximal weight. Give the runtime for the whole procedure.

\item{[10 marks]} Implement in C++ the algorithms described so far (and submit via Marmoset). The format for input files is:
  \begin{itemize}
  \item $n$ on the first line; we assume that the vertices are $0,\dots,n-1$
  \item $n$ rows, the $i$th of which (for $i=0,\dots,n-1$) gives you $w[i][0],\dots,w[i][n-1]$, separated by
    spaces ($w[i][i]$ is undefined, in our input it will be set to zero)
  \item $t \in \{0,1\}$
  \end{itemize}
  If $t=0$, run the brute-force algorithm. If $t=1$, run the DP algorithm. Then,
  the format for the output is
  \begin{itemize}
  \item 1st line: the maximal weight of a simple cycle
  \item 2nd line: a simple cycle that realizes the maximum (do not
    worry about which vertex you should choose to start, or how to
    break ties if any; any cycle that gives the maximum is OK). Print the vertices separated by spaces, with the
    first one repeated the end, and finish your line with a return.
  \end{itemize}
  Sample input: 
\begin{verbatim}
4
0 10 33 4
1 0 3 10
0 8 0 8
11 1 1 0
1
\end{verbatim}
with possible output (two lines)
\begin{verbatim}
62
0 2 1 3 0
\end{verbatim}
  You can assume $n < 32$.
\end{enumerate}

\medskip

\item{[10 marks]} \textbf{Graphs.}
 Given a directed graph $G=(V,E)$, with $|V|=n$ and $|E|=m$, and
  two vertices $a,b$ in $G$, give an algorithm that returns the number
  of {\bf shortest} walks from $a$ to $b$ in $G$. Give its runtime
  in terms of $n$ and $m$.

\end{enumerate}
\end{document}