\documentclass[10pt]{article}

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

\begin{document}

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

\textbf{Directions: 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.  Do not use any Python constructs which were not
introduced either in lecture, discussion section or our written
materials.}

{\bf 1.} (20) Write a generator analog of the {\bf cq} iterator class
for ``circular queues'' in our PLN on iterators and generators.  Use no
more than four lines:

\begin{Verbatim}[fontsize=\relsize{-2}]
def cq(q):
   ______________________________
   ______________________________
   ______________________________
   ______________________________
\end{Verbatim}

{\bf 2.} (20) The class {\bf atominc}, usable with the {\bf thread}
module, will store variables that can be atomically incremented without
the user having to deal him/herself with locks.  The value being stored
is in the {\bf val} member variable of the class.  For example:

\begin{Verbatim}[fontsize=\relsize{-2}]
i = atominc()
...
i.inc()
\end{Verbatim}

would add 1 to {\bf i.val} in an atomic manner.

\begin{Verbatim}[fontsize=\relsize{-2}]
print i.val
\end{Verbatim}

would print out the latest value stored (though of course it could be
``old'' by the time we get it).

We would still need to lock/unlock ourselves for operations other than
incrementing.  For instance, if we needed to perform some operations
atomically if the stored value is 8, we'd write:

\begin{Verbatim}[fontsize=\relsize{-2}]
...
i.lock()
if i.val == 8:
...
i.unlock()
\end{Verbatim}

Fill in the gaps below.  

\begin{Verbatim}[fontsize=\relsize{-2}]
class atominc():
   def __init__(self,initval):
      self.vallock = _______________
      self.val = initval
   def inc(self):
      _______________
      _______________
      _______________
   def lock(self):
      _______________
   def unlock(self):
      _______________
\end{Verbatim}

{\bf 3.} (10) Consider the primes finder code in Sec. 5 of our PLN on
threading.  Show a single line of code which we could insert somewhere
early in {\bf main()} which would result in better load balancing. 

{\bf 4.} (20) Consider the functions {\bf ones()} and {\bf ints()} presented
in an example in discussion section.  Suppose they are in the source
file {\bf s.py}, and we execute the following:

\begin{Verbatim}[fontsize=\relsize{-2}]
>>> from s import *
>>> i = ints()
>>> for j in i:
...    if j > 3: break
\end{Verbatim}

Then the execution of these statements will result in a total of
\_\_\_\_\_\_\_\_\_\_\_\_ iterators being created.

{\bf 5.} (20) The function {\bf mrgitrs()} below takes as its argument a
list of several iterators, each of which produces an ascending-order
sorted sequence (finite or infinite).  The function outputs the merge of
them, as a generator.  It is assumed that each iterator will return at
least one item.

The variable {\bf ins} will be such that {\bf ins[2]}, for instance,
will initially consist of [x,y,2], where y is {\bf itrs[2]} and x is the
first element of the sequence produced by y.  

Note that the built-in Python function {\bf min()} does work
lexicographically where appropriate; e.g.  {\bf
min([4,'abc'],[8,5],[3,200])} is [3,200].  

Fill in the gaps.  (In some cases it is possible to use fewer lines than
allotted.)  

\begin{Verbatim}[fontsize=\relsize{-2}]
def mrgitrs(itrs):
   tmp = [______________________________]
   ins = [______________________________]
   while ins != []:
      [val,itr,j] = min(ins)
      try:
         ______________________________
         ______________________________
      except ______________________________:
         ______________________________
      ______________________________
\end{Verbatim}

{\bf 6.} (10) Again consider the {\bf cq} iterator class for ``circular
queues'' in our PLN on iterators and generators.  One problem with it is
that if the input list is modified in code external to the class, the
change won't be reflected in the class' version of the list.  For
example:

\begin{Verbatim}[fontsize=\relsize{-2}]
>>> import cq
>>> x = [5,12,8]
>>> c = cq.cq(x)
>>> c.next()
5
>>> c.next()
12
>>> c.next()
8
>>> c.next()
5
>>> x[1] = 'abc'
>>> x
[5, 'abc', 8]
>>> c.next()
12
>>> c.next()
8
\end{Verbatim}

Show how to remedy this problem by changing just one portion of one line
in the original class.

{\bf Solutions:}

{\bf 1.}

\begin{Verbatim}[fontsize=\relsize{-2}]
def cq(q):
   while True:
      q[0:] = q[1:] + [q[0]]
      yield q[-1]
\end{Verbatim}

{\bf 2.}

\begin{Verbatim}[fontsize=\relsize{-2}]
class atominc():
   def __init__(self,initval):
      self.vallock = thread_allocate_lock()
      self.val = initval
   def inc(self):
      self.vallock.acquire()
      self.val += 1
      self.vallock.release()
   def lock(self):
      self.vallock.acquire()
   def unlock(self):
      self.vallock.release()
\end{Verbatim}


{\bf 3.}  For example, 

\begin{Verbatim}[fontsize=\relsize{-2}]
setcheckinterval(5)
\end{Verbatim}

(Any value less than 10 is an acceptable answer.)

{\bf 4.}  There are a total of 9 iterators created.  One determines this
simply by tracing through the recursion, and remembering that the
functions are not actually called at the time the iterators are created;
the call occurs when the {\bf .next()} functions in the iterators are
called.

{\bf 5.}  The original intended solution was

\begin{Verbatim}[fontsize=\relsize{-2}]
def mrgitrs(itrs):
   tmp = [[i.next(),i] for i in itrs]
   ins = [tmp[j]+[j] for j in range(len(itrs))]
   while ins != []:
      [val,itr,j] = min(ins)
      try:
         v = itr.next()
         ins[j] = [v,itr,j]
      except StopIteration:
         del(ins[j])
      yield val
\end{Verbatim}

However, this does not work if there is a finite iterator and it is not
the last element of {\bf itrs}.  Full credit was given if the student's
code worked in the case in which all input interators are infinite.

{\bf 6.}  

\begin{Verbatim}[fontsize=\relsize{-2}]
self.q[0:] = self.q[1:] + [self.q[0]]
\end{Verbatim}

\end{document}