\documentclass[10pt,letterpaper,unboxed,cm]{hmcpset}
\usepackage[margin=1in]{geometry}
\usepackage{graphicx}
\usepackage{enumerate}
\newcommand{\st}{~\mid~}
\newcommand{\ind}{$~~~$}
\name{}
\class{CSE 101 Fall 2018}
\assignment{Homework 2}
\duedate{Due: Tuesday, October 16, 2018 at 11:59pm}
\begin{document}
\begin{center}
\begin{minipage}[t]{5.7in}
\rule{\linewidth}{2pt}
{\sc Instructions}\newline
This homework assignment may be completed in groups of size 1-4. The solutions must be {\bf typed} (using a computer.) Figures and graphs can be hand drawn. For algorithm descriptions we require a high-level English description AND an implementation description. If you find it necessary to also include a pseudo code to help understand your description then feel free to include it.
\newline\newline
Please refer to the course page for requirements in writing up answers for algorithm questions.
\rule{\linewidth}{2pt}
\end{minipage} \hfill
\end{center}
\begin{enumerate}
%FIRST PROBLEM
\item Run the strongly connected components algorithm on the following directed graph $G$. When doing DFS on $G^R$: whenever there is a choice of vertices to explore, always pick the one that is alphabetically first.\\
{\scriptsize$
A: B,D\\
B: C,D,E\\
C: F\\
D: E\\
E: A,C\\
F: I,J\\
G: A,D,K\\
H: D,E,G,I\\
I: J\\
J: C\\
K: H$}\\
In each case answer the following questions.
(6.25 points each)
\begin{enumerate}
\item
In what order are the strongly connected components (SCCs) found?
\item
Which are source SCCs and which are sink SCCs?
\item
Draw the "metagraph" (each meta-node is an SCC of $G$)
\item
What is the minimum number of edges you must add to this graph to make it strongly connected?
\end{enumerate}
\bigskip
%SECOND PROBLEM
\item
Give a linear time ($O(|V|+|E|)$) algorithm which takes as input a directed simple graph $G=(V,E)$ and determines for each vertex whether or not it is part of a directed (non-empty) cycle. For output We represent a cycle by list of vertices that are part of a cycle. Return all such lists that are found in the graph where every node is just a part of single list.\\
(13 points for correct algorithm description,
6 for correctness proof, and 6 for efficiency and time analysis,).
%THIRD PROBLEM
\item
You are devising a flight scheduler for a travel agency. The
scheduler will get a list of available flights,
and the customer's origin and destination.
For each flight, it is given the cities and times of departure and
arrival.
The scheduler should output a list of
flights that will take the customer from her origin to her
destination that arrives as early as possible, subject to
giving her at least 15 minutes for each connection. Give a formal specification for this problem (Instance, Solution Space, Constraints, Objective), and give as efficient as possible an algorithm to solve the problem.\\
(11 points for correct algorithm description,
7 for correctness proof, and 7 for efficiency and time analysis,).
\bigskip
% FOURTH PROBLEM
\item
Suppose you had $n$ matrices with dimensions: $a_1\times b_1, a_2\times b_2,\dots, a_n\times b_n$. Your goal is to determine, given two integers $s$ and $t$, whether it is possible to multiply a sequence from the list of given matrices together, in any order
and possibly not using all of the matrices, to end up with a matrix with dimensions $s\times t$.
\\
For example, if the list of matrix
dimensions is $A: 3 \times 5, B: 5 \times 7, C: 7 \times 9, D: 9 \times 5 $, $E : 9 \times 3$, and $F: 7 \times 5$
we can construct a $9 \times 9$ matrix as $E*A*B*C$. \\
(13 points for correct algorithm description,
6 for correctness proof, and 6 for efficiency and time analysis,).
\end{enumerate}
\end{document}