<commit_before>\documentclass{article}
\usepackage{listings}	% add code segment
\usepackage{titlesec}   %set the page head/foot

\title{Algorithm Homework 4}
\author{<NAME>}

\newpagestyle{maintest}
{            
    \sethead{<NAME>}{<EMAIL>}{#01516178}     % %
    \setfoot{}
    \headrule
    \footrule
}
\newpagestyle{maintest}

\begin{document}

\section{Q1}
Following the next four steps for verification and if doesn't meet then we could know this algorithm is not optimal.

1)First for the basic comparasion, check the source(starting code)'s d value and predecessor. It should be
s.d = 0 and s.$\pi$ = NIL(as we know source should not have the predecessor)

2)Then we can traverse all the other vertex to verify whether the weight and predecessor is right, that's to
say that they should meet the following equations:
$$v.d = v.\pi + w(v.\pi, v) $$

3) After the above step we can verify the connecting point's relation, as they have predecessor, but some points
which may not have the similar connecting. If they don't have predecessor, then the value $v.\pi$ should be NIL
and the value $v.d$ should be $\infty$


4) For any verification of the above step, if it doesn't mean the requirement, then we know it is not the shortest
path's solution since they're the basic property of shortest path, the complexity of these steps are $O(V)$. After
that, we need to verify that it's optimal, which is shortest, we need to apply each pass of Bellman-Ford, which is
just like each pass of the graph, and its complexity is $O(E)$, if it changes then we know it's not optimal and could
be reduced again. So the total complexity is $O(V+E)$.

\section{Q2}
In Dijkstra's algorithm, we start from a fixed source whose weight is zero and it has no predecessor, all other nodes
are initialized as the $\infty$.

However, here the difference is that we should start from a given source, not the source point above. Since all other
nodes are $\infty$, we cannot apply the original algorithm to do the relaxation. From the question, we know that the
weight is W at most, so the maximum value of the longest path is $(V-1)W$, which is smaller than $\infty$<commit_msg>add page foot and head for assignment<commit_after>\documentclass{article}
\usepackage{listings}	% add code segment
\usepackage{titlesec}   %set the page head/foot
%\usepackage{lastpage} % maybe used using Lastpages
\usepackage[page]{totalcount}

\title{Algorithm Homework 4}
\author{<NAME>}

\begin{document}

\newpagestyle{main}{            
    \sethead{<NAME>}{HW4}{<EMAIL>} % I don't know why here must use two "\" before to input @
    % and also know that strange error is often caused by the special characters.
    % here the \thepage is very useful to add for page number in the right part
    % \setfoot{}{}{\thepage} % just output the page number
    \setfoot{}{}{\thepage\ \// \totalpages} % add totalpages then needs page package and totalcount
    \headrule
    \footrule
}
\pagestyle{main}

%\clearpage


\section{Q1}
Following the next four steps for verification and if doesn't meet then we could know this algorithm is not optimal.

1)First for the basic comparasion, check the source(starting code)'s d value and predecessor. It should be
s.d = 0 and s.$\pi$ = NIL(as we know source should not have the predecessor)

2)Then we can traverse all the other vertex to verify whether the weight and predecessor is right, that's to
say that they should meet the following equations:
$$v.d = v.\pi + w(v.\pi, v) $$

3) After the above step we can verify the connecting point's relation, as they have predecessor, but some points
which may not have the similar connecting. If they don't have predecessor, then the value $v.\pi$ should be NIL
and the value $v.d$ should be $\infty$


4) For any verification of the above step, if it doesn't mean the requirement, then we know it is not the shortest
path's solution since they're the basic property of shortest path, the complexity of these steps are $O(V)$. After
that, we need to verify that it's optimal, which is shortest, we need to apply each pass of Bellman-Ford, which is
just like each pass of the graph, and its complexity is $O(E)$, if it changes then we know it's not optimal and could
be reduced again. So the total complexity is $O(V+E)$.

\section{Q2}
In Dijkstra's algorithm, we start from a fixed source whose weight is zero and it has no predecessor, all other nodes
are initialized as the $\infty$.

However, here the difference is that we should start from a given source, not the source point above. Since all other
nodes are $\infty$, we cannot apply the original algorithm to do the relaxation. From the question, we know that the
weight is W at most, so the maximum value of the longest path is $(V-1)W$, which is smaller than $\infty$
{'fraction_non_alphanumeric': 0.07909604519774012, 'fraction_numerical': 0.005649717514124294, 'mean_word_length': 4.058201058201059, 'pattern_counts': {'":': 0, '<': 9, '<?xml version=': 0, '>': 9, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '1515284', 'n_tokens_mistral': 1360, 'n_tokens_neox': 1293, 'n_words': 724}