%
% 6.006 problem set template
%
\documentclass[12pt,twoside]{article}

\input{macros}

\usepackage{amsmath}
\usepackage{graphicx}

\setlength{\oddsidemargin}{0pt}
\setlength{\evensidemargin}{0pt}
\setlength{\textwidth}{6.5in}
\setlength{\topmargin}{0in}
\setlength{\textheight}{8.5in}

% Fill these in!
\newcommand{\theproblemsetnum}{4}
\newcommand{\handoutnum}{9}
\newcommand{\releasedate}{October 21, 2008}
\newcommand{\partaduedate}{Tuesday, November 4}
\newcommand{\partbduedate}{Thursday, November 6}

\begin{document}

\handout{\handoutnum}{Problem Set \theproblemsetnum}{\releasedate}
\setlength{\parindent}{0pt}

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

This problem set is divided into two parts: Part A problems are
programming tasks, and Part B problems are theory questions.

{
\parindent 0.5in
\textbf{Part A questions} are due {\bf \partaduedate} at {\bf 11:59PM}.

\textbf{Part B questions} are due {\bf \partbduedate} at {\bf 11:59PM}.
}

Solutions should be turned in through the course website in PDF form
using \LaTeX\ or scanned handwritten solutions. 

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

Remember, your goal is to communicate. Full credit will be given only
to the correct solution which is described clearly. Convoluted and
obtuse descriptions might receive low marks, even when they are
correct. Also, aim for concise solutions, as it will save you time
spent on write-ups, and also help you conceptualize the key idea of
the problem.

\medskip

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\hrulefill

\medskip

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

{\bf Exercises:}

\begin{itemize}

\item CLRS 22.2-3 (page 539)

\item CLRS 22.2-8 (page 539)

\item CLRS 22.3-9 (page 548)

\item CLRS 22.3-10 (page 549)

\end{itemize}

