\documentclass[10pt]{article}

\PassOptionsToPackage{numbers, sort&compress}{natbib}

%\usepackage{changepage}

\usepackage{amsmath, amssymb, amsthm}
\usepackage{algorithm}
\usepackage{mathtools}
%\usepackage{caption}
%\usepackage{subcaption}
\usepackage{float}
\usepackage{framed}
\usepackage[noend]{algpseudocode}
\usepackage{enumitem}
\usepackage{tikz}
\usepackage{thmtools, thm-restate}

\usepackage[utf8]{inputenc} % allow utf-8 input
\usepackage[T1]{fontenc}    % use 8-bit T1 fonts
\usepackage[hidelinks]{hyperref}       % hyperlinks
\usepackage{url}            % simple URL typesetting
\usepackage{booktabs}       % professional-quality tables
\usepackage{amsfonts}       % blackboard math symbols
\usepackage{nicefrac}       % compact symbols for 1/2, etc.
\usepackage{microtype}      % microtypography
\usepackage{xcolor}         % colors
\usepackage{wrapfig}
\usepackage{tabularx}
\usepackage{makecell}

% Recommended, but optional, packages for figures and better typesetting:
\usepackage{graphicx}
\usepackage{subcaption}
\usepackage{multirow}
\usepackage{fancyhdr}
\usepackage[capitalize,noabbrev]{cleveref}

\renewcommand{\O}{\mathcal{O}}

\pagestyle{fancy}
\lhead{COMSC 312}
\rhead{Spring 2026}


\theoremstyle{definition}
\newtheorem{problem}{Problem}
\newenvironment{solution}{\begin{proof}[Solution]}{\end{proof}}

\title{Homework 6: Divide and Conquer Algorithms}
\date{}

\begin{document}

\maketitle
\thispagestyle{fancy}

\noindent You may work in groups, but you must write solutions yourself. List your collaborators at the top of your submission. 

\vspace{1em}

\noindent \textbf{Instructions for submission:} Submit your homework as a single PDF file to the course Gradescope page. Either scan your \emph{legible} handwritten solutions or type them up in \LaTeX. 

\vspace{5pt}
\noindent \textbf{Setting:} Suppose you are consulting for a high-performance computing center. They have a single supercomputer that can run one job at a time and have $n$ jobs to run. Each job $i$ has a running time of $t_i > 0$ and a strict deadline $d_i$.  

\begin{problem}

    Consider the following divide-and-conquer algorithm, which takes an array $A$ of $n$ numbers as input and returns a single number. The algorithm is given below.

    \begin{algorithm}
    \caption{Mystery Divide-and-Conquer Algorithm}
    \begin{algorithmic}[1]
    \Procedure{Mystery}{$A, n$}
        \If{$n \leq 1$}
            \State \Return $A[1]$ \Comment{Base case}
        \EndIf
        
        \State $\textit{k} \gets \lfloor n / 3 \rfloor$ \Comment{Find the one-third point}
        \Statex

        \State $\textit{left} \gets \textsc{Mystery}(A[1..k], k)$ \Comment{Recur on the left third}
        \State $\textit{right} \gets \textsc{Mystery}(A[k+1..n], n-k)$ \Comment{Recur on rest}
        \Statex

        \State $\textit{total} \gets 0$ 
        \For{$i \gets 1$ to $n$}
            \State $\textit{total} \gets \textit{total} + (A[i] * \textit{left} * \textit{right})$ \Comment{Combine results}
        \EndFor
        \State \Return $\textit{total}$
    \EndProcedure
    \end{algorithmic}
    \end{algorithm}
    
    \noindent Let's analyze the running time of this algorithm. Let $T(n)$ be the running time of \textsc{Mystery} on an input of size $n$. Write down a recurrence relation for the worst-case running time $T(n)$. You may assume $n$ is a power of 3 for simplicity. \textbf{Note:} You do not need to solve the recurrence relation, just write it down.
\end{problem}

% \begin{solution}
%     This is a sample solution.
% \end{solution}

\newpage
\begin{problem}
    Suppose you have developed a new divide-and-conquer algorithm. You analyze your pseudocode and determine that its worst-case running time $T(n)$ satisfies the following recurrence relation:
    \[
    T(n) \leq 3T\left(\nicefrac{n}{2}\right) + cn^2 \quad \text{for } n > 1, \quad \text{and} \quad T(1) \leq c,
    \]
    where $c$ is a positive constant. 

    \noindent Use the recursion tree method to find a closed-form expression for an upper bound on $T(n)$ in terms of $n$. 
    \begin{enumerate}[label=(\alph*)]
        \item Find the amount of work done at the root level (level 0) of the recursion tree.
        \item Find the amount of work done at level $1$ and $2$ of the recursion tree.
        \item Find a general formula for the total work down at level $i$ of the recursion tree.
        \item Find the height of the recursion tree.
        \item Use the above to find a closed-form expression for an upper bound on $T(n)$.
    \end{enumerate}
\end{problem}

% \begin{solution}
%     This is a sample solution.
% \end{solution}


\end{document}
