#LyX 2.2 created this file. For more info see http://www.lyx.org/
\lyxformat 508
\begin_document
\begin_header
\save_transient_properties true
\origin unavailable
\textclass article
\use_default_options true
\begin_modules
theorems-std
\end_modules
\maintain_unincluded_children false
\language english
\language_package default
\inputencoding auto
\fontencoding global
\font_roman "default" "default"
\font_sans "default" "default"
\font_typewriter "default" "default"
\font_math "auto" "auto"
\font_default_family default
\use_non_tex_fonts false
\font_sc false
\font_osf false
\font_sf_scale 100 100
\font_tt_scale 100 100
\graphics default
\default_output_format default
\output_sync 0
\bibtex_command default
\index_command default
\paperfontsize default
\spacing single
\use_hyperref false
\papersize default
\use_geometry false
\use_package amsmath 1
\use_package amssymb 1
\use_package cancel 1
\use_package esint 1
\use_package mathdots 1
\use_package mathtools 1
\use_package mhchem 1
\use_package stackrel 1
\use_package stmaryrd 1
\use_package undertilde 1
\cite_engine basic
\cite_engine_type default
\biblio_style plain
\use_bibtopic false
\use_indices false
\paperorientation portrait
\suppress_date false
\justification true
\use_refstyle 1
\index Index
\shortcut idx
\color #008000
\end_index
\secnumdepth 3
\tocdepth 3
\paragraph_separation indent
\paragraph_indentation default
\quotes_language english
\papercolumns 1
\papersides 1
\paperpagestyle default
\tracking_changes false
\output_changes false
\html_math_output 0
\html_css_as_file 0
\html_be_strict false
\end_header

\begin_body

\begin_layout Title
How To Properly Answer Questions in CIS502
\end_layout

\begin_layout Author
Mingyang Li
\end_layout

\begin_layout Standard
\begin_inset CommandInset toc
LatexCommand tableofcontents

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Newpage newpage
\end_inset


\end_layout

\begin_layout Part
Dynamic Programming
\end_layout

\begin_layout Section
Example Problem: Booking Flights
\end_layout

\begin_layout Standard
With the seemingly arbitrary ways in which airlines set their fares, you
 need dynamic programming to find the cheapest way to get from one city
 to another, especially when you care only about the cost and not about
 the number of stops you make.
 For this problem assume that we have n cities, 1, 2, .
 .
 .
 n arranged on a line.
 You are given the fare F(i,j) for going from city i to city j.
 Every flight you take must go from a lower-numbered city to a higher-numbered
 city.
 Design a dynamic programming algorithm to find the cheapest sequence of
 flights that will get you from city 1 to city n.
 Make your algorithm as efficient as possible and analyze its running time.
 
\end_layout

\begin_layout Subsection
Top-Level Question
\end_layout

\begin_layout Standard
Should I take the flight from 
\begin_inset Formula $n-1$
\end_inset

 to 
\begin_inset Formula $n$
\end_inset

? In other words: From which city should I settle for city 
\begin_inset Formula $n$
\end_inset

?
\end_layout

\begin_layout Subsection
Base Case
\end_layout

\begin_layout Standard
Airline Fare is zero for going to the first city.
\end_layout

\begin_layout Subsection
Recurrence
\end_layout

\begin_layout Standard
Let 
\begin_inset Formula $L(k)$
\end_inset

 be the lowest rate to reach city #
\begin_inset Formula $k$
\end_inset

:
\end_layout

\begin_layout Standard
\align center
\begin_inset Formula 
\[
L(k)=\begin{cases}
\min_{i=1}^{k-1}\left\{ L(i)+F(i,k)\right\}  & \text{\text{if }k>1}\\
0 & \text{if }k=1
\end{cases}.
\]

\end_inset


\end_layout

\begin_layout Subsection

\series bold
Final Answer
\end_layout

\begin_layout Standard
\begin_inset Formula $L(n)$
\end_inset

.
\end_layout

\begin_layout Subsection

\series bold
Running Time
\end_layout

