\documentclass[12pt,twoside]{article}
\usepackage{amsmath,graphicx}

\input{6006-stuff}
\newcommand{\name}{}
\newcommand{\proc}{\textsc}
\begin{document}


\handout{ps4}{Problem Set 4}
\setlength{\parindent}{0pt}

\newcommand{\solution}{
  \medskip
  {\bf Solution:}
}

\newcommand{\collaborators}[1]{
  \qquad {\bf Collaborators:} #1
}

This problem set is due {\bf November 6} at {\bf 11:59PM}. 

Solutions should be turned in through the course website in PS or PDF
form using \LaTeX\ or scanned handwritten solutions, or they may be
handwritten and turned in to a member of the 6.006 course staff on or
before the due date.  Hand-drawn diagrams may also be referenced in
your \LaTeX\ writeup and turned in at the next day's recitation.

A template for writing up solutions in \LaTeX\ is available on the
course website.

\medskip

\hrulefill

\medskip

Exercises are for extra practice and should not be turned in.

{\bf Exercises:}

\begin{itemize}

\item Exercise 6.1-3 from CLRS.

\item Exercise 6.2-1 from CLRS.

\item Exercise 6.3-1 from CLRS.

\item Exercise 6.4-1 from CLRS.

\item Exercise 6.4-3 from CLRS.

\item Exercise 6.5-4 from CLRS.

\item Exercise 8.2-2 from CLRS.

\item Exercise 8.4-1 from CLRS.

\end{itemize}

\hrulefill

\begin{enumerate}

\item {\bf (12 points)} Heap Delete

The operation $\proc{Heap-Delete}(A, i)$ deletes the item in node $i$
from heap $A$. Give a pseudocode implementation of
$\proc{Heap-Delete}$ that runs in $O(\lg n)$ time for an $n$-element
max-heap, using notation similar to p. 140 of CLRS; you may choose to
use Python syntax.

\item Monotone Priority Queues

A ``monotone priority queue'' (MPQ) is a data structure that supports
the following operations:

\begin{itemize}
\item \proc{Max}($Q$) - Returns the maximum element in $Q$. The
maximum of a new, empty MPQ is initially $\infty$. Otherwise, the
maximum of an empty MPQ is the last element to have been deleted.
Note that \proc{Max}($Q$) leaves the elements of $Q$ unchanged.

\item \proc{Delete-Max}($Q$) - If $Q$ is empty, returns
\proc{Max}($Q$). Otherwise, removes and returns \proc{Max}($Q$). If
the queue is empty after the operation, the last deleted value remains
the maximum. In other words, \proc{Max}($Q$) is monotonically
decreasing and does not reset when the MPQ is empty.

\item \proc{Insert}($Q, x$) - Inserts $x$ into $Q$ given that $x \leq
\proc{Max}(Q)$. If $x> \proc{Max}(Q)$, then the MPQ is not modified.
\end{itemize}

For this problem, assume that $x$ is an integer in the range $[0,k]$
for some fixed integer value $k$.

\begin{enumerate}

\item {\bf (9 points)} Give an implementation of a monotone priority
queue that takes $O(m \log m)$ time to perform $m$ operations starting
with an empty data structure.

\item {\bf (9 points)} Give an implementation of a monotone priority
queue that takes $O(m + k)$ time to perform $m$ total
operations. Hint: Use an idea from \proc{Counting-Sort}.

\end{enumerate}

\item Gas Simulation

  In this problem, we consider a simulation of $n$ bouncing balls in
  two dimensions inside a square box.  Each ball has a mass and
  radius, as well as a position $(x,y)$ and velocity vector, which
  they follow until they collide with another ball or a wall.
  Collisions between balls conserve energy and momentum.  This model
  can be used to simulate how the molecules of a gas behave, for
  example.  The box is 8192 by 8192 units wide, and each ball has a
  maximum radius of 128 units.

  The initial code, featuring an interactive graphical simulation, is
  given to you at \\
  http://courses.csail.mit.edu/6.006/fall07/source/gas.py.  You may
  need to install the pygame module (available from http://pygame.org)
  for graphics if you don't already have it.

  You may notice that performance, indicated by the simulation steps
  per second rate, slows down significantly as you increase the number
  of balls.  Your goal is to improve the running time of the
  \texttt{detect\_collisions} function, which computes whether pairs
  of balls collide (two balls are said to collide if they overlap) and
  dispatches to the \texttt{handle\_collision} function to compute the
  new ball velocities.  You do not need to worry about
  \texttt{handle\_collision}.

  For this problem, there is no single right answer. We'd like you to
  explore the techniques we've introduced in class to improve the
  running time of the simulation.

  \begin{enumerate}

    \item {\bf (3 points)} What is the running time of
    \texttt{detect\_collisions} in terms of $n$, the number of balls?
    Do not include the time used by \texttt{handle\_collision}.

    \item {\bf (15 points)} Write a more efficient
    \texttt{detect\_collisions} routine. To be correct, it must still
    detect any collisions. The code provided does correctly calculate
    whether balls collide, so you can use it to compare against your
    results.

    Submit your version of gas.py, containing an improved
    \texttt{detect\_collisions} routine.  You may find the option to
    automatically pause after a certain number of timesteps useful, as
    well as the count of total collisions to spot if something is wrong.

    \item {\bf (9 points)} Explain how your \texttt{detect\_collisions}
    algorithm is asymptotically faster than the original
    implementation. We do not expect a formal proof here, but give
    justifications where you can.  Again, do not include the time used
    by \texttt{handle\_collision}.

    \item {\bf (3 points)} After 2048 timesteps, what is the ratio of
    the increase in simulation steps per second of your version
    compared to the given code for $n = 100$?  $n = 200$?  How many
    total collisions are counted in each case? (For this problem, use
    the interface at the starting screen to set the number of balls
    and to pause at 2048 steps.)

  \end{enumerate}

\end{enumerate}

\end{document}