\documentclass[10pt,letterpaper]{article}
\usepackage[utf8]{inputenc}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{xcolor}
\usepackage[left=1cm,right=2.5cm,top=2cm,bottom=2.5cm]{geometry}
\begin{document}
\begin{center}
\textbf{\Large CSCA48 Assignment 3}\\{\large Due: April 1, 2018. 11:59pm}
\end{center}
To account for the fact that this assignment must be done in \emph{one day}, we will make it relatively simple.
Complete 3 (or more) of the 5 problems, but only 3 will be marked by a human.
\subsection*{\texttt{match\_mask} revisited}
Our friends, the marine biologists from A08 were not too pleased with the results of your solutions for their nucleotide project.
They claimed that your \texttt{match\_mask()} function was too ugly.
Reimplement it using recursion.
\subsection*{More FormulaTrees!}
It turns out \texttt{FormulaTrees} can be used more elegantly.
Given a formula tree with the operators (\texttt{+-*\^{}/} and \texttt{\_} for ln), the leaf \(x\) being a variable, and all other possible leaves as constant, make the function \texttt{differentiate(formula\_tree)} that returns the derivative of the input.
Use leaves that have a number for a symbol to specify constants that the user has not given.
\subsection*{Sorts, Sorts, Sorts!}
Implement either \texttt{selection\_sort()} or \texttt{quick\_sort()} with the SLL used in the lectures.
If you do both, it counts as 2 of the 5.
BONUS: Do in-place quicksort.
\subsection*{For a Thousand Dollars}
Show whether or not any non-deterministic algorithm in polynomial time can be reduced to a deterministic algorithm in polynomial time.
We will give you 1K for solving this.
\color{lightgray}{\tiny $\mathbb{april fools}$}
\end{document}