\begin_layout Standard
Let's look at how the algorithm will visit nodes at depth 1 (Lv.1 in the
 figure).
 
\end_layout

\begin_layout Enumerate
When visiting 
\begin_inset Formula $L(1)$
\end_inset

: 0 node in Lv.2 needs to be visited.
\end_layout

\begin_layout Enumerate
When visiting 
\begin_inset Formula $L(2)$
\end_inset

: 1 node in Lv.2 needs to be visited.
\end_layout

\begin_layout Enumerate
When visiting 
\begin_inset Formula $L(3)$
\end_inset

: 2 nodes in Lv.2 need to be visited.
\begin_inset Newline newline
\end_inset

...
\end_layout

\begin_layout Enumerate
When visiting 
\begin_inset Formula $L(n-1)$
\end_inset

: 
\begin_inset Formula $n-2$
\end_inset

 nodes in Lv.2 need to be visited.
\end_layout

\begin_layout Standard
Sum of the nodes in Lv.2 that need to be visited is
\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
S=\frac{1}{2}\left[0+\left(n-2\right)\right]\cdot\left(n-1\right)=\frac{1}{2}\left(n-2\right)\cdot\left(n-1\right).
\]

\end_inset


\end_layout

\begin_layout Standard
Also consider:
\end_layout

\begin_layout Enumerate
Nodes in Lv.1 themselves need another 
\begin_inset Formula $n-1$
\end_inset

 visits.
\end_layout

\begin_layout Enumerate
Nodes in Lv.0, i.e.
 the root itself, needs another visit.
\end_layout

\begin_layout Standard
In total, that is 
\begin_inset Formula $\frac{1}{2}\left(n-2\right)\cdot\left(n-1\right)+\left(n-1\right)+1\implies O(n^{2})$
\end_inset

 time.
\end_layout

\begin_layout Subsection
Prove Correctness
\end_layout

\begin_layout Subsubsection
Prove 
\begin_inset Quotes eld
\end_inset

optimal substrcture
\begin_inset Quotes erd
\end_inset

 property
\end_layout

\begin_layout Enumerate

\series bold
A solution to this problem involves making a choice.

\series default
 Here, it's 
\begin_inset Quotes eld
\end_inset

to reach city 
\begin_inset Formula $k$
\end_inset

, from which city should I start my flight?
\begin_inset Quotes erd
\end_inset


\end_layout

\begin_layout Enumerate

\series bold
One of these choices must lead to the optimal solution.

\series default
 This is an assumption.
\end_layout

\begin_layout Enumerate

\series bold
Let's define the subproblem after taking this optimal choice.

\series default
 If we decide to settle for 
\begin_inset Formula $k$
\end_inset

 from city 
\begin_inset Formula $m$
\end_inset

, then the sub-problem is just 
\begin_inset Quotes eld
\end_inset

to reach city 
\begin_inset Formula $m$
\end_inset

, from which city should I start my flight?
\begin_inset Quotes erd
\end_inset


\end_layout

\begin_layout Enumerate

\series bold
Prove that the sub-solutions in the optimal solution must themselves be
 optimal:
\series default
 
\end_layout

\begin_deeper
\begin_layout Enumerate

\series bold
Declare the optimal solution to a problem:
\series default
 Suppose the optimal solution to go from city 1 to city k says 
\begin_inset Quotes eld
\end_inset

we should leave from city w
\begin_inset Quotes erd
\end_inset

: (
\begin_inset Formula $1\rightsquigarrow w\rightarrow k$
\end_inset

).
 
\end_layout

\begin_layout Enumerate

\series bold
Assume there exists a better solution solution:
\series default
 Suppose also a better solution says 
\begin_inset Quotes eld
\end_inset

we should leave from city p
\begin_inset Quotes erd
\end_inset

 which offers lower fare: (
\begin_inset Formula $1\rightsquigarrow p\rightarrow k$
\end_inset

).
 
\end_layout

\begin_layout Enumerate

\series bold
Using cut-and-paste technique, disprove the optimality of the original solution,
 creating a contradiction:
