\documentclass[twocolumn]{article}

\setlength{\oddsidemargin}{-0.5in}
\setlength{\evensidemargin}{-0.5in}
\setlength{\topmargin}{0.0in}
\setlength{\headheight}{0in}
\setlength{\headsep}{0in}
\setlength{\textwidth}{7.0in}
\setlength{\textheight}{9.5in}
\setlength{\parindent}{0in}
\setlength{\parskip}{0.05in}
\setlength{\columnseprule}{0.3pt}
\usepackage{fancyvrb}
\usepackage{relsize}
\usepackage{hyperref}

\usepackage{listings}

\begin{document}

Name: \_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_

Directions: {\bf Work only on this sheet} (on both sides, if needed); do
not turn in any supplementary sheets of paper. There is actually plenty
of room for your answers, as long as you organize yourself BEFORE
starting writing.

{\bf 1.} (10) Below is a generator version of the circular queue example
on p.85, plus a test program.  Fill in the blanks:

\begin{lstlisting}
def cq(q):
   while True:
      head = q[0]
      # one blank line
      # one blank line

def main():
   x = [5,12,13]
   g = cq(x)
   print g.next()  # prints 5
   print g.next()  # prints 12
   print g.next()  # prints 13
   print g.next()  # prints 5
   print g.next()  # prints 12
\end{lstlisting}

{\bf 2.} (10) Below is a function to find all subsets of size k from a set
of size n.  Here's a test:

\begin{lstlisting}
def subsets(n,k):
   # remaining code...

def main():
   n = int(sys.argv[1])
   k = int(sys.argv[2])
   g = subsets(n,k)
   for sub in g: print sub

% python subsets.py 5 2
[0, 1]
[0, 2]
[0, 3]
[0, 4]
[1, 2]
[1, 3]
[1, 4]
[2, 3]
[2, 4]
[3, 4]
\end{lstlisting}

Fill in the blanks:

\begin{lstlisting}
def subsets(n,k):
   if k == 0: 
      yield # blank
      # blank
   for i in range(n-k+1):
      # find all subsets beginning with i
      g = # blank
      for sub in g: 
         yield #blank
\end{lstlisting}

\onecolumn

{\bf Solutions:} 

{\bf 1.}

\begin{lstlisting}[numbers=left]
def cq(q):
   while True:
      head = q[0]
      yield head
      q = q[1:] +[head]

def main():
   x = [5,12,13]
   g = cq(x)
   print g.next() 
   print g.next() 
   print g.next() 
   print g.next() 
   print g.next() 

if __name__ == '__main__': main() 
\end{lstlisting}

{\bf 2.}

\begin{lstlisting}[numbers=left]
import sys
def subsets(n,k):
   if k == 0: 
      yield []
      raise StopIteration
   for i in range(n-k+1):
      # find all the subsets beginning with i
      g = subsets(n-i-1,k-1)
      for sub in g: 
         yield [i] + map(lambda u:u+i+1,sub)

def main():
   n = int(sys.argv[1])
   k = int(sys.argv[2])
   g = subsets(n,k)
   for sub in g: print sub

if __name__ == '__main__': main()


\end{lstlisting}


\end{document}