commit 2465551bbb0e3a700fab5061d88ba4108b6014ba
parent fa6653a2c1f3649861c424d86b1533e1a08acecb
Author: Andrew Laack <andrew@laack.co>
Date: Sun, 13 Sep 2026 13:16:05 -0500
Updated some docs for algos
Diffstat:
9 files changed, 66 insertions(+), 2 deletions(-)
diff --git a/docs/Algorithms.md b/docs/Algorithms.md
@@ -4,6 +4,7 @@ This is an index for links to notes taken about algorithms. These are CS related
## Links
+- [Quickselect](Quickselect.md)
- [Monte Carlo Method](MonteCarloMethod.md)
- [Las Vegas Method](LasVegasMethod.md)
- [Perlin Noise](PerlinNoise.md)
diff --git a/docs/CS3110.md b/docs/CS3110.md
@@ -0,0 +1,9 @@
+# CS 3110
+
+This is the index for my CS 3110 (Data Structures and Functional Programming) notes.
+
+[https://www.cs.cornell.edu/courses/cs3110/2025sp/](https://www.cs.cornell.edu/courses/cs3110/2025sp/)
+
+## Links
+
+- [OCaml](OCaml.md)
diff --git a/docs/ComputerScience.md b/docs/ComputerScience.md
@@ -6,6 +6,7 @@ This is the index for my Computer Science related notes.
- [CS 202](CS202.md)
- [CS 331](CS331.md)
+- [CS 3110](CS3110.md)
- [Math 310](Math310.md)
- [Computer Security](ComputerSecurity.md)
- [Probabilistic Robotics](ProbabilisticRobotics.md)
diff --git a/docs/Darcs.md b/docs/Darcs.md
@@ -0,0 +1,21 @@
+# Darcs
+
+**Source:** [https://darcsbook.acmelabs.space/chapter01.html](https://darcsbook.acmelabs.space/chapter01.html)
+
+**Definition:** Darcs is a distributed version control system based on the theory of patches.
+
+## Why?
+
+Darcs is quite nice to use because it makes sense. A repository is just a set of changes. This is not true with git where ordering matters, but such a stipulation feels rather arbitrary.
+
+### Commutation
+
+If there are two patches A and B that both create disjoint files, the order of their application doesn't impact the final state we are in. This is called commutation. This is to say, A(B(x)) = B(A(x)).
+
+### Commands
+
+- log
+- rollback
+- init
+- record
+-
diff --git a/docs/DeveloperTooling.md b/docs/DeveloperTooling.md
@@ -11,4 +11,4 @@ Index for links to notes on developer tooling
### Patch Based VCSs
- [Pijul](Pijul.md)
-- Darcs
+- [Darcs](Darcs.md)
diff --git a/docs/LasVegasMethod.md b/docs/LasVegasMethod.md
@@ -2,4 +2,6 @@
SS
-**Definition:** The Las Vegas method is similar to the monte carlo method as it uses random sampling, but it always gives the correct answer whereas the monte carlo method does not guarantee a correct answer.
+**Definition:** The Las Vegas method is similar to the monte carlo method as it uses random sampling, but it always gives the correct answer whereas the monte carlo method does not guarantee a correct answer.
+
+Despite always giving the correct answer, Las Vegas method algorithms have variadic runtimes. An example of such an algorithm is [quickselect](Quickselect.md).
diff --git a/docs/OCaml.md b/docs/OCaml.md
@@ -0,0 +1,7 @@
+# OCaml
+
+OCaml is a multi-paradigm programming language that extends Caml, a dialect of ML with object-oriented features.
+
+## Notable Projects
+
+- [Unison](https://github.com/bcpierce00/unison)
diff --git a/docs/Quickselect.md b/docs/Quickselect.md
@@ -0,0 +1,22 @@
+# Quickselect
+
+**Source:** Competitive Programmer's Handbook Ch 24.5
+
+**Definition:** Quickselect is a Las Vegas method stochastic algorithm with O($n^2$) worst case asymptotic time complexity and O($n$) average case asymptotic time complexity used for the selection of the $k$th smallest element in an unordered collection, also referred to as the $k$th order statistic.
+
+## Procedure
+
+1. Select a random pivot
+2. Swap pivot with the righmost elment
+3. Partition the subarray
+4. Move the pivot into its final sorted position
+5. Compare the pivot index with the target index
+ - if pivot index == index, return the pivot
+ - if index < pivot index, recurse left subarray
+ - if index > pivot index, recurse right subarray
+
+## Complexity
+
+When we select an arbitrary element of the array as the pivot we expect to perform ~n operations because we check if each element is > or < the current element. On the next iteration, we expect to perform $\frac{n}{2}$ operations. This continues on, and we note we expect this sum to be <2n. This gives us our O(n) average case time complexity.
+
+For the worst case asymptotic time complexity, notice we may select the highest element of the array every time, requiring n, n-1, n-2, ... operations at each step. This gives us a worst case asymptotic time complexity of O($n^2$).
diff --git a/docs/Software.md b/docs/Software.md
@@ -34,6 +34,7 @@ Software and software related concepts. Focused on free software and primitives.
- [rsync](rsync.md)
- [Git](Git.md)
+- [Darcs](Darcs.md)
- [systemd](Systemd.md)
- cpio