\series default
 Then we can just go via p instead of w, contradicting to the assumption
 of 
\begin_inset Quotes eld
\end_inset

leaving from city w
\begin_inset Quotes erd
\end_inset

 is the optimal solution.
\end_layout

\begin_layout Enumerate

\series bold
Prove the 
\begin_inset Quotes eld
\end_inset

optimal substrcture
\begin_inset Quotes erd
\end_inset

 property: 
\series default
Therefore, in order for an optimal solution to be optimal, every of its
 subproblems (in this case, only one) should be optimal.
 
\end_layout

\end_deeper
\begin_layout Subsubsection
Prove 
\begin_inset Quotes eld
\end_inset

overlapping subproblems
\begin_inset Quotes erd
\end_inset

 property
\end_layout

\begin_layout Standard
Suppose there are flights between every city in the map A->B->C->D.
 When querying L(D), we need query L(B) and L(C) respectively.
 When computing for the latter (
\begin_inset Formula $L(C)$
\end_inset

), we need to solve for 
\begin_inset Formula $L(B)$
\end_inset

, for which we have already calculated when dealing with 
\begin_inset Formula $L(D)$
\end_inset

.
 That is to say, we have overlapping subproblems.
\end_layout

\begin_layout Part
Greedy Algorithms
\end_layout

\begin_layout Section
Example Problem: Activity Selection
\end_layout

\begin_layout Standard
\begin_inset Formula $S$
\end_inset

: list of activities.
\begin_inset Newline newline
\end_inset


\begin_inset Formula $f$
\end_inset

: list of finishing times.
\begin_inset Newline newline
\end_inset


\begin_inset Formula $s$
\end_inset

: list of starting times.
\begin_inset Newline newline
\end_inset


\begin_inset Formula $n$
\end_inset

: number of activities.
\end_layout

\begin_layout Subsection
Subproblems Exist In This Problem – Answers to this problem is a series
 of choices
\begin_inset CommandInset label
LatexCommand label
name "subsec:Subproblems-Exist-In"

\end_inset


\end_layout

\begin_layout Quote
We make a choice, and are left with a subproblem to solve.
\end_layout

\begin_layout Subsubsection
Description In This Case
\end_layout

\begin_layout Standard
We can rephrase our problem as: 
\begin_inset Quotes eld
\end_inset

given a set of activities, which should we choose, leaving the rest activities
 to be dealt with later as a subproblem?
\begin_inset Quotes erd
\end_inset


\begin_inset Newline newline
\end_inset

Answer to this problem is: 
\begin_inset Quotes eld
\end_inset

take the one finishes the first.
\begin_inset Quotes erd
\end_inset


\end_layout

\begin_layout Subsubsection
(No Proof Required)
\end_layout

\begin_layout Standard
If the question only requires an algorithm to be designed, this is it.
 Done.
 Don't bother to continue.
\end_layout

\begin_layout Subsection
Greedy Choice Property
\end_layout

\begin_layout Quote
Greedy Choice Property: We can assemble a globally optimal solution by making
 locally optimal (greedy) solutions.
 
\bar under
Point it that, we don't have to make use of information outside, nor a layer
 inside, the scope of the current problem.
\end_layout

\begin_layout Subsubsection
Description In This Case
\end_layout

\begin_layout Standard
Consider a non-empty problem 
\begin_inset Formula $S_{k}$
\end_inset

.
 Let 
\begin_inset Formula $a_{1}$
\end_inset

 be the activity in 
\begin_inset Formula $S_{k}$
\end_inset

 w/ earliest finsihing time (i.e.
 our greedy choice).
 Let's show that 
\begin_inset Formula $a_{1}$
\end_inset

is indeed a member of the optimal solution (i.e.
 a maximum-size subset of muutually comatible activities) to 
\begin_inset Formula $S_{k}$
\end_inset

.
\end_layout

\begin_layout Subsubsection
Proof by Exchange
\end_layout

\begin_layout Standard
Suppose our greedy choice, the activity finishes first (at 
\begin_inset Formula $f_{1}$
\end_inset

), is not in the optimal solution 
\begin_inset Formula $A_{k}$
\end_inset

