%\def\includemarkingscheme{YES} % uncomment to produce marking scheme


\documentclass[12pt]{article}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{lmodern}

\usepackage{algpseudocode,enumitem,calc,multicol}
\setlist[enumerate]{%
	font=\bfseries,
%	listparindent=\parindent,
}

\SetEnumitemKey{margin}{%
	leftmargin={\widthof{#1}+\labelsep},
	labelwidth={\widthof{#1}},
}
\usepackage[hyphens]{url}
\usepackage{fullpage,amssymb,epsfig,color,xspace,tikz,amsmath}
\usetikzlibrary{positioning,calc}

\usepackage{tikz}

\usepackage{listings}
\lstset{%
	language=C++,
	keepspaces=true,
	basicstyle=\small\ttfamily,
	commentstyle=\footnotesize\itshape{},
	identifierstyle=\slshape{},
	keywordstyle=\bfseries,
	numbers=left,
	numberstyle=\tiny{},
	numberblanklines=false,
	inputencoding={utf8},
	columns=fullflexible,
	basewidth=.5em,
	fontadjust=true,
	tabsize=3,
	emptylines=*1,
	breaklines,
	breakindent=30pt,
	prebreak=\smash{\raisebox{-.5ex}{\hbox{\tiny$\hookleftarrow$}}},
	escapeinside={//*}{\^^M} % Allow to set labels and the like in comments starting with //*
}


\usepackage[
	pdftitle={},%
	pdfsubject={},%
	pdfauthor={},
	hidelinks,
]{hyperref}
%\RequirePackage{pstricks,pst-node,pst-tree} % draw trees, requires using xetex
\newlength{\nodeLength}
\newcommand{\Node}{A}
\newcommand{\setnode}[1]{
  \settowidth{\nodeLength}{#1}
  \renewcommand{\Node}[1]{
    \Tcircle[name=#1]{\makebox[\nodeLength]{##1}}
  }
}
\setnode{99}
\newcommand{\quesbox}[2]{\begin{center} \framebox[.5\textwidth]{%
\raisebox{-5mm}[0mm][#1]{\begin{minipage}[t]{.45\textwidth}%
{\normalsize\sf #2}{\phantom{ans}}\end{minipage}}} \end{center}}
\newcommand{\ceil}[1]{\left\lceil#1\right\rceil}
\newcommand{\floor}[1]{\left\lfloor#1\right\rfloor}
\let\oldsection\section
\renewcommand\section[2][]{\oldsection[\thesection{}]{[#2]}}
\definecolor{typo}{rgb}{0.75,0,0}
\definecolor{care}{rgb}{0,0,0}

\setlength\parindent{0pt}
\setlength\parskip{\medskipamount}

\usepackage{todonotes}

% Nicer tables; defines \[top,mid,bottom]rule
\usepackage{booktabs}
\usepackage{multirow} % tabular cells extending over several rows
\usepackage{multicol} % tabular cells extending over several columns

\usepackage{pbox} % \pbox is a \parbox with automatic width
\usepackage{relsize} % \smaller / \larger
\usepackage{needspace} % \needspace{10\baselineskip} inserts pagebreak unless room for 10 more lines

% Add a build timestamp
\RequirePackage[yyyymmdd]{datetime}\renewcommand{\dateseparator}{-}
\newcommand\buildTimestamp{\texttt{\today~\currenttime}}

% include a file into the pdf
\usepackage{attachfile2}
\newcommand\attachsource{%
	\textattachfile[]{\jobname.tex}{%
		\begin{tikzpicture}
		\node[drop shadow, rounded corners, thick, draw=black,fill=black!10,text=black]
			{\sffamily \jobname.tex};
		\end{tikzpicture}%
	}%
}
\usetikzlibrary{shadows}


\ifdefined\includemarkingscheme
	\input{\jobname-marking-scheme}
\fi%

\newcommand\marking[1]{% %1:problemnumber
	\ifdefined\includemarkingscheme
		\markingscheme{#1}
	\fi%
}

\setcounter{section}{3}
\usepackage{graphicx}
\graphicspath{ {images/} }

\begin{document}

\maketitle

\textbf{Problem 1:}


\textbf{Description:}

We'll break the array up into two pieces of equal size, find the maximum subrange minus the smallest value sum in each part, and then take the maximum. But we also need to consider when the subrange sum straddles the middle. \newline

There are 2 cases: \newline

1) We add the maximum suffix mins the smallest value of the first half to the maximum prefix of the second half. \newline

2) We add the maximum suffix of the first half to the maximum prefix minus the smallest value of the second half. \newline

\textbf{Justification of Correctness:}

The algorithm is basically identical to the original subrange sum algorithm with the exception that the way the subrange sum which passes through the middle is calculated.

We can prove that our method is correct because we can either exclude the min element from the first half of the array or the second. If we exclude it from the first half it makes sense to find largest subrange minus one that passes through the middle in the first half (maxleftminusone variable in psuedocode) and then we would have to combine it with the largest prefix from the second half. The same also works when you remove the min element from the second half.

\begin{lstlisting}
maxsubrangesumminusone(x,lower,upper);

    if lower > upper then
	    return(0);

    if lower = upper then
	    return(max(0,x[lower]));

    m := floor( (lower+upper)/2 );

    suml := 0;
    maxleft := 0;
    minleftvalue := infinity;
    maxleftminusone := 0;
    for i := m downto lower do
	    suml := suml + x[i];
	    maxleft := max(maxleft,suml);
	    minleftvalue := min(minleftvalue, x[i])
	    maxleftminusone := max(maxleftminusone, suml - minleftvalue);

    sumr := 0;
    maxright := 0;
    minrightvalue := infinity;
    maxrightminusone := 0;
    for i := m + 1 to upper do
	    sumr := sumr + x[i];
	    maxright := max(maxright,sumr);
	    minrightvalue := min(minrightvalue, x[i])
	    maxrightminusone := max(maxrightminusone, sumr - minrightvalue);

    maxa := maxsubrangesumminusone(x, lower, m);
    maxb := maxsubrangesumminusone(x, m+1, upper);

    return(max(maxa, maxb, maxleft+maxrightminusone, maxleftminusone+maxright));
\end{lstlisting}

\textbf{Runtime and justification:}

This algorithm has the same exact runtime as the original subrange sum algorithm. It does not do any additional loops anywhere.

Letting T(n) denote the time needed for n items, this algorithm's running time satisfies the recurrence T(n) = 2 T(n/2) + O(n). This is the same recurrence as for mergesort, so T(n) = O(n log n). Much better!


\pagebreak

\textbf{Problem 2:}

\textbf{Description:}

This problem is very similar to the LCS problem. The key observation that it suffices to look at the last character of each string, still holds for the weighted LCS problem just like it held for the original LCS problem. So, instead of adding one when adding a new character to the LCS we add the weight of the new character. \newline

\textbf{Justification:}

Let X = x[1..m] and Y = y[1..n] and W be the weight a dict that maps each letter to their weights \newline

If x[m] = y[n] = a, then any maximum weight substring Z = z[1..k] of X and Y will end in z[k] = a, \textbf{given that W(a) is a positive number}. Furthermore, in this case z[1..k-1] is a maximum weight substring of x[1..m-1] and y[1..n-1]. \newline

Otherwise, x[m] ≠ y[n]. So either z[k] ≠ x[m] or z[k] ≠ y[n]. There are two cases: \newline

1) If z[k] ≠ x[m], then z[1..k] is a maximum weight substring of x[1..m-1] and y[1..n]. For if there were a common substring with larger weight of x[1..m-1] and y[1..n], it would also be the max weight substring of x[1..m] and y[1..n]. \newline

2) If z[k] ≠ y[n], then z[1..k] is a max weight substring of x[1..m] and y[1..n-1] - by the same reasoning as the case just before. \newline

\begin{lstlisting}
LCS-LENGTH-WEIGHT(x[1..m], y[1..n])

c := array(0..m,0..n) of integer;

for i := 0 to m do
	c[i,0] := 0;

for j := 1 to n do
	c[0,j] := 0;

for i := 1 to m do
	for j := 1 to n do
		if x[i] == y[j] then
			c[i,j] := max(weight[x[i]] + c[i-1,j-1], c[i-1,j-1])
		else
			c[i,j] := max(c[i-1,j], c[i,j-1]);
\end{lstlisting}

\textbf{Runtime and justification:}

This clearly costs O(mn) because it simply has 2 nested for loops which perform a constant time operation each time.

\pagebreak

\textbf{Problem 3:}

\textbf{Description:}
I was not sure how to use DP to implement the maze search algorithm so I just implemented it as a simple DFS. It traverses the maze recursively and does not revisit a node more than once given if it is on the same cur\_letter.

\textbf{Justification:}
It visits every single possible path that is at least the length of the word letters away. Therefore, if there is a path it will always find the path no matter what.


\begin{lstlisting}
def find_word(word, cur_letter, i, j, path):
	if cur_letter == len(word):
		return path

	if word[cur_letter] == M[i][j]:
		res = find_word(word, cur_letter + 1, i + 1, j, path.add(i, j))

		if(res != False):
			return res

		res = find_word(word, cur_letter + 1, i, j - 1, path.add(i, j))

		if(res != False):
			return res

		return False
	else:
		return False
\end{lstlisting}


\textbf{Runtime:}

A DFS takes O(V + E) time to run in the worst case if it visits every node and scans every single edge a single time, where V is the number of vertices and E is the number of edges.

The number of vertices is $n^2$ and the because every single vertex has only 2 edges which are right and bottom the total number of edges is $2n^2$ this means that the total running time of this algorithm should be $O(n^2)$ which is the same time that the DP algorithm would have taken.

\end{document}