cs341a3/341-a3-q2.tex

\documentclass[a4paper]{article}

%% Language and font encodings
\usepackage[english]{babel}
\usepackage[utf8x]{inputenc}
\usepackage[T1]{fontenc}

%% Sets page size and margins
\usepackage[a4paper,top=2cm,bottom=2cm,left=2cm,right=2cm,marginparwidth=1.75cm]{geometry}

%% Useful packages
\usepackage{amsmath}
\usepackage{graphicx}
\usepackage[colorinlistoftodos]{todonotes}
\usepackage[colorlinks=true, allcolors=blue]{hyperref}

\title{CS 341 A3 Q2}
\author{Tareef Dedhar - 20621325}

\begin{document}
\maketitle
\section{Bookshelf Problem}

\subsection{Description/Correctness}
First, we assume W >= the max thickness, otherwise this is impossible to solve. So, given that, for each book, if it fits in the space left on the current shelf, shelve it. If not, start a new shelf and add it there. Repeat this until all books are shelved. This is an optimal solution because since we have a defined order of books, for any given book being shelved, there are only 2 options: shelf on the current shelf, or a new one. This algorithm chooses the former, which does not increase our target variable (number of shelves used), whenever possible. So it must be the minimal solution.

\subsection{Pseudocode}
\begin{verbatim}
Librarian(books, numShelves, spaceLeft)
{
  if (books.empty) return numShelves

  width = pop(book)

  if width <= spaceLeft
  {
    spaceLeft -= width
    return Librarian(books, numShelves, spaceLeft)
  }
  else
  {
    ++numShelves
    spaceLeft = W - width
    return Librarian(books, numShelves, spaceLeft)
  }
}

call used: Libarian(books, 0, W)
\end{verbatim}

\subsection{Time Complexity}

This is a recursive algoritm that processes 1/n books each call, so the runtime will be Theta(n * loop), where loop is the runtime of the inner loop code.
The first check made (if books is empty) should be a constant time task.
The if/else check is a numeric comparison, so this is also constant time.
Inside each if/else case, we have either 1 or 2 constant time assignment/incrementing operations, and recursive call. All of these should each (not considering the runtime of the recursive call's code, but the call itself) take constant time.

So, since we have a function comprised of constant time functions being called n times, our runtime is Theta(n)
\end{document}