, and that the first activity our optimal solution had chosen finishes at
 
\begin_inset Formula $f_{2}$
\end_inset

.
\end_layout

\begin_layout Standard
Since, by definition, our greedy choice finishes first, 
\begin_inset Formula $f_{1}\le f_{2}$
\end_inset

.
 Then, 
\begin_inset Formula $A'_{k}=\left(A_{k}-\left\{ a_{2}\right\} \right)\cup\left\{ a_{1}\right\} $
\end_inset

must also be feasible, because 
\family roman
\series medium
\shape up
\size normal
\emph off
\bar no
\strikeout off
\uuline off
\uwave off
\noun off
\color none

\begin_inset Formula $a_{1}$
\end_inset

 must be compatible just like 
\begin_inset Formula $a_{2}$
\end_inset

 is.
 Therefore, we can always find a optimal solution that includes 
\begin_inset Formula $a_{1}$
\end_inset

.
\end_layout

\begin_layout Subsection
Optimal Substructure Property
\end_layout

\begin_layout Quote
Optimal Substructure Property: An optimal solution to the problem contains
 within it optimal solutions to its subproblems.
\end_layout

\begin_layout Subsubsection
Description In This Case
\end_layout

\begin_layout Standard
The optimal solution (i.e.
 the size of the maximum-size subset of mutually compatible activities)
 to the problem 
\begin_inset Formula $S$
\end_inset

 should contain the greedy choice in every (in the case, only 1) subproblem
 
\begin_inset Formula $S'$
\end_inset

.
\end_layout

\begin_layout Subsubsection
Proof
\end_layout

\begin_layout Enumerate
(Trival steps omitted.)
\end_layout

\begin_layout Enumerate

\series bold
Prove that the sub-solutions in the optimal solution must themselves be
 optimal:
\series default
 
\end_layout

\begin_deeper
\begin_layout Enumerate

\series bold
Declare the optimal solution to a problem:
\series default
 Suppose the optimal solution 
\begin_inset Formula $A$
\end_inset

 to taking the best activity in the subset of 
\begin_inset Formula $S$
\end_inset

 is to take 
\begin_inset Formula $a_{1}$
\end_inset

.
 Then, according to 
\begin_inset Formula $A$
\end_inset

, the optimal solution to the subproblem 
\begin_inset Formula $S'=\{i\in S:s_{i}\ge f_{1}\}$
\end_inset

.
\end_layout

\begin_layout Enumerate

\series bold
Assume there exists a better solution solution:
\series default
 Suppose a better solution to 
\begin_inset Formula $A'$
\end_inset

 is actually 
\begin_inset Formula $B'$
\end_inset

.
 i.e., size(B') > size(A').
\end_layout

\begin_layout Enumerate

\series bold
Using cut-and-paste technique, disprove the optimality of the original solution,
 creating a contradiction:
\series default
 Then, by prepending 
\begin_inset Formula $a_{1}$
\end_inset

 to 
\begin_inset Formula $B'$
\end_inset

, we can create a solution to 
\begin_inset Formula $S$
\end_inset

, called 
\begin_inset Formula $B$
\end_inset

.
 Since 
\begin_inset Formula $|B'|>|A'|$
\end_inset

, 
\begin_inset Formula $|B|=|B'|+1$
\end_inset

 and 
\begin_inset Formula $|A|=|A'|+1$
\end_inset

, then 
\begin_inset Formula $|B|>|A|$
\end_inset

, contradicting to the assumption that 
\begin_inset Formula $A$
\end_inset

 should be the optimal solution (i.e.
 the max-size solution) to 
\begin_inset Formula $S$
\end_inset

.
\end_layout

\begin_layout Enumerate

\series bold
Prove the 
\begin_inset Quotes eld
\end_inset

optimal substrcture
\begin_inset Quotes erd
\end_inset

 property: 
\series default
Therefore, the greedy solution must contain the optimal solution of every
 subproblem.
\end_layout

\end_deeper
\end_body
\end_document