\documentclass[12pt]{article}
\usepackage{fullpage}
\usepackage{epsfig}
\usepackage{latexsym}
\usepackage[all]{xy}
\begin{document}
\begin{center}
\bf
Algorithms\\
Computer Science 140 \& Mathematics 168\\
Instructor: B. Thom\\
Fall 2004\\
\rm
Homework 10a\\
Due on Thursday, November 4, 2004 (beginning of class)\\
\end{center}
\begin{enumerate}
\item \textbf{[15 Points] Dijkstra's Mind Games.}  

A deeper understanding of Dijkstra's algorithm can be obtained by considering
its behavior in specific situations. (The same can be said for most algorithms!) 
Towards this end, your task is to solve the following puzzles:
\begin{enumerate}
\item 
Give me a graph with at least two negative weight edges for which Dijkstra's
algorithm miscalculates at least one shortest path from $s$.


\item 
Give me a graph with at least one negative weight edge for which Dijkstra's
algorithm calculates the correct shortest paths from $s$.


\item
Give me a graph with at least one negative weight and no negative cost cycles
for which Dijkstra's algorithm miscalculates at least one shortest path from
$s$.


\end{enumerate}
Your examples should be fairly simple, e.g. $|V| \leq 4$. For each answer, draw
your graph and clearly indicate which vertex is $s$. Also indicate what labels
Dijkstra would assign and indicate the graph's shortest path values.



\item \textbf{[15 Points] Proof of Dijkstra's Algorithm.}

Write the proof of correctness of Dijkstra's Algorithm \emph{that was presented
in class} in your own words.  For full credit, your proof should be clear,
precise, and complete. Note that the proof that we did in class is not the same
as the proof in the book.  Our technique was simpler, and is the one must
address here.




\end{enumerate}
\end{document}
