main.tex

\documentclass[a4paper]{article} 
\input{head}
\usepackage{algorithm}
\usepackage[noend]{algpseudocode}
\newcommand{\algrule}[1][.2pt]{\par\vskip.5\baselineskip\hrule height #1\par\vskip.5\baselineskip}
\begin{document}

%-------------------------------
%	TITLE SECTION
%-------------------------------

\title{\textbf{COL351 : Analysis and Design of Algorithm \\ Assignment 2 }}
\author{Gaurav Jain (2019CS10349) \& T Abishek (2019CS10407)}
\date{}
%-------------------------------
%	CONTENTS
%-------------------------------

\maketitle

\section{Algorithms Design book}

Algorithm to partition the chapters into 3 sets $S_1$, $S_2$, $S_3$, so that maximum sum of each set in minimised.

\textbf{Observation:}\\
To minimize the objective, we can find the minimum of every possibility of a chapter being assigned to all 3 sets. We can achieve this by dynamic programming.

\textbf{Algorithm:}
    
    {\centering
    \begin{minipage}{\linewidth}
    \begin{algorithm}[H]
    \caption{Minimisation}\label{alg:ts}
    \begin{algorithmic}[1]
    \Procedure{DP}{a,b,c,i, P, M}\Comment{a,b,c: sum of questions given to Alice, Bob and Charlie}
    \If {M[a][b][c][i] $\neq$ -1}
        \State \Return M[a][b][c][i]
    \EndIf
    \State M[a][b][c][i] = min(DP(a+P[i],b,c,i+1), DP(a,b+P[i],c,i+1), DP(a,b,c+P[i], i+1))
    \State \Return M[a][b][c][i]
    \EndProcedure
    
    \Procedure{Start}{P, n}
    \State n $\gets$ no. of chapters
    \State P $\gets$ P is array where P[i] is no. of questions in chapter i( 1 to n)
    \State M $\gets$ M is matrix which is used to store computed totals in DP (initially -1)
    \For{i from 0 to $n^2$}
        \For{j from 0 to $n^2$}
            \For {k from 0 to $n^2$}
                \State M[i][j][k][n] = max(i,j,k)
    \EndFor
    \EndFor
    \EndFor
    \State \Return DP(0,0,0,1,P,M)
    \end{algorithmic}
    \end{algorithm}
    \end{minipage}
    \par}
    
    \textbf{Runtime Analysis:}\\
    This is dynamic programming problem, and in the worst case, all the elements of the matrix M will have to be filled to the final answer we are looking for. Dimensions a, b and c can be maximum $n^2$, because each chapter has a maximum of n questions and there are n chapters, so the maximum no. of questions is $n^2$, and thus each person can be assigned a maximum of $n^2$ questions. Dimension i can be maximum n, as there are only n chapters. So, no. of elements in M is $(n^2)^3*n = n^7$, So, the Time Complexity is O($n^7$).
    
    \textbf{Correctness of Algorithm:}\\
    The correctness of the algorithm can be proved using induction.
    
    
    \textit{Base Case:}\\
    When all chapters are assigned i.e. $i=n$ in procedure DP, the max value of a,b and c is max(i,j,k) which is the optimal solution.
    
    
    \textit{Induction Hypothesis:}\\
    For all $n \geq j > i$ the algorithm provides the optimal solution using chapters $P[1],P[2],...,P[j]$. 
    
    \textit{Induction Step:}\\
    The $i^{th}$ chapter can be assigned to any of the three sets a, b or c. Thus, the optimal solution is the minimum of the three subproblems generated by including questions of chapter $i$ to the any one of the three sets. 
    
    By induction, the proof for all chapters. Hence, the algorithm gives an optimal solution to the problem.
    
    \hfill\qedsymbol
    
\newpage
\section{Course Planner}
\begin{enumerate}[1.]
\item Algorithm to find an order for taking the courses so that a student is able to take all the courses with the prerequisite criteria being satisfied.

    \textbf{Representation:}
    
    All courses are represented as vertices in a directed graph, with the in-edges of every vertex being the prerequisites. 
    
    \textbf{Observation:}
    The order is required in such a way that all the prerequisites of a course is done before it, i.e, in the required order, all the edges go from left to right and there exists no edge from right to left. This is the same as the aim of topological sorting which can be achieved with a small modification to DFS.
    
    \textbf{Algorithm:}
    
    {\centering
    \begin{minipage}{\linewidth}
    \begin{algorithm}[H]
    \caption{Topological sorting}\label{alg:ts}
    \begin{algorithmic}[1]
    \Procedure{Topsort}{Graph $G$, $S$, Node $x$, visited}
    %\State $distance \gets$ array of size $|V|$
    \State visited[x] = grey
    \For{each vertex $v$ in $N(x)$} %\Comment{Changing edge weights}
        \If{$visited[v] = white$}
            \State Topsort(G, S, v, visited) 
        \EndIf
        \If{$visited[v] = grey$}
            \State \Return Error: Not Possible 
        \EndIf
        
    \EndFor
    \State S.insertFront(x)
    \State visited[x] = black
    
    
    \EndProcedure
    
    \Procedure{Initial}{Graph $G$}
    \State visited $\gets$ array of size of number of vertices(initially white)
    \State S $\gets$ order of taking courses(initially empty)
    \For{each vertex $v$ in G}
        \If{$visited[v] = white$}
            \State Topsort(G, S, v, visited) 
        \EndIf
    \EndFor
    \State \Return S
    \EndProcedure
    \end{algorithmic}
    \end{algorithm}
    \end{minipage}
    \par}
    
    \textbf{Runtime Analysis:}\\
    As discussed in class, the runtime complexity of topological sort is equivalent to DFS, i.e, O(m+n).
    
    \textbf{Correctness of Algorithm:}\\
    There can be no cycles in the graph that we are given so the given graph is a DAG and as discussed in class, topological sort guarantees a order of vertices in case of DAG where edges only go from left to right and not the other way. If we follow this order, it would satisfy the requirement that all courses have to be done only after their prerequisites are completed, as the source of edges represent the destination's prerequisites.
    
    \hfill\qedsymbol
    
\newpage
\item Algorithm to find the minimum number of semesters needed to complete
all n courses.

\textbf{Algorithm:}
    
    {\centering
    \begin{minipage}{\linewidth}
    \begin{algorithm}[H]
    \caption{Minimum no. of semesters}\label{alg:ms}
    \begin{algorithmic}[1]
    \Procedure{Minimum\_semester}{Graph G}
    %\State $distance \gets$ array of size $|V|$
    \State $D \gets$ array of buckets where vertices are arranged by their degree
    \State count = 0
    \While{G $\neq$ EMPTY}
        \If{D[0] = EMPTY}
            \State \Return Error: No order possible
        \EndIf
        \For{$v \in D$ with $deg(v) = 0$}
            \State \textsc{RemoveVertex}($G,v$)
        \EndFor
        \State count = count + 1
    

    \EndWhile
    \State \Return count
    
    \EndProcedure
    
    \Procedure{RemoveVertex}{$G,v$}\Comment{Reduces degrees of vertices connected to $v$}
    \State Mark $v$ \Comment{$v$ is removed from invitees list}
    \State $D[deg(v)].\textsc{remove}(v)$
    \For{$j$ from $1$ to $deg(v)$}
    \State $u \gets adj(v)(j)$
    \If{$u$ is marked} 
    \State \textbf{continue}
    \EndIf
    %\State Delete $v$ from $adj(u)$
    \State $deg(u) \gets deg(u)-1$
    \State $D[deg(u)+1].\textsc{remove}(u)$
    \State $D[deg(u)].\textsc{insert}(u)$
    \EndFor
    \EndProcedure
    \end{algorithmic}
    \end{algorithm}
    \end{minipage}
    \par}
    
    
    \textbf{Runtime Analysis:}\\
    The graph is stored in adjacency list as a HashMap mapping each vertex to an unordered set of connected vertices. The time taken to make the graph is $O(m)$.
    Degree of all vertices is also stored separately as a HashMap to give $O(1)$ access to degrees of each vertex and updated accordingly.
    
    The degree of all the vertices is then sorted using bucket sort with each bucket being an unordered set(Hash) of vertices which allows us to insert and remove in  $O(1)$ time. The buckets themselves are stored as an array of buckets of size N, with the index of the bucket representing the degree of the vertices stored in them. The initial sorting takes $O(m)$ as it is done through a single pass.
    
    The inner FOR loop inside the WHILE loop in the Select procedure, is also run only $O(n)$ times as each iteration, a vertex is removed, and the maximum no. of vertices that can be removed is n. 
    
    Since the number of edges are $m$ so the procedure \textsc{RemoveVertex}'s FOR loop runs atmost $2*m$  over all the calls as the procedure is called for each vertex only once, and the for loop is run degree(v) times. Sum of the degrees of all the vertices is $2*m$. So the overall running time of the algorithm is $O(m+n)$.
    Since $m \leq n^2$ so the time complexity is $O(n^2)$.
    
    \textbf{Correctness of Algorithm:}\\
    Claim: Let P be an array of sets, where P[i] = set of courses done by semester i. Let P' be the array representing the optimal(minimum) order of courses and let P be the array representing the above algorithm. Claim is P'[i] $\subseteq$ P[i] for all i.
    
    Proof: Proof by induction on i
    
    Base Case: i = 1\\
    When i=1, the algorithm picks all the courses that don't have any prerequisites and the optimal order can't pick more courses than the given algorithm as there are no more courses left that can be taken.
    
    Induction Hypothesis:\\
    P'[j] $\subseteq$ P[j] for all j $<=$ i-1
    
    Induction Step:\\
    for i, as P'[i-1] $\subseteq$ P[i-1], the courses that can be done in the ith semester (all prerequisites cleared) by our algorithm must be at least the same as the optimal algorithm. And as our algorithm picks all the eligible courses again, the optimal algorithm can't pick more courses than the given algorithm. Thus, P'[i] $\subseteq$ P[i].
    
    Therefore, the claim is proved, and the algorithm provides the optimal way to finish the courses in minimum no. of semesters. 
    
    {\hfill\qedsymbol}
    
\newpage

\item Algorithm to compute the set of all those course pairs whose prerequisites and ancestors don't intersect.

\textbf{Algorithm:}
    
    {\centering
    \begin{minipage}{\linewidth}
    \begin{algorithm}[H]
    \caption{Set of no intersection}\label{alg:ms}
    \begin{algorithmic}[1]
    \Procedure{Non\_intersection}{Graph G}
    %\State $distance \gets$ array of size $|V|$
    \State $D \gets$ array of buckets where $D[i]$ is a bucket with nodes of $i$ indegree
    \State $Root$ $\gets$ boolean array for each node mapping that node to its ancestor with degree 0
    \State $Removed \gets$ the nodes removed from the graph(initially empty)
    \State $P \gets$ the required set (initially empty)
    \While{G $\neq$ EMPTY}
        \If{D[0] = EMPTY}
            \State \Return Error: No order possible
        \EndIf
        \For{$v \in D$ with $deg(v) = 0$}
            \State \textsc{RemoveVertex}($G,v$)
            \For{$t$ in Removed}
                \If{\textsc{Check(v,t)}}
                    \State P.add(v,t)
                    \State P.add(t,v)
                \EndIf
            \EndFor
            \State Removed.add(v) 
        \EndFor
        
    

    \EndWhile
    \State \Return $P$
    
    \EndProcedure
    \algrule
    \Procedure{RemoveVertex}{$G,v$}\Comment{Reduces degrees of vertices connected to $v$}
    
    \State $D[deg(v)].\textsc{remove}(v)$
    \For{$j$ from $1$ to $deg(v)$}
    \State $u \gets adj(v)(j)$
    \If{$u$ is marked} 
    \State \textbf{continue}
    \EndIf
    %\State Delete $v$ from $adj(u)$
    \State $deg(u) \gets deg(u)-1$
    \State $D[deg(u)+1].\textsc{remove}(u)$
    \State $D[deg(u)].\textsc{insert}(u)$
    \For{$i$ from $0$ to $size(Root(u))$}
        \If{Root(v)[i]}
        Root(u)[i] = True
        \EndIf
    \EndFor
    \EndFor
    \EndProcedure
    \algrule
    \Procedure{Check}{$v, u$}\Comment{Checks whether the 2 nodes don't have any common ancestors}
    \For{$i$ from $0$ to $size(Root(u))$}
        \If{Root(u)[i] and Root(y)[i]}
            \State \Return False
        \EndIf
    \EndFor
    \State \Return True
    \end{algorithmic}
    \end{algorithm}
    \end{minipage}
    \par}
    
    \textbf{Runtime Analysis:}\\
    The subroutine \textsc{RemoveVertex} can take $O(n)$ time and the subroutine \textsc{Check} can also take $O(n)$ time for each vertex. The size of $Removed$ array can grow upto $O(n)$ and thus, for each vertex we may end up checking for all elements present in $Removed$ in $O(n^2)$ time.\\
    Thus, the total time complexity of the algorithm is $O(n^3)$. The space complexity can be $O(n^2)$ when all nodes are independent. 
    
    \textbf{Correctness of Algorithm:}\\
    We can prove the correctness of the algorithm by contradiction by assuming that there exists a pair of vertices which is not selected by the algorithm.
    Suppose the pair is $(u,v)$ and at some stage of the algorithm, degree of $u$ is 0 (as ancestors of $u$ is finite). So, at this stage $u$ is added to the $Removed$ array. Consider the stage at which degree of $v$ becomes 0.\\ Without loss of generality, assume that $u$ is added to $Removed$ first compared to $v$. Thus, the procedure \textsc{Check} will be called using $(u,v)$. So, this pair will be checked and added to $P$ if there is no common ancestor between them. This is a contradiction as we assumed that the algorithm will not find $(u,v)$. 
    
    {\hfill\qedsymbol}
    
    
\end{enumerate}
\newpage
\section{Forex Trading}
\begin{enumerate}[1.]
    \item Algorithm to verify whether or not there exists a cycle such that exchanging money over this cycle results in positive gain.
    
    \textbf{Observation:}
    
    A number $x$ is strictly larger than $1$ if and only if $log(1/x) > 0$.
    
    \begin{center}
        So, if we want ${R[i_1,i_2]R[i_2,i_3]...R[i_{k-1},i_k]R[i_k,i_1] > 1}$

        Then ${log(1/R[i_1,i_2]R[i_2,i_3]...R[i_{k-1},i_k]R[i_k,i_1]) < 0}$
        
        $\implies log(1/R[i_1,i_2]) + log(1/R[i_2,i_3]) + ..... + log(1/R[i_{k-1},i_k] + log(1/R[i_k,i_1]) < 0$
        
        $\implies R'[i_1,i_2] + R'[i_2,i_3] + ..... + R'[i_{k-1},i_k] + R'[i_k,i_1] < 0$
    \end{center}
    Since this problem is related to forex trading where it is suitable to assume that every currency is exchangeable with any other currency either directly or indirectly so it is assumed that the graph generated by the currency exchange is connected.  \\
    Thus, the problem can be reduced to finding a negative weight cycle in a (connected) graph where weight of edges is given by
    \begin{center}
        $R'[i_p,i_{p+1}] = log(1/R[i_p,i_{p+1}])$
    \end{center}
    A negative weight cycle can be detected easily in a (connected) graph using Bellman-Ford Algorithm.
    
    \textbf{Algorithm:}
    
    {\centering
    \begin{minipage}{\linewidth}
    \begin{algorithm}[H]
    \caption{Negative Cycle Detection Algorithm}\label{alg:dc}
    \begin{algorithmic}[1]
    
    \Procedure{NegativeCycleDetect}{Graph $G$, $S$}
    
    \State $distance \gets$ array of size $|V|$
    \For{$i=0$ to $m-1$} \Comment{Changing edge weights}
        \State $R'(e_i) \gets log(1/R(e_i))$
    \EndFor
    
    \For{each vertex $v$ in $G$}
    \State $distance[v] \gets \infty$
    \EndFor

    \State $distance[S] \gets 0$
    
    \For{$i=0$ to $n-1$}
        \For{each edge $(u,v)$ in $G$}
            \If{$distance[u]+R'[u,v] < distance[v]$}
            \State $distance[v] \gets distance[u]+R'[u,v]$ 
            \EndIf
        \EndFor
    \EndFor
    
    \For{each edge $(u,v)$ in $G$}
        \If{$distance[u]+R'[u,v] < distance[v]$}
        \State\Return True
        \EndIf
    \EndFor
    
    \State\Return False
    
    \EndProcedure
    
    \end{algorithmic}
    \end{algorithm}
    \end{minipage}
    \par}
    
    \textbf{Runtime Analysis:}\\
    Edge weights are changed in $O(m)$ time. After changing the edge weights, the rest part of the algorithm is identical to the standard Bellman-Ford Algorithm which has time complexity $O(mn)$ and space complexity $O(n)$.\\
    Thus, the total time complexity is $O(mn)$ and space complexity is $O(n)$.
    
    \textbf{Correctness of Algorithm:}\\
    The conversion of edge weights is explained in the observation section above and this conversion leads to a standard problem of shortest paths- Bellman-Ford Algorithm. The correctness of Bellman-Ford Algorithm is discussed in the lectures of the course. Thus, by reducing the problem to another problem, the algorithm is designed to find the solution of the problem.
    
    \hfill\qedsymbol
    \newpage
 %-------------------------------------------------------------------------% 
    \item Algorithm to print out such a cyclic sequence defined in part 1, if it exists.
    
    \textbf{Algorithm:}
    
    {\centering
    \begin{minipage}{\linewidth}
    \begin{algorithm}[H]
    \caption{Print Negative Cycle Algorithm}\label{alg:pfc}
    \begin{algorithmic}[1]
    \Procedure{PrintNegativeCycle}{Graph $G$, $S$}
    \State $distance \gets$ array of size $n$
    \State $parent \gets$ array of size $n$ 
    \For{$i=0$ to $m-1$} \Comment{Changing edge weights}
        \State $R'(e_i) \gets log(1/R(e_i))$
    \EndFor
    
    \For{each vertex $v$ in $G$}
    \State $distance[v] \gets \infty$
    \EndFor

    \State $distance[S] \gets 0$
    
    \For{$i=0$ to $n-1$}
        \For{each edge $(u,v)$ in $G$}
            \If{$distance[u]+R'[u,v] < distance[v]$}
            \State $distance[v] \gets distance[u]+R'[u,v]$ 
            \State $parent[v] \gets u$
            \EndIf
        \EndFor
    \EndFor
    \algrule
    \State $cycle \gets$ sequence of nodes containing a cycle
    
    \For{each edge $(u,v)$ in $G$}
        \If{$distance[u]+R'[u,v] < distance[v]$} \Comment{Cycle detected}
        \State $p \gets v$
        \For{$i = 0$ to $n-1$}
            \State $p \gets parent[p]$
        \EndFor
        
        \State Add $p$ to $cycle$
        \While{$i$ is not $p$}
            \State Add $i$ to $cycle$
            \State $i \gets parent[i]$
        \EndWhile
        
        \State \Return $cycle$
        \EndIf
    \EndFor
    
    \State\Return False
    
    \EndProcedure

    \end{algorithmic}
    \end{algorithm}
    \end{minipage}
    \par}
    
    \textbf{Runtime Analysis:}\\
    The time complexity of this algorithm is same as the previous one because in this algorithm, we only add a $parent$ array to store the previous element of a node in the shortest path tree.\\
    Thus, the space complexity is $O(n)$ and the time complexity is $O(mn)$.
    
    \textbf{Correctness of Algorithm:}\\
    Printing negative cycle in a graph is a standard problem based on the Bellman-Ford algorithm. Similar to the previous algorithm, we stop when an update is possible in the $n^{th}$ iteration and using the $parent$ array, we backtrack to reach the starting point. The correctness of this algorithm is strongly related to the previous one which is based on Bellman-Ford algorithm and its correctness is discussed in the lectures.
    
    \hfill\qedsymbol
\end{enumerate}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newpage
\section{Coin Change}
\begin{enumerate}[1.]
    \item Algorithm to count the number of ways to make change for Rs. $n$,
    given an infinite amount of coins/notes of denominations $d[1],...,d[k]$.
    
    \textbf{Recurrence Relation:}
    
    Let $C(n,m)$ represent the number of ways to make change for Rs. $n$ using coins of denomination $d[1],...,d[m]$.
    
    The solution of $C(n,m)$ can be partitioned into two parts:
    \begin{itemize}
        \item Solution containing at least one coin of denomination $d[m]$. The subproblem here is to count number of ways to make change of Rs. $n-d[m]$ using $d[1],...,d[m]$ i.e. $C(n-d[m],m)$.
        \item Solution containing no coins of denomination $d[m]$. The subproblem here is to count number of ways to make change of Rs. $n$ using $d[1],...,d[m-1]$ i.e. $C(n,m-1)$.
    \end{itemize}
    Thus, the recurrence relation is formulated as:
    \begin{equation}
        C(n,m) = C(n,m-1) + C(n-d[m],m)
    \end{equation}
    with the base cases:
    \begin{itemize}
        \item $C(n,m) = 1$ when $n=0$ (No coin change)
        \item $C(n,m) = 0$ when $n<0$ (Negative money)
        \item $C(n,m) = 0$ when $n>0$ and $m\leq0$ (No coin left)
    \end{itemize}
    
    \textbf{Algorithm:}
    
    {\centering
    \begin{minipage}{\linewidth}
    \begin{algorithm}[H]
    \caption{Coin Change Algorithm}\label{alg:cc}
    \begin{algorithmic}[1]
    \Procedure{CoinChange}{$n$, set of coins $d[1],d[2],...,d[k]$}
    \State $count \to$ 2D array of size $(n+1) \times k$
    \For{$i=0$ to $n$}
    \For{$j=1$ to $k$}
    \If{$i=0$}
        $count(i,j) \gets 1$
    \ElsIf{$j=0$} 
        \If{$i\mod d[j] = 0$} $count(i,j) \gets 1$
        \Else{} 
        $count(i,j) \gets 0$        
        \EndIf
    \ElsIf{$d[j]>i$} $count(i,j) \gets count(i,j-1)$
    \Else{} $count(i,j) \gets count(i,j-1)+count(i-d[j],j)$
    \EndIf
    \EndFor
    \EndFor
    \State \Return $count(n,k)$
    \EndProcedure
    \end{algorithmic}
    \end{algorithm}
    \end{minipage}
    \par}
    
    \textbf{Runtime Analysis:}
    
    Like other dynamic programming problems, this algorithm fills the complete 2D array $count$ in a single pass. So, the time complexity as well as space complexity is $O(nk)$.
    
    \textbf{Correctness of Algorithm:} Proof by Induction on $i$
    
    \textit{Base Case:}\\
    There are three base cases: 
    \begin{itemize}
        \item When no amount is left to make change. In this case, there is only 1 way to make change.
        \item When the amount is negative, there is no way to make change. Thus, $C(n,m) = 0$ is 0 in this case.
        \item When there is some amount left but no coins are left to make change. Thus, in this case, number of ways to make change is 0.
    \end{itemize}
    
    \textit{Induction Hypothesis:}\\ The algorithm gives the correct count of the number of ways to make change for all values of Rs. $p < i$ using coins of denominations $d[1], d[2],...,d[j]$ and number of ways to make change of Rs. $i$ using coins of denomination $d[1],d[2],...,d[q]$ for all $q<j$.
    
    \textit{Induction Step:}\\
    To calculate the number of ways to make change of Rs. $i$ using coins of denomination $d[1],d[2],...,d[j]$. We can either include the coin of denomination $d[j]$ or exclude it.\\
    By induction hypothesis, we have the number of ways to make change of Rs. $i$ using $d[1],d[2],...,d[j-1]$. We also have the number of ways to make change of Rs. $i-d[j]$ using coins of denomination $d[1],d[2],...,d[j]$.\\
    Thus, the total number of ways is calculated by using these two subproblems solutions.
    \hfill\qedsymbol
    
%----------------------------------------------------------------------%    
    \newpage
    \item Algorithm to find a change of Rs. $n$ using the minimum number of coins. 
    
    \textbf{Recurrence Relation:}
    
    Let $C(n)$ represent the minimum number of coins required to make change for Rs. $n$ using coins of denomination $d[1],...,d[m]$.
    
    $C(n)$ is minimum of the subproblems generated by using one coin of $d[j]$ denomination. The recurrence relation is formulated as:
    \begin{equation}
        C(n) = min(C(n) , 1+C(n-d[j]))~\forall j \in [1,m]
    \end{equation}
    with the base case:
    $C(n) = 0$ when $n=0$ (No coin change)

    
    \textbf{Algorithm:}
    
    {\centering
    \begin{minipage}{\linewidth}
    \begin{algorithm}[H]
    \caption{Min Coin Change Algorithm}\label{alg:mc}
    \begin{algorithmic}[1]
    \Procedure{MinCoinChange}{$n$, set of coins $d[1],d[2],...,d[k]$}
    \State $count \to$ array of size $n+1$
    \State $previous \to$ array of size $n+1$
    \State $count[0] = 0$
    \State $previous[0] = Null$
    \For{$i=1$ to $n$}
        \State $minimum \gets \infty$
        \State $minprevious \gets Null$
        \For{$j=1$ to $k$}
            \If{$i \geq d[j]$}
                \State $minimum \gets min(minimum,1+count[i-d[j]])$
                \State $minprevious \gets i-d[j]$
            \EndIf
        \EndFor
        \State $count[i] \gets minimum$
        \State $previous[i] \gets minprevious$
    \EndFor
    \State $change \to$ list of coins required 
    \State $x \gets n$
    \While{$previous[x] \neq Null$}
        \State $change.append(x-previous[x])$
        \State $x \gets previous[x]$
    \EndWhile
    \State \Return $change$
    \EndProcedure
    \end{algorithmic}
    \end{algorithm}
    \end{minipage}
    \par}
    
    \textbf{Runtime Analysis:}
    
    Like other dynamic programming problems, this algorithm fills the complete array $count$ in a single pass. There are two nested for loops which run $n$ and $k$ times respectively. So, the time complexity is $O(nk)$. The space complexity is $O(n)$ to store the $previous$ array.
    
    \textbf{Correctness of Algorithm:} Proof by Induction on $i$
    
    \textit{Base Case:} $i=0$\\ When $i=0$ the number of coins required to make change is zero. The algorithm is initialized with $count[i]=0$ when $i=0$. So, base case holds.
    
    \textit{Induction Hypothesis:}\\ The algorithm gives the correct count of the minimum number of coins required to make change for all values of Rs. $j < i$.
    
    \textit{Induction Step:}\\ 
    Consider the $i^{th}$ iteration of the outer for loop, the algorithm finds the minimum coins required to make change for Rs. $i$ by using a coin of denomination of $d[j]$ and breaking the problem into various subproblems.\\
    By induction hypothesis, the solution given by the algorithm of these subproblems is optimal and thus, we only need to add one coin of denomination $d[j]$ (which gives the minimum) to the coin sequence.
    
    \hfill\qedsymbol
    
    
\end{enumerate}
%------------------------------------------------

\end{document}