% \documentclass{article}
\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{amsmath}

\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.
When appropriate, SHOW YOUR WORK. 

{\bf 1.} (20) Fill in the blanks below.  We have a graph with adjacency
matrix {\bf adj}, so that {\bf adj[i][j]} is 1 or 0, indicating the
presence or absence of an edge from i to j.  The function returns a list
of vertices that are immediate neighbors of i.

\begin{Verbatim}[fontsize=\relsize{-2}]
def find1(adj,i):  # find 1-hop neighbors of i, excluding i
   # get number of vertices in graph
   nverts = ____________________________  
   nghbrs = []
   for j in range(nverts):
      if _________________________________________:
         _________________________________________
   return nghbrs
\end{Verbatim}

{\bf 2.} (20) The following program is run with the command line

\begin{Verbatim}[fontsize=\relsize{-2}]
python SplitIn2.py f n f1 f2
\end{Verbatim}

It splits the file {\bf f} into files {\bf f1} and {\bf f2}, where {\bf
f1} consists of the first {\bf n} bytes of {\bf f} and {\bf f2} is the
remainder.  Fill the blanks.  Make sure it is platform-independent.

\begin{Verbatim}[fontsize=\relsize{-2}]
import sys, os

def main():
   f = open(_______________________________)
   n = int(sys.argv[2])
   f1 = open(_______________________________)
   f2 = open(_______________________________)
   firstn = f.read(_______________________________)
   ________________________________
   f1.close()
   nbytesremaining = _____________________________ - n
   therest = _____________________________
   f2.write(therest)
   f2.close()

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

{\bf 3.} The following code was meant to produce an {\bf n}x{\bf n}
matrix of 1s:

\begin{Verbatim}[fontsize=\relsize{-2}]
all1s = n*[1]  # a row of 1s
x = n*all1s  # n rows of 1s
\end{Verbatim}

\begin{itemize}

\item [(a)] (10) The above code fails to meet its goal.  Show how to fix this by
modifying the first statement.

\item [(b)] (10) Explain why is the above code, even after fixing, probably 
is not a good idea.

\end{itemize}

{\bf 4.} (20) The function {\bf dsort()} below will ``sort'' a dictionary
{\bf d}, returning a list of two-element lists.  Each of the latter is
key-value pair from {\bf d}.  Sorting is according to keys.  For example:

\begin{Verbatim}[fontsize=\relsize{-2}]
>>> dsort({'abc':12,'sailing':'away','aa':15})
[['aa', 15], ['abc', 12], ['sailing', 'away']]
\end{Verbatim}

Fill in the blanks:

\begin{Verbatim}[fontsize=\relsize{-2}]
def dsort(d):
   dk = _________________________________
   dk.sort()
   return map(__________________________________)
\end{Verbatim}

{\bf 5.} (20) Fill in the blanks in {\bf rgmx()}, a function that returns
both the maximum value in a list and the index for that value (or {\it
some} index, in the case of ties).  For example, {\bf rgmx([5,12,13,8])}
will return [13,2].

\begin{Verbatim}[fontsize=\relsize{-2}]
def rgmx(x):
   xandi = ___________(x,____________________)
   return max(xandi) 
\end{Verbatim}

{\bf Solutions:}

{\bf 1.}

\begin{Verbatim}[fontsize=\relsize{-2}]
len(adj)
adk[i][j] == 1 and i != j
nghbrs.append(j)
\end{Verbatim}

{\bf 2.}

\begin{Verbatim}[fontsize=\relsize{-2}]
sys.argv[1],'rb'
sys.argv[3],'w'
sys.argv[4],'w'
n
f1.write(firstn)
os.path.getsize(f.name) 
f.read(nbytesremaining)
\end{Verbatim}

A better way would be to bypass computing {\bf nbytesremaining} and then
simply call {\bf f.read()}.

{\bf 3.a}

\begin{Verbatim}[fontsize=\relsize{-2}]
add1s = [n*[1]]
\end{Verbatim}

{\bf 3.b}  The problem is that you would get {\bf n} copies of the
object pointed to by the reference {\bf all1s}.  If you then changed one
element of the matrix, the whole column would change.

{\bf 4.}  

\begin{Verbatim}[fontsize=\relsize{-2}]
d.keys()
lambda z: [z,d[z]],dk
\end{Verbatim}

{\bf 5.}

\begin{Verbatim}[fontsize=\relsize{-2}]
zip
range(len(x))
\end{Verbatim}

\end{document}