Ass 2: Finally done

6 files changed, 48 insertions, 22 deletions

diff --git a/ass2/q1/kruskals.py b/ass2/q1/kruskals.py
index 6b73019..d9cc8de 100644
--- a/ass2/q1/kruskals.py
+++ b/ass2/q1/kruskals.py
@@ -7,6 +7,7 @@ class Edge:
     """
     The class which represents an edge in a graph
     """
+
     def __init__(self, start, end, weight):
         self.start = start
         self.end = end
@@ -130,5 +131,6 @@ def main():
     write_output(total_weight, min_span_tree, "output_kruskals.txt")
     print("Done.")
 
+
 if __name__ == "__main__":
     main()
diff --git a/ass2/q2/suffix_array.py b/ass2/q2/suffix_array.py
index 78cf6c4..8efdb04 100644
--- a/ass2/q2/suffix_array.py
+++ b/ass2/q2/suffix_array.py
@@ -1,3 +1,4 @@
+# Alexander Occhipinti - 29994705
 from ass2.ukkonen import Node, ukkonen
 import sys
 
diff --git a/ass2/q3/lcp.py b/ass2/q3/lcp.py
index 6c72771..614b9a2 100644
--- a/ass2/q3/lcp.py
+++ b/ass2/q3/lcp.py
@@ -1,3 +1,4 @@
+# Alexander Occhipinti - 29994705
 import sys
 from ass2.ukkonen import ukkonen, Point, Node
 
diff --git a/ass2/q4/fibonacci.md b/ass2/q4/fibonacci.md
index f550e1b..c22101b 100644
--- a/ass2/q4/fibonacci.md
+++ b/ass2/q4/fibonacci.md
@@ -2,7 +2,7 @@
 title: Assignment 2, **Question 4** - FIT3155
 author: Alexander Occhipinti - 29994705
 date: Week 8 of Semester 2, 2021
-geometry: margin=2cm
+geometry: margin=2.2cm
 header-includes:
 - \usepackage{cancel}
 - \usepackage{qtree}
@@ -74,22 +74,36 @@ Adding the time taken by these three operations results in:
 ## Potential cost
 
 The potential function $\Phi$ we are using is the number of nodes in the root list.