\hrulefill

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection*{Part A: Due \partaduedate}
\begin{enumerate}
\item {\bf (50 points)} $2 \times 2 \times 2$ Rubik's Cube

  We say that a configuration of the cube is $k$ levels from the
  solved position if you can reach the configuration in exactly $k$ 
  twists, but cannot reach the it in any fewer twists.

  Download \texttt{ps4\_rubik.zip} from the class website.

  \begin{enumerate}

  \item {\bf (20 points)} For this problem, we will use breadth-first search to 
    recreate the column labeled $f$ in the chart seen at
    \texttt{http://en.wikipedia.org/wiki/Pocket\_Cube}.  
    
    Write a
    function \texttt{positions\_at\_level} in \texttt{level.py}
    that takes a nonnegative integer argument \texttt{level}, and
    returns the number of configurations that are \texttt{level} levels 
    from the solved configuration (\texttt{rubik.I}), using both quarter 
    twists and half twists (twisting the cube by 90 or 180 degrees). 
    
    The code in \texttt{rubik.py} only defines the \texttt{rubik.quarter\_twists} 
    move set, so you should start by defining a new move set that includes half 
    twists as well. Do not modify \texttt{rubik.quarter\_twists} because you will
    need it for the next part of this problem.

    Test your code using \texttt{test\_level.py}, and submit it to the
    class website. Testcases above level 8 are commented out, 
    since they may require more memory than many computers have.
    %because
    %they may require at least 1GB of RAM. Level 10 should take no more
    %than a couple minutes, even with 512MB of RAM.


  \item {\bf (30 points)} Now you will actually solve a given configuration
    of the cube, by finding the shortest path between two configurations
    of the cube (the start and the goal). In this part of the problem, only
    quarter twists are allowed (half twists are not).

    Your code from part (a) could easily be modified to find shortest
    paths, but a BFS that goes as deep as 14 levels takes a few minutes
    (not to mention the memory needed). A few minutes might be fine
    for creating a Wikipedia page, but we want to solve the cube fast!

    Instead, we will take advantage of a property of the graph that we
    can see in the chart. In particular, the number of nodes at level
    7 (half the diameter) is much smaller than half the total number
    of nodes. 
    
    With this in mind, we can instead do a two-way BFS, starting from
    each end at the same time, and meeting in the middle. At each
    step, expand one level from the start position, and one level from
    the end position, always checking to see whether any new nodes have
    been discovered in both searches. When you find such a node,
    you just have to read off parent pointers to return the correct path. 

    Write a function \texttt{shortest\_path} in \texttt{solver.py} that
    takes two positions, and returns a list of moves that is a
    shortest path between the two positions.

    Test your code using \texttt{test\_solver.py}. Check that your
    code runs at close to the same speed as level 7 from part(a) in the worst 
    case, after modifying it to use just the quarter\_twist move set.

  \item {\bf (Optional)} Go out and impress your friends with new
   2x2x2 Rubik's Cube solver you just created! You can test your code using
   \texttt{test\_human\_solver.py}, which will ask you to input the
   current configuration of a real Rubik's cube, and then tell you the
   shortest path in human-readable symbols (you may need to read \texttt{rubik.py} 
   to understand these symbols though).

  \end{enumerate}

\end{enumerate}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection*{Part B: Due \partbduedate}
\begin{enumerate}

\item {\bf (15 points)} Connected Components

	Given an undirected graph $G=(V,E)$, a \emph{connected component} 
	of $G$ is a set of verticies $C \subseteq V$ for which the
	following two properties hold. \\
	\begin{itemize}
  		\item every two vertices in $C$ are connected by a path. \\
  			$v_1, v_2 \in C \implies \exists $ a path in $G$ $v_1 = x_0 
  			\rightarrow x_1 \rightarrow \; ... \; \rightarrow x_k = v_2$
  		\item no edge connects a vertex inside the set to a vertex outside the set. \\
  			$v \in C$ and $w \in V/C \implies \set{v, w} \notin E$ \\
  			($V/C$ is the set $V$ minus the set $C$)
	\end{itemize}
	
  Give an $O(V+E)$-time algorithm for partitioning an undirected graph into
  connected components. That is, given a graph $G=(V,E)$ return a set 
  $S = \set{C_i}$ where each $C_i$ is a connected component of $G$ and 
  $\bigcup{C_i} = V$
    
\item {\bf (20 points)} Eliminating Cycles by Removing One Edge

  For each of the following statements, prove the statement or give 
  a counter example to show that it is false. If you give a counter
  example, give one with the fewest possible vertices. Use \LaTeX{}
  to draw counter-example graphs if necessary (the solution template
  contains a drawing of the following graph to get you started).

\setlength{\unitlength}{1mm}
\begin{picture}(40, 40)  % area of the drawing

  % vertices
  
  \put(10, 10){\circle*{1}}
  \put(20, 10){\circle*{1}}
  \put(30, 10){\circle*{1}}
  
  \put(10, 20){\circle*{1}}
  \put(20, 20){\circle*{1}}
  \put(30, 20){\circle*{1}}

  \put(10, 30){\circle*{1}}
  \put(20, 30){\circle*{1}}
  \put(30, 30){\circle*{1}}

  % edges

  \put(10, 10){\vector(1, 0){9}}
  \put(10, 10){\vector(0, 1){9}}
  \put(10, 10){\vector(1, 1){9}}
\end{picture}

  \begin{enumerate}

  \item {\bf (10 points)} If DFS on a graph $G$ produces exactly one back edge, then it is 
  possible to remove an edge from $G$ to make the graph acyclic.

  
  \item {\bf (10 points)} If $G$ is cyclic but can be made acyclic by removing one edge, then
  DFS will encounter exactly one back edge.

  \end{enumerate}

\item {\bf (15 points)} Graphs and Matrices

  The {\em incidence matrix} of an undirected graph $G=(V,E)$ is
  an $|V|\times|E|$ matrix $U$, in which every column corresponds
  to an edge $e=\{i,j\} \in E$. The entries of column $e=\{i,j\}$ are all
  zero except for the entries in rows $i$ and $j$ which are both $1$.

%  \begin{enumerate}

%  \item {\bf (7 points)} 
  Consider the matrix $A=U U^T$. (that is, $A$ is
  the matrix product of $U$ and its transpose; the $i,j$ entry of
  a product $X=Y*Z^T$ is $X_{i,j}=\sum_{k}Y_{i,k} Z{j,k}$ where
  the summation is over a column of $Y$ and a column of $Z$.)
  Describe two ways in which the entries of $A$ relate to properties of the graph $G$.   

  \end{enumerate}

\end{document}