\documentclass[12pt,twoside]{article}
\usepackage{amsmath,graphicx}
\input{6006-stuff}
\newcommand{\name}{}
\newcommand{\proc}{\textsc}
\begin{document}
\handout{ps5}{Problem Set 5}
\setlength{\parindent}{0pt}
\newcommand{\solution}{
\medskip
{\bf Solution:}
}
\newcommand{\collaborators}[1]{
\qquad {\bf Collaborators:} #1
}
This problem set is due {\bf November 21} 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 22.2-3 from CLRS.
\item Exercise 22.2-8 from CLRS.
\item Exercise 22.3-1 from CLRS.
\item Exercise 22.3-8 from CLRS.
\item Exercise 22.3-9 from CLRS.
\end{itemize}
\hrulefill
\begin{enumerate}
\item {\bf (8 points)} Bipartite graphs
A graph is called \emph{bipartite} if its nodes can each be assigned
a color, either red or blue, such that no red node is adjacent to
another red node, and no blue node is adjacent to another blue
node. Give an efficient algorithm to determine if a graph is
bipartite. What is its running time?
\item {\bf (22 points)} Cycles in a directed graph
You are given a directed graph $G=(V, E)$ in which every vertex
has at least one outgoing edge.
Your task is to find a vertex $v$ that is part of a directed cycle
(a cycle is a path of edges from a node to itself).
\begin{enumerate}
\item {\bf (6 points)} Argue that G must contain at least one
directed cycle.
\item {\bf (8 points)} Can you use a single BFS to find such a
vertex? If so, how? If not, why not?
\item {\bf (8 points)} Can you use a single DFS to find such a
vertex? If so, how? If not, why not?
\end{enumerate}
\item {\bf (30 points)} 2x2x2 Rubik's Cube
For this problem, you only need to turn in code.
We say that a configuration of the cube is $k$ levels from the
solved position if you can reach the position in exactly $k$ twists
(quarter-turns, either clockwise or counterclockwise), but you
cannot reach the position in fewer twists.
\begin{enumerate}
\item {\bf (15 points)} Use breadth first search to recreate the
chart seen on \\
\texttt{http://en.wikipedia.org/wiki/Pocket\_Cube}. You will
write a function that takes \texttt{moves}, the set of legal
permutations of the cube, and \texttt{level}. It should return the
number of configurations of the cube \texttt{level} levels from
the solved position. Using the set of quarter-twists provided to
you should give you the same output as column $q$ in the chart.
Note: if your machine does not have much RAM, your program may not
work for higher levels. In this case, don't worry, and just add a
comment telling us the largest level you solved, and how much RAM
you have.
\item {\bf (15 points)} Given two configurations of the cube, write
a function that returns the shortest path between the two
configurations. Instead of doing a simple breadth first search as
in part (a), use less memory and time by doing a 2-way breadth
first search. That is, do two breadth first searches, one starting
at each end, and find the configuration where they meet. This will
be discussed in recitation.
\end{enumerate}
\end{enumerate}
\end{document}