-When we delete the minimum element from the heap, its children become root nodes themselves. This means that the potential function increases by 
-$D_{max}(N)$ (minus 1, but this isn't important for the sake of the cost function) as it is the maximum number of children that a node could have.
-Therefore, the change in potential is:
-$$
-\Phi(D_{i}) - \Phi(D_{i-1}) = D_{max}(N)
-$$
+When we delete the minimum element from the heap, its children become root nodes themselves.
+The most children a node could put into the root on its deletion is $D_{max}(N)$ nodes.
+Since the node that was deleted would have been a root node, the potential only changes by $D_{max}(N) - 1$.
+
+\begin{align*}
+\Delta \Phi &= \Phi(D_{i}) - \Phi(D_{i-1})  \\
+&= T(H) - T(H) + D_{max}(N) - 1 \\
+&= D_{max}(N) - 1
+\end{align*}
 
 ### Scaling units of potential
 
+If we set $m = T(H)$ then we can scale the units of potential by the number of nodes in the root list.
+
 Plugging this into the original amortised cost equation:
 \begin{align*}
     ac_i &= tc_i + m[\Phi(D_{i}) - \Phi(D_{i-1})] \\
-    &= O\big(D_{max}(N) + T(H)\big) + m[\Phi(D_{i}) - \Phi(D_{i-1})] \\
-    &= O\big(D_{max}(N) + T(H)\big) + m[D_{max}(N)]
+    &= O\big(D_{max}(N) + T(H)\big) + T(H)[D_{max}(N) - 1] \\
+    &= O\big(D_{max}(N) + T(H)\big) + T(H) \cdot D_{max}(N) - T(H) \\
+    &= O\big(D_{max}(N)\big) + T(H) \cdot D_{max}(N)\\
 \end{align*}
 
+Since the unit of potential for each newly promoted node underneath the node of degree $D_{max}(N)$ scales with the amount of nodes in the root list $T(H)$, 
+it is safe to say that this cost function outgrows or dominates the $T(H)$ included in the true cost.
+Because of this and the derivation above we can say that:
+
+$$
+ac_i = O\big(D_{max}(N)\big)
+$$
+
 # Part d
 
 Consider a Fibonacci heap where $D_{max}(N) = 3$ named $H_3$.
@@ -152,16 +166,16 @@ This also holds true for $N_1$. Since deleting a tree of degree 1's only child w
 To define a maximally decreased tree of degree $k$, we must delete as many nodes as we can from that tree while preserving the degree of the tree's root. 
 The root must have $k$ direct children at all times in order to remain a tree of degree $k$.
 
-Assume that this property holds for a maximally decreased tree $T$ of degree $k$. (*i.e.* $N_k = F_{k+2}$) *and* for a maximally decreased tree  of degree $k-1$. (*i.e.* $N_{k-1} = F_{k+1}$)
+**Inductive Assumptions:** Assume that this property holds for a maximally decreased tree $T$ of degree $k$. (*i.e.* $N_k = F_{k+2}$) *and* for a maximally decreased tree  of degree $k-1$. (*i.e.* $N_{k-1} = F_{k+1}$)
 
 This means that $T$ must have $k$ children, and that each of those subtrees must also be maximally decreased. This extends down to every node in $T$.
 
-To obtain a maximally decreased tree of degree $k$, we must ask each of the root's children to delete the node with the highest degree out of its children, then tell each of its children to do the same.
-For nodes of rank $0$, they have no children so they remain unaffected.
+To obtain a maximally decreased tree of degree $k$, we must ask each of the root's children to delete the child with the highest degree, then perform the same operation on each of its other children's children.
 The recursively applies the operation to all children in the tree. 
-The reason this forms a maximally decreased tree is because: each node is deleting the most nodes it possibly can with a single delete action, marking that node.
+In the case of nodes of rank $0$: they have no children, so they remain unaffected.
+The reason this forms a maximally decreased tree is because: each node is deleting the most nodes it possibly can with a single delete action, marking that node. We're getting the most ``bang for your buck'' possible from gaining a mark.
 
-We know that a tree of degree $k+1$ can be split into two trees of degree $k$, joined by the link between the root and the node of degree $k$. Let us name the side without the root as $\alpha$ and the one with the root as $\beta$.
+We know that a tree of degree $k+1$ can be split into two trees of degree $k$, joined by the link between the root and the node of degree $k$. Let us name the side without the root node as $\alpha$ and the one with the root as $\beta$.
 When $\alpha$ is maximally decreased, we delete the node of degree $k-1$, marking the node of degree $k$ of $\alpha$. The same is done to all of its children. This results in a maximally decreased tree of degree $k-1$, since the “root” of $\alpha$ was allowed to be marked.
 Due to our assumption of $N_{k-1} = F_{k+1}$, we assume $\alpha$ has $F_{k+1}$ nodes.
 
@@ -170,14 +184,15 @@ Instead, we can treat $\beta$ as a normal tree of degree $k$ and maximally decre
 
 ## Conclusion
 
-Given what's described above, the size of $T$ is the sum of both its halves: $\alpha$ and $\beta$.
+Given what's described above, the size of the tree ($N_{k+1}$) is the sum of both parts: $\alpha$ and $\beta$.
+Using the definition of the Fibonacci sequence which is: $F_n = F_{n-1} + F_{n-2}$ we can conclude that:
 
-Since the definition of the Fibonacci sequence is: $F_n = F{n-1} + F{n-2}$, it can be said that:
 \begin{align*}
     N_{k+1} &= \alpha + \beta \\
     &= F_{k+1} + F_{k+2} \\
     &= F_{k+3}
 \end{align*}
+
 Therefore by the Principle of Mathematical Induction: $N_{k} = F_{k+2}$. $\blacksquare$
 
 # Part g
@@ -269,7 +284,7 @@ This is because an `extract_min` operation will consolidate the stack, using exa
 We can form the following equation:
 \begin{align*}
     \Phi(D_i) - \Phi(D_{i-1}) &= 3 \\
-    \Big[\Delta T(H) + \alpha \Delta M(H)\Big]_{i} - \Big[]\Delta T(H) + \alpha \Delta M(H)\Big]_{i-1} &= 3 \\
+    \Big[\Delta T(H) + \alpha \Delta M(H)\Big]_{i} - \Big[\Delta T(H) + \alpha \Delta M(H)\Big]_{i-1} &= 3 \\
     (1+ 1\alpha) - (2 + -\alpha) &= 3 \\
     (1+ \alpha) - (2 -\alpha) &= 3
 \end{align*}
@@ -316,3 +331,9 @@ This is why it makes sense for each marking operation to be worth 2 cost.
 Another thing to note is that 2 is the only positive integer constant that is related marking nodes, regardless of all parameters for the reasons stated above. 
 The number 2 in this case is kind of baked into the idea of marking nodes in a Fibonacci heap.
 
+
+\begin{center}
+    \texttt{-=o0o=-} \\
+    \texttt{END} \\
+    \texttt{-=o0o=-}
+\end{center}
\ No newline at end of file
diff --git a/ass2/q4/fibonacci.pdf b/ass2/q4/fibonacci.pdf
new file mode 100644
index 0000000..cec8add
--- /dev/null
+++ b/ass2/q4/fibonacci.pdf
diff --git a/ass2/ukkonen.py b/ass2/ukkonen.py
index 5aa94e7..eb49820 100644
--- a/ass2/ukkonen.py
+++ b/ass2/ukkonen.py
@@ -1,4 +1,5 @@
 """
+Alexander Occhipinti - 29994705
 This file is imported into questions 2 and 3.
 """
 
@@ -39,12 +40,12 @@ class OrderedDict(dict):
         """
         Define a number value to an alphabet letter, including special characters so they can fit in a list
         """
-        if char == "$":
-            return 26
-        elif char == "&":
-            return 27
+        if char == "$":  # Designates end of string
+            return 0
+        elif char == "&":  # Designates break in two strings (Used for Q3)
+            return 1
         else:
-            return ord(char) - 96
+            return ord(char) - 95  # Letters a-z
 
 
 class Node: