\documentclass[11pt]{article}

%\usepackage{mtpro2,times}
%\usepackage[special]{handout}
%\usepackage{graphicx}
%\usepackage{alltt}
%\usepackage{textcomp}
\usepackage{graphicx}
\usepackage{alltt}
\usepackage[pdftex]{color}
\definecolor{Tan}{rgb}{1,1,.3}


\topmargin 0.0in \addtolength{\topmargin}{-1in}
\addtolength{\textheight}{2in}
\oddsidemargin 0.0in
%\addtolength{\oddsidemargin}{-.25in}
\addtolength{\textwidth}{1.5in}

\usepackage{graphicx}

\newcommand{\courierScale}{0.97}

\newcommand{\comment}[1]{}

\newcommand{\code}[1]{\texttt{#1}}


\begin{document}
\begin{center}
\textbf{Computer Science 112} \\
            Problem Set 6, \textbf{2\%}\\
\end{center}

\textbf{Parallel Mergesort and Monte Carlo Simulation}\\

In this assignment, you will implement a parallel mergesort and a parallel
Monte Carlo simulation for computing the value of $\pi$ ($pi$).  As your guide,
you may use the example \code{parallel*.py} programs we have seen and developed
in class.  Please submit \code{parallelMergesort.py} and
\\ \code{parallelMontePi.py} to your \code{turnin/ps6} subfolder.  Both programs
should show timings of the sequential and parallel versions of the algorithms,
as in the example programs.

\textbf{\\Mergesort}\\

There are various ways of approaching a parallel implementation of the
mergesort algorithm.  A complicated implementation could involve a
parallelization of the \code{merge} operation, where two Processes responsible
for separate sorted lists swap elements with each other to ensure that the lists
don't overlap.  Then the lists could simply be concatenated to form the overall
sorted list.

You can take a more simple approach, duplicating the kind of parallelism used
in the \\ \code{parallelQuicksort.py} example.  Here, we keep the \code{merge}
operation as before and rely on the non-parallel \code{mergesort}, but simply
run more than one instance of \code{mergesort} at a time.

\textbf{\\Monte Carlo Simulation}\\

Monte Carlo methods are the class of algorithms that use random sampling to
compute their results.  For this part, you will implement both a sequential
and parallel implementation of one of the more basic Monte Carlo methods, that
for computing the value of the mathematical constant $\pi$. Your \code{main}
method will show the sequential versus parallel timings for performing this
computation.  The \code{parallelIntegration.py} example can be used as a guide.

The process for randomly approximating $\pi$ is quite simple.  Consider the
disk of radius 1 centered at the origin.  Considering only the part of the disk
within the first quadrant (positive x and y), we see the area within the disk
is $\pi/4$ while the area within the unit square (from $0$ to $1$ in x and y) is
obviously $1$. If we generate a random point in the unit square (using
\code{random.random()} for the x coordinate and again for the y coordinate),
then the probability that the point is within the unit disk is $\pi/4$. We can
determine whether the point is within the disk by evaluating $x^2 + y^2 <= 1$.
If we generate $n$ points, then the proportion of points that were within the
disk is an approximation of $\pi/4$. Multiply by $4$ and you have an
approximation of $\pi$.




\end{document}