commit 2eded775c0c5eaa2c54555aa8c58e0d7209b430e
parent e570d7d69e66895c804db5aeee31208636c3031a
Author: Andrew <andrewlaack1@gmail.com>
Date: Thu, 22 Aug 2024 12:26:55 -0500
Took notes on discrete, dsa, calc, and discrete
Diffstat:
11 files changed, 97 insertions(+), 0 deletions(-)
diff --git a/Algorithms.md b/Algorithms.md
@@ -20,6 +20,12 @@ L2:
- [[DataStructureAugmentation.md]]
- [[Amortization.md]]
+L4:
+ - [[Hashing.md]]
+ - [[OpenAddressing.md]]
+
+L5 (non-comparative sorting):
+ - [[CountSort.md]]
#### Intro To Algorithms Textbook (CLRS)
@@ -31,3 +37,8 @@ L2:
- [[Incremental.md]]
- [[DivideAndConquer.md]]
- [[MergeSort.md]]
+
+3.2
+ - [[AsymptoticNotation.md]]
+ - [[Trichotomy.md]]
+ - [[MonotonicFunction.md]]
diff --git a/AsymptoticNotation.md b/AsymptoticNotation.md
@@ -20,6 +20,8 @@ There are three different notations for this big O, beg Theta, and big Omega.
3. Big O
- Big O notation is used to describe the upper bound (worst case) complexity. An interesting note is that the function with growth 7n^3 + 2n^2 can have O(n^3) time complexity, but more accurately we could say O(n^c) where c >= 3. This is because we are stating it does not grow faster than n^c. Such is the case then that O(n^10) is also true as the complexity does not grow faster than that.
+Note: When describing loose bounds (2n = o(n^2)) we use lowercase letters such as little o. This implies that we are describing an upper bound that is guaranteed to be larger than the growth rate that is not tight to the upper bound of the algorithm like how big O would be.
+
#### Common complexities
diff --git a/Calculus.md b/Calculus.md
@@ -18,6 +18,11 @@ L2:
- [[Surjective.md]]
- [[Bijective.md]]
+Khan Calc 2:
+
+Unit 1:
+ - [[FundamentalTheroemofCalculus.md]]
+
Calculus Early Transcendentals JS:
Section 2.8:
diff --git a/CountSort.md b/CountSort.md
@@ -0,0 +1,8 @@
+:algorithms:
+# Count Sort
+
+L5
+
+## Notes
+
+**Definition:** Count sort is a non-comparative sorting algorithm where we count the total number of instances of a given value and then reassemble a sorted output by creating a datastructure that contains the number of each value specified by the count.
diff --git a/DiscreteMath.md b/DiscreteMath.md
@@ -60,6 +60,7 @@ Unit 2.1 (sets):
- [[CartesianProduct.md]]
- [[TruthSet.md]]
- [[Complement.md]]
+ - [[Multiset.md]]
Unit 2.3 (functions):
- [[Range.md]]
diff --git a/FundamentalTheroemofCalculus.md b/FundamentalTheroemofCalculus.md
@@ -0,0 +1,10 @@
+:calc:
+# (Second) Fundamental Theroem of Calculus
+
+Khan U1
+
+## Notes
+
+**Definition:** The (second) fundamental theroem of calculus states that the derivative of the integral of a function from a (constant) to x that is continuous is equivalent to the contained function with respect to x.
+
+This implies that all functions that are continuous on a domain have an antiderivative.
diff --git a/Hashing.md b/Hashing.md
@@ -0,0 +1,8 @@
+:cs: :algorithms: :data-structures:
+# Hashing
+
+L4
+
+## Notes
+
+**Definition:** Hashing is a process done whereby we use some function f(x) to map one value to another where the output value is generally an index or otherwise adressable place.
diff --git a/MonotonicFunction.md b/MonotonicFunction.md
@@ -6,3 +6,5 @@ Stats
## Notes
**Definition:** A monotonically increasing function is one where as the input increases the output either stays the same or increases. The inverse is also true with a monotonically decreasing function. The statement of monotonicity simply means always increasing or decreasing.
+
+Another variant upon monotonic functions is the strictly function which is always moving in some direction and never stagnates. An example is f(x) = x where the function is strictly increasing for all reals.
diff --git a/Multiset.md b/Multiset.md
@@ -0,0 +1,24 @@
+:discrete: :logic:
+# Multiset
+
+U2.2.5
+
+## Notes
+
+**Definition:** A multiset is an unordered collection that can contain multiple instances of the same object.
+
+Multiset is short for multiple-membership set.
+
+Example:
+
+Multiset:
+
+{a,a,a,b,b}
+
+Preferred notation:
+
+{3 x a , 2 x b}
+
+The number out front that denotes the number of instances is called the multiplicity of the element. As such, a multiplicity of 0 means the element is not contained in the set.
+
+When unioning two multisets we take the larger of the multiplicities for shared elements. Conversely, the intersection between two multisets is the minimal multiplicity value.
diff --git a/OpenAddressing.md b/OpenAddressing.md
@@ -0,0 +1,8 @@
+:algorithms: :data-structures:
+# Open Addressing (hashing)
+
+L4
+
+## Notes
+
+**Definition:** Open addressing is the process of resolving collisions by probing for the next available location in a predefined manor to remove the need to resolve collisions with another data structure.
diff --git a/Trichotomy.md b/Trichotomy.md
@@ -0,0 +1,18 @@
+:discrete: :algorithms: :cs:
+# Trichotomy
+
+CLRS 3.2
+
+## Notes
+
+**Definition:** Trichotomy is a property of real numbers such that for any two real numbers one of the following must be true:
+
+1. a < b
+2. b < a
+3. a = b
+
+More generally trichotomy is a term to express three way classification.
+
+#### Asympotic Notation
+
+The reason I created this note is because asymptotic notations can be compared namely with O(n) < O(n^2) and such, but they are not tricotometric (word?) as it is possible a functions runtime may oscilate thus not allowing for a proper comparision.
