\documentclass{article}

\usepackage{amsmath}
\usepackage{listings}
\usepackage{framed}
\usepackage{amssymb}
\usepackage{graphicx}

\addtolength{\textwidth}{1in}
\addtolength{\evensidemargin}{-0.5in}
\addtolength{\oddsidemargin}{-0.5in}
\addtolength{\textheight}{1in}
\addtolength{\topmargin}{-0.5in}

\begin{document}

\noindent
\centerline{\Large\bf 22C:16 (CS:1210) Quiz 11}

\medskip

\medskip
\hrule

\medskip
\noindent
You have 20 minutes to complete this quiz.

\begin{enumerate}
\item
Write down the output produced (via the print statement) when the function given below is called
as 

\centerline{\texttt{generalQuickSort([4, 9, 10, 2, 1, 1, 7] , 0, 6)}}

\begin{center}
\begin{framed}
\begin{verbatim}
def partition(L, first, last):
    p = first

    for current in range(p+1, last+1):
        if L[current] < L[p]:
            swap(L, current, p+1)
            swap(L, p, p+1)
            p = p + 1

    return p

def generalQuickSort(L, first, last):
    if first < last:
        p = partition(L, first, last)
        print L[first:p], L[p], L[p+1:last+1]
        generalQuickSort(L, first, p-1)
        generalQuickSort(L, p+1, last)
\end{verbatim}
\end{framed}
\end{center}


\newpage

\item Write down a length-7 list of positive integers that causes \texttt{partition} to split the list into exactly two
halves each time \texttt{partition} is called as part of the call to \texttt{generalQuickSort} on this list.
In other words, the first time \texttt{partition} is called, it is called on a length-7 list, and it should split the
list into two sublists of size 3 each.
Subsequently, \texttt{partition} will be called on two length-3 lists.
In each case, \texttt{partition} should split the given length-3 list into two length-1 lists.

\vspace{2in}


\end{enumerate}

\medskip
\end{document}
