diff options
| author | Joshua Liu <joshua.liu@sourceobby.com> | 2026-09-12 22:40:59 -0400 |
|---|---|---|
| committer | Joshua Liu <joshua.liu@sourceobby.com> | 2026-09-12 22:40:59 -0400 |
| commit | 729c7d054efd63cbdcee539127a57539aa4f5b5b (patch) | |
| tree | 4e65d7802487b119ecd4aad13d5944c95aee843b | |
| parent | bf7e70d9ead85488b3d2278eb059a32e086e223e (diff) | |
feat: continuing to work on notes information cutoff 0909 and adding .gitignoremaster
| -rw-r--r-- | .gitignore | 7 | ||||
| -rw-r--r-- | main.pdf | bin | 139733 -> 140168 bytes | |||
| -rw-r--r-- | main.tex | 4 |
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 Binary files differ@@ -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.\\ |
