summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJoshua Liu <joshua.liu@sourceobby.com>2026-09-12 22:40:59 -0400
committerJoshua Liu <joshua.liu@sourceobby.com>2026-09-12 22:40:59 -0400
commit729c7d054efd63cbdcee539127a57539aa4f5b5b (patch)
tree4e65d7802487b119ecd4aad13d5944c95aee843b
parentbf7e70d9ead85488b3d2278eb059a32e086e223e (diff)
feat: continuing to work on notes information cutoff 0909 and adding .gitignoremaster
-rw-r--r--.gitignore7
-rw-r--r--main.pdfbin139733 -> 140168 bytes
-rw-r--r--main.tex4
3 files changed, 9 insertions, 2 deletions
diff --git a/.gitignore b/.gitignore
new file mode 100644
index 0000000..bca873b
--- /dev/null
+++ b/.gitignore
@@ -0,0 +1,7 @@
+*.fls
+*.log
+*.out
+*.synctex.gz
+*.toc
+*.aux
+*.fdb_latexmk
diff --git a/main.pdf b/main.pdf
index 6371725..ff4dc44 100644
--- a/main.pdf
+++ b/main.pdf
Binary files differ
diff --git a/main.tex b/main.tex
index 1c80e91..1b7bde7 100644
--- a/main.tex
+++ b/main.tex
@@ -176,7 +176,7 @@ includefoot=true,top=19mm,nohead,footskip=12mm,bottom=6mm]{geometry}
This is also easily disproved as a bad idea. To find a counter example, just take two long jobs that do not conflict, then put a shorter job that conflicts with both.
\subsubsection{Sort jobs by smallest number of job interval conflicts}
This one is also not optimal. It requires a slightly more complex counter example.\\
- Note that this option is also dependent on the order we pick. The counter example chosen illustrates this.
+ Note that this option is also dependent on the order we pick. Why is that? Because {\bf we are ordering by number of conflicts in $\mathcal{J}$.} When we pop an element from $\mathcal{J}$, we remove this element from $\mathcal{J}$, so in reality the number of conflicts is not static, but dynamic. Try it for yourself, and then see how the second example is more resilient against ordering.
\subsubsection{Sort jobs by finish time}
This option will be guaranteed to produce an optimal outcome.\\
\subsection{Proving that sorting by finish time is optimal}
@@ -187,7 +187,7 @@ includefoot=true,top=19mm,nohead,footskip=12mm,bottom=6mm]{geometry}
Running Time:\\
If we pick a competent sorting algorithm, we can finish the sort in $\mathcal{O}(n\log n) + \mathcal{O}(n) = \mathcal{O}(n\log n)$}
\subsubsection{Promising Proof}
- \proofbox{lemma}{bruh}
+ \proofbox{lemma}{bruh}{nada}
We say ``promising'', because here, we want to prove that every partial answer is a subset of an optimal answer. First we will need the promising set lemma, which goes as follows:\\
Lemma: Promising set $\forall\text{ iter } t\exists \text{ opti set } A^*_t \st A_T \subseteq A^*_t$\\
In regular English, this means for each iteration $t$, it's partial solution is a subset of an optimal solution.\\