commit eab637885542a90674a1c3069824bc69ff129c25
parent 10c26a58c929d70b033c4404732181407ae48f6b
Author: Andrew <andrewlaack1@gmail.com>
Date: Thu, 17 Oct 2024 06:15:32 -0500
Took some notes
Diffstat:
8 files changed, 119 insertions(+), 5 deletions(-)
diff --git a/Algorithms.md b/Algorithms.md
@@ -55,6 +55,34 @@ Ch 4 (graphs):
- [WeightedGraph](WeightedGraph.md)
- [EmptyGraph](EmptyGraph.md)
- Isomorphism (relabel verticies still same graph)
+ - Bipartite
+
+Ch 5 (Hashing)
+ - [Hashing](Hashing.md)
+ - [Homogeneous](Homogeneous.md)
+ - HashTable
+ - Key (defn. if a key x.r = y.r then x=y - note this is a list of elements)
+ - HashValues (also hash code)
+ - [HashFunction](HashFunction.md)
+ - Folding (hashing techinque, partition the key into chunks then operate on chunks)
+ - ArithmeticComputations (think about making a polynomial and such)
+ - FiniteField (abstract algebra)
+ - Collision
+ - LinearProbing (home position, wrap-around (circular linked list), clustering)
+ - ProbingFunction
+ - QuadraticProbing
+ - LoadFactor
+ -
+
+#### Other Stuff To Look At
+
+Operation types (operations done with n inputs)
+ - Unary Operations (unary ops)
+ - Binary Operations (binary ops)
+ - Ternary Operations
+ - N-ary Operations (> 3 ops)
+ - Quaternary Operations (4 inputs)
+ - Variadic Operations (varying inputs)
#### Intro To Algorithms (MIT)
diff --git a/Assembly.md b/Assembly.md
@@ -85,6 +85,42 @@ addgt
bx
-cbz
+cbz - Compare and branch on zero
+cbz R2, fa2 - This will compare R2 with 0 and then if they are the same branch to fa2
+arrb
+
+LR - Link register
+SP - stack frame
+
+LSL
+
+When you have a function that updates registers make sure to save to the stack the original values in those registers then load them at the end of the function. Doing this ensures the method does not mess with the caller.
+
+EX (start):
+
+push {R1} ; preserve R1
+
+; end
+
+pop {R1} ; restore register
+
+mov PC,LR ; return to sender - program counter, link register
+
+
+USE BL to branch with link back
+
+ENDP
+
+To preserve multiple things you can do:
+
+push {R1, R2}
+
+Corresponding pop:
+
+pop {R1, R2}
+
+
+
+consider incrementing count in insert
diff --git a/DiscreteMath.md b/DiscreteMath.md
@@ -148,3 +148,6 @@ Unit 8.2 (Solving Linear Recurrence Relations)
- [LinearHomogeneousRecurrenceRelation](LinearHomogeneousRecurrenceRelation.md)
- [CharacteristicEquation](CharacteristicEquation.md)
- [CharacteristicRoots](CharacteristicRoots.md)
+
+Unit 8.3 (Divide and Conquer)
+ - [DivideAndConquer](DivideAndConquer.md)
diff --git a/DivideAndConquer.md b/DivideAndConquer.md
@@ -1,4 +1,4 @@
-:algorithms:
+:algorithms: :discrete:
# Divide And Conquer
CLRS 2.3.1
diff --git a/HashFunction.md b/HashFunction.md
@@ -0,0 +1,41 @@
+:cs: :algorithms: :data-structures:
+# Hash Function
+
+Ch. 5
+
+## Notes
+
+**Definition:** A hash function is a function f(k) that takes a key value k (x.r = k where x is an object) and outputs a natural number.
+
+f : K -> N where K is the set of all possible keys and N is the natural numbers.
+
+Oftentimes we also want to state that the set of valid outputs (image of f) is from 0 to m-1 where m is the length of the array we are using to store the objects of the given hash value.
+
+### n-bit hash functions
+
+**Definition:** n-bit hash functions are hash functions such that their image is the natural numbers from 0 to 2^n-1.
+
+These hash function can then map to all permuations of bits with a length of n.
+
+### Important aspects of the hashing function
+
+1. Speed
+2. One-way
+3. Deterministic
+4. Uniform
+
+Speed - this means the time to compute the hash for the inputs is generally fast
+
+One-way - this means it is hard to go the opposite direction namely from N -> K
+
+Deterministic - this means for the same input the output should always be the same
+
+Uniform - the distribution, with respect to K, should be roughly uniform across the image of the function - [0, m-1]
+
+### Perfect
+
+A hash function is perfect if for all valid inputs, there are no collisions (one-to-one).
+
+$f:K \to N$ is a perfect hash function if
+$\forall x,y\in K, f(x) \neq f(y) \text{ where } y \neq x$
+
diff --git a/Hashing.md b/Hashing.md
@@ -1,7 +1,7 @@
:cs: :algorithms: :data-structures:
# Hashing
-L4
+L4 - Ch5 (Rosen)
## Notes
diff --git a/Homogeneous.md b/Homogeneous.md
@@ -1,4 +1,4 @@
-:lin-alg:
+:lin-alg: :cs: :algorithms: :data-structures:
# Homogeneous
Khan U2
@@ -8,3 +8,9 @@ Khan U2
**Definition:** In linear algebra a homogeneous solution is one where the right side of the system is the zero vector.
See also [[Inhomogeneous.md]]
+
+## CS
+
+Ch. 5 (Rosen)
+
+**Defintiion:** In computer science homogeneous means that all items in some collection are of the same datatype.
diff --git a/LinearHomogeneousRecurrenceRelation.md b/LinearHomogeneousRecurrenceRelation.md
@@ -11,4 +11,4 @@ Example of k degree LHRR:
$a_n = c_1a_{n-1} + c_2a_{n-2} + ... + c_ka_{n-k}$
-Assume all c terms are coefficients and c_k is non-zero.
+Assume all c terms are coefficients and all c_i are non-zero.
