\documentclass{article}

\usepackage{url}

\newcommand{\code}{\texttt}
\newcommand{\urln}[1]{\vskip -1pc \hskip .25in \url{#1} \vskip 0pc}
\newcommand{\cmd}[1]{\vskip -1pc \hskip .25in \texttt{#1} \vskip 0pc}

\setcounter{tocdepth}{2}
\setcounter{secnumdepth}{2}

\setlength{\topmargin}{-3pc}
\setlength{\textheight}{9in}
\setlength{\oddsidemargin}{0pc}
\setlength{\evensidemargin}{0pc}
\setlength{\textwidth}{6.5in}
\setlength{\parskip}{1pc}
\setlength{\parindent}{0in}

\begin{document}

\section*{Notes for future 6.006 staff}

This is a repository of knowledge/suggestions for future TAs and
professors of 6.006. We hope it will help to improve the class even
more in the future.

Matthew Ng and I are the principal authors of this document. The two
of us, as well as Prof. Toledo, have been on the 6.006 staff for two
semesters (Fall 2008 and Spring 2009); all of us are now preparing to
leave MIT. We've really enjoyed teaching this class, and so we're
hoping to pass on what knowledge we've accumulated.

This document ended up growing longer than I anticipated; sorry about
that. Section \ref{admin-stuff} is the most important; it explains
where to find all the course materials, etc. The later sections aren't
necessary, but I think they'll probably prove informative, if you
choose to read them. They pertain to more specific aspects of the
course, and are a little more opinionated.

Please don't hesitate to write if you have questions for us.

---Jason Juang, \code{juang@alum.mit.edu}, May/June 2009

\subsection*{Spring 2009 staff}
\begin{itemize}
% add your contact info if you want
\item Prof. Sivan Toledo
\item Prof. Alan Edelman
\item Jason Juang, \code{juang@alum.mit.edu}
\item Matthew Ng, \code{matthew.ng@alum.mit.edu}
\item Chieu Nguyen
\item Rishabh Singh
\item Rob Speer
\end{itemize}

{
\parskip 0pc
\tableofcontents
}


\section{Where to find things}
\label{admin-stuff}

\subsection{CSAIL AFS Locker}

You will need to be a member of the 6.006 group to access the
locker. Have somebody add you to the CSAIL group:
  \cmd{pts adduser YOUR\_USER\_NAME 6.006}
Profs. Rivest, Devadas, Demaine, or Sudan should be able to do
it. (You might also find it useful to have access to the 6.046
locker.)

The 6.006 AFS locker is located at
  \urln{/afs/csail.mit.edu/proj/courses/6.006/}

Details of the layout of the locker are described in the \code{README}
file, inside the main directory.

There is an Athena AFS locker for this course, as well, but there
should be nothing in there. The website there just redirects to the
CSAIL website.

\subsection{Course website}

The files for the website are located at 
  \urln{/afs/csail.mit.edu/proj/courses/6.006/www/data/}
and the site is accessible at
  \urln{http://courses.csail.mit.edu/6.006/}

Each year's website is stored in its own directory. All of the S'09
website was hosted on a MediaWiki hosted on
\url{http://scripts.mit.edu/}, as were portions of earlier
websites. XML backups of these wikis are stored on the AFS locker.

We password-protected the \code{solutions} and
\code{protected} directories, and gave out the password in
class. See the \code{.htaccess} file in each directory for details.

\subsubsection{Website passwords}

The username was \code{6.006} in all semesters.

\begin{itemize}
\item F2007: \code{algorithms-rule!}
\item S2008: \code{python-dictionaries}
\item F2008: \code{sublinear-time}
\item S2009: \code{theta-nlogn}
\end{itemize}

\subsection{Mailing lists}

Have somebody add you to the Athena group so you can manage the lists:
  \cmd{blanche 6.006-staff -a YOUR\_USER\_NAME}

We own the following Athena mailing lists (all \code{@mit.edu}):
{\parskip 0pt
\begin{itemize}
\item \code{6.006-students}, \code{6006-staff}: the professors and TAs
\item \code{6.006-tas}, \code{6006-tas}: just the TAs
\item \code{6.006-students}, \code{6006-students}: all students in the class, as well as the TAs
\item \code{6.006-help}: for students to e-mail with questions about problem sets, etc.---contained the staff plus the LA
\end{itemize}
}

All lists are owned by the group \code{6.006-staff}.


\subsection{Subversion repository}

The svn repository lives in the CSAIL AFS locker, at
  \urln{/afs/csail.mit.edu/proj/courses/6.006/repository/}
and is also accessible, with appropriate authentication, at
  \urln{https://svn.csail.mit.edu/6.006/}

The file that controls authentication is
  \urln{/afs/csail.mit.edu/proj/courses/6.006/auth/htpasswd}
In order to checkout/commit via https, you'll need to do the following
on CSAIL AFS:
\begin{enumerate}
\item \code{\$ cd /afs/csail/proj/courses/6.006/auth}
\item \code{\$ htpasswd htpasswd \$USER}
\item Pick a password, and enter it at the prompt. (Twice.)
\end{enumerate}

Better instructions for CSAIL SVN use are located on the TIG wiki:
  \urln{http://tig.csail.mit.edu/twiki/bin/view/TIG/UsingSubversionAtCSAIL}


\subsection{Submission website}

We required all problem sets to be submitted electronically via our
website, located at \url{http://alg.csail.mit.edu/}. We also used this
site to record and publish grades. The code for this website is
located in the Subversion repository, in the \url{website/}
directory. For details about setting up and using this website, please
contact Victor Costan (\code{costan@gmail.com}).


\subsection{Scripts}

A shell script for printing submitted problem sets, downloaded from
the submission website, is located in the \url{spring09/script/}
directory in Subversion.

Other scripts in this directory include a script for generating
histograms of problem set/quiz scores, and for sending submitted
Python code to MOSS (see Section \ref{moss}).


\section{Plagiarism}

Much to our chagrin, we encountered several cases of plagiarism
throughout the semester. Dealing with these cases was difficult and
time-consuming, possibly because of our lack of an official policy for
it. The course collaboration policy does clearly state that all code
must be written alone, but this escaped some students.

Some students copied code from the published staff solutions from
previous semesters; we tended to deal with such cases more harshly, as
such copying was most likely not accidental.

There was much dissatisfaction among the course staff regarding how we
wound up handling plagiarism cases. In particular, we were
uncomfortable with the fact that students who plagiarized often
received more credit than students who did the work honestly, but
turned it in late.

We recommend revisiting the late policy as well as establishing a more
consistent plagiarism policy, laying out specific and harsh penalties
for infractions.

The collaboration policy should also address self-plagiarism; every
semester, some students drop the class and re-take it the following
semester. If problems get reused, the course should have a specific
policy regarding whether students may reuse their own code from
previous terms.

\subsection{MOSS}
\label{moss}

The tool we used for detecting plagiarism is MOSS
(\url{http://theory.stanford.edu/~aiken/moss/}). A submission script
is present in Subversion; it's pretty easy to use. Submitted work from
previous semesters is present in AFS, at
\url{/afs/csail/proj/courses/6.006/old_submissions/}, in the event that
you feel like running current submissions against older submissions.


\section{Recitations}

Recitation attendance was ``mandatory''. We didn't take attendance,
but if a TA remembered a student, it did play a very minor role in
assigning final grades.

We tried to shy away from covering new material in recitation. Most
recitations were dedicated to solving sample problems relating to the
lecture material; to more carefully reviewing difficult concepts from
lecture; or to covering lecture material from a different perspective.

While the lecturers gave some guidance on recitation material, the TAs
typically prepared lesson plans independently, which led to some
divergence between sections. I'd recommend trying to coordinate
between TAs a little better, so that the different sections cover as
similar material as possible.


\section{Problem sets}

\subsection{General Comments}

We had 6 problem sets this year, split into Part A (coding) and Part B
(theory). Most students commented on their feedback forms that they liked
this format and it helped with managing their workload.

Usually, problem sets were due every two weeks, with Part A due on
Tuesday, and Part B due two days later, on Thursday. Some students
suggested a longer gap between parts, perhaps as long as a full
week. Both parts were due at 11:59pm; some students disliked this and
would have preferred a later deadline (say, 6:00am).

The material on each problem set had typically been covered in lecture
at the time the problem set was released (two weeks in advance of the
due date). There was some feeling that problem sets lagged too far
behind lectures, and so they didn't serve to reinforce material from
class.

\subsection{Comments on specific Part A problems}

\subsubsection{Problem Set 1 -- Profiling}

The purpose of this coding assignment was mainly to get students to get 
setup and get familiar with using Python and Latex. Whil the profile and 
timeit functions are useful, but most students did not bother using them 
for any other problem set. Also, the backstory for this part was weak and 
can be improved upon.

Almost any timing value was accepted for this problem. The major error
that students made was that they timed list creation along with the sort. 
Most students did arrive at the correct asymptotic running time, since it 
was mentioned in class, but their values were rather skewed.

\subsubsection{Problem Set 2 -- Longest Common Substring}

Students thought this problem was interesting, but the debugging was
frustrating and time-consuming. More guidance would be appreciated.

Many students had trouble debugging their code here; the tendency is
to write a big block of code and hope it works. One thing that might
help is providing a framework for writing the rolling hash, and
providing separate test cases for it. Students used many different
rolling hash implementations, some of which betrayed a fundamental
misunderstanding of the purpose of a rolling hash---covering this more
carefully in lecture and/or recitation is probably a good idea.

Other issues that students encountered were:
\begin{itemize}
\item Use \texttt{xrange} instead of \texttt{range} for large ranges.
\item Use \texttt{pow(b, e, m)} to compute $b^e\bmod m$, rather than
  \texttt{(b**e) \% m}. (Note: \texttt{math.pow} and \texttt{pow} are
  different!)
\end{itemize}

\subsubsection{Problem Set 3 -- Gas Simulation}

Students seemed to think it was interesting to see the problem
visually; it gave a more concrete feel to the problem.

We intentionally did not give a running time guideline for this
problem, so there were many suboptimal approaches. Some students found
this frustrating, but we tried to make them get used to the concept
that the optimal solution is not always known.

\subsubsection{Problem Set 4 -- Rubiks Cube}

Many students enjoyed this coding assignment a lot and were excited to tackle
the challenge (although it turned out quite easy). Check out the two GUIs that
students made, located under 
\urln{/afs/csail.mit.edu/proj/courses/6.006/www/data/spring09/source/ps4-rubik}

Common errors included failing to stop at level 8.

\subsubsection{Problem Set 5 -- Shortest Route from MIT to Caltech}

There were many complaints about this coding problem. First, some students felt 
that they did not learn much from a straightforward implementation of Dijkstra. 
Second, they did not like the HeapID class that was provided because they felt
it was hard to understand the source code and the details were difficult to work 
with.

We took off a couple points for solutions that didn't stop upon
reaching the destination node; some students felt this was unfair as
it doesn't affect the asymptotic runtime of the solution.

\subsubsection{Problem Set 6 -- Image Resizing and Longest Increasing Subsequence}

Students enjoyed the image resizing problem.

The longest increasing subsequence problem was intended to be a simple
exercise, but turned out more challenging than we expected. The
solution is easy to search for online, and some students openly
admitted to looking it up on Wikipedia. An $O(n\lg n)$ solution
exists, but we gave full credit to the $O(n^2)$ solution.


\subsection{Comments on specific Part B problems}

\subsubsection{Problem Set 3, Problem 1 -- Find the Largest i Elements in Sorted Order}

The point distribution here was pretty bad; part (c), for which the
solution is ``use counting sort'', was far overweighted at 15 points.

\subsubsection{Problem Set 5, Problem 2 -- Parameterized Graph}

This problem was widely reviled as overly vague and difficult. The TAs
generally agreed; we do not recommend using this problem again without
major reworking.

\subsubsection{Problem Set 5, Problem 3 -- Even-Length Paths}

We like this problem a lot, but some students students were irritated
that the opportunities for partial credit seemed a little lacking.

\subsubsection{Problem Set 6, Problem 1 -- Linear Rubberband Approximataion}

We heard many complaints that this problem was difficult to
understand. Providing an example in the problem statement would really
help---it would also explain why it is called a ``linear rubberband
approximation''.

\subsubsection{Problem Set 6, Problem 2 -- Viterbi's Algorithm}

Many students tried to use a BFS-based solution. An unmodified BFS
doesn't work because it eliminates valid paths that are not also
shortest paths to a given vertex. It might be wise to explicitly
caution students about this.

This might also have stemmed from a misunderstanding of the problem
itself, so a more clear problem statement may help.
	

\section{Exams}

There were three exams; two two-hour midterms, and a three-hour final
exam.

Quiz 1 was far too long! Nobody finished early, and several students
wound up leaving one or more problems blank or half-finished due to
time pressure. As it happened, the final exam was probably a little
too long as well.

Our quizzes this semester tended to have several long-form problems,
often with no subparts, and for which it was difficult to assign
objective partial credit.  It would probably be better to have at
least a little more emphasis on shorter problems and subproblems that
tease out understanding of particular concepts.

We made the mistake of having a few problems whose point distributions
tended to be all-or-nothing. Such problems should be avoided to the
extent possible!

Per-problem score distributions for the Fall 2008 and Spring 2009
quizzes are posted to their respective websites, if you are curious
how a particular problem played out.

Quizzes from previous semesters can be found in Subversion, or posted
publicly at \url{http://courses.csail.mit.edu/6.006/oldquizzes/}.

\subsection{Comments on specific problems}

\subsubsection{Quiz 1, Problem 6 -- Treaps}

This was pretty much an all-or-nothing problem. If you got lucky and
figured it out in the limited time available, you got a lot of points,
but otherwise you got very few.

This problem was very widely panned by the students. We acknowledge
that it was a poor exam problem.

\subsubsection{Quiz 2, Problem 4 -- Clusters}

There was some griping from students that grading on this problem was
capricious, and in particular that it was inconsistent with Problem
3. Specifically, suboptimal running times for Problem 3 tended to
receive 20/24 or more, while suboptimal running times for Problem 4
received much lower scores. Not sure what to make of that, but it's
probably something to keep in mind.

\subsubsection{Final Exam, Problem 5 -- Local Minimum}

This was another all-or-nothing problem. We wound up giving 14 out of
24 for an $O(n)$ solution, even though the problem specifically asked
for a more efficient solution; we felt pretty guilty about taking away
all 24 points, considering that the $O(\lg n)$ solution was not
straightforward.

\subsubsection{Final Exam, Problem 6 -- Straits}

This problem was a disaster. Very few students understood the problem
at first, and it was impossible to issue a clarification because of
the limited blackboard space available in Johnson during the
exam. This problem would have been much improved by including an
example, and explaining the motivation of the name ``straits''.


\section{Grading Policy}

For the last several semesters, the final grade has been 40\% problem
sets, 15\% per midterm, 25\% final exam, and 5\% participation. There
was some feeling among students that the problem sets were too heavily
weighted; as it happened, each homework problem was weighted
about the same as a quiz problem. It's probably worth thinking about
whether this is desirable. It's probably also worth considering a less
draconian late policy, considering the large weight given to each
problem set.

If you're curious, the letter grade distribution for the last few
semesters is shown below. We adhered to the principle that B+'s are
evil and should be avoided.

\begin{center}
\begin{tabular}{|l|ccc|cc|cc|c|c|c||ccc|}
\hline
Term & A+ & A & A- & B & B- & C & C- & D & F & Total & A & B & C \\
\hline
Spring 2009 & 4 & 54 & 4 & 49 & 7 & 10 & 4 & 1 & 2 & 135 & 45.9\% & 41.5\% & 10.4\% \\
\hline
Fall 2008 & 5 & 35 & 7 & 43 & 3 & 3 & 0 & 0 & 1 & 97 & 48.5\% & 47.4\% & 3.1\% \\
\hline
Spring 2008 & 4 & 25 & 9 & 19 & 7 & 7 & 0 & 4 & 0 & 75 & 50.7\% & 34.7\% & 9.3\% \\
\hline
\end{tabular}
\end{center}


\end{document}
