commit 0ea5f66235997519a3953b018c6c0ca81e51bcec
parent eab637885542a90674a1c3069824bc69ff129c25
Author: Andrew <andrewlaack1@gmail.com>
Date: Thu, 17 Oct 2024 11:55:26 -0500
Took some notes
Diffstat:
19 files changed, 197 insertions(+), 20 deletions(-)
diff --git a/Algorithms.md b/Algorithms.md
@@ -54,35 +54,31 @@ Ch 4 (graphs):
- [ConnectedComponent](ConnectedComponent.md)
- [WeightedGraph](WeightedGraph.md)
- [EmptyGraph](EmptyGraph.md)
- - Isomorphism (relabel verticies still same graph)
- - Bipartite
+ - [Bipartite](Bipartite.md)
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)
+ - [HashTable](HashTable.md)
+ - [Key](Key.md)
+ - [HashValues](HashValues.md)
- [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
- -
+ - [Folding](Folding.md)
+ - [ArithmeticComputations](ArithmeticComputations.md)
+ - [FiniteField](FiniteField.md)
+ - [Collision](Collision.md)
+ - [LinearProbing](LinearProbing.md)
+ - [ProbingFunction](ProbingFunction.md)
+ - [QuadraticProbing](QuadraticProbing.md)
+ - [LoadFactor](LoadFactor.md)
#### 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)
+ - [UnaryOperations](UnaryOperations.md)
+ - [BinaryOperations](BinaryOperations.md)
+ - [NaryOperations](NaryOperations.md)
+ - [VariadicOperations](VariadicOperations.md)
#### Intro To Algorithms (MIT)
diff --git a/ArithmeticComputations.md b/ArithmeticComputations.md
@@ -0,0 +1,8 @@
+:data-structures: :cs:
+# Arithmetic Computations
+
+Ch 5
+
+## Notes
+
+**Definition:** Arithmetic computations, with respect to hashing, are computations that use arithmetic operators to go from some key (or portion of a key) to a hash value (or portion).
diff --git a/BinaryOperations.md b/BinaryOperations.md
@@ -0,0 +1,10 @@
+:computer-science:
+# Binary Operations
+
+SS
+
+## Notes
+
+**Definition:** Binary operations are operations that take two inputs.
+
+Some examples include assignment (left,right side), addition, subtraction
diff --git a/Bipartite.md b/Bipartite.md
@@ -0,0 +1,12 @@
+:cs: :graphs:
+# Bipartite
+
+Ch 4
+
+## Notes
+
+**Definition:** A bipartite graph is a graph that can be divided into two sets where every edge connects a vertex in one set to the other set, but never the same set.
+
+Think about a graph with red and blue where blue can only connect to red and vice versa.
+
+The generalization of this are multipartite graphs where we have integer k that defines the number of sets instead of simply 2.
diff --git a/Collision.md b/Collision.md
@@ -0,0 +1,8 @@
+:data-structures: :cs:
+# Collision
+
+Ch 5
+
+## Notes
+
+**Definition:** A collision, with respect to hash tables, is when we try to place an element into a position in the array that is already taken.
diff --git a/DiscreteMath.md b/DiscreteMath.md
@@ -151,3 +151,6 @@ Unit 8.2 (Solving Linear Recurrence Relations)
Unit 8.3 (Divide and Conquer)
- [DivideAndConquer](DivideAndConquer.md)
+
+Unit 8.5 (Inclusion Exclusion)
+ - [PrincipleOfInclusionExclusion](PrincipleOfInclusionExclusion.md)
diff --git a/FiniteField.md b/FiniteField.md
@@ -0,0 +1,8 @@
+:abstract-algebra:
+# Finite Field
+
+Ch 5
+
+## Notes
+
+**Definition:** A finite field in abstract algebra is a set where addition, subtraction, multiplication, and division are defined and behave in a way similar to real numbers (field) that also contains a finite number of elements.
diff --git a/Folding.md b/Folding.md
@@ -0,0 +1,8 @@
+:data-structures: :cs:
+# Folding
+
+Ch 5
+
+## Notes
+
+**Definition:** Folding is a process used in a hashing function where we split the key into discrete parts and then operate upon each of them seperately.
diff --git a/HashTable.md b/HashTable.md
@@ -0,0 +1,10 @@
+:data-structures: :cs:
+# Hash Table
+
+Ch 5
+
+## Notes
+
+**Definition:** A hash table is a collection data structure that allows insertions of elements and checking for elements that uses a hashing function to place objects into an array for 'constant' time access.
+
+Note that generally we use openaddressing (linear/quadratic probing), to ensure collisions are handled correctly. There is also the case where you might use a linked list, but in cs 303 we are not doing that, and python does not do that either.
diff --git a/HashValues.md b/HashValues.md
@@ -0,0 +1,10 @@
+:data-structures: :cs:
+# Hash Values (hash code)
+
+Ch 5
+
+## Notes
+
+**Definition:** A hash value is the output of the hash function that describes which index we should try to place an element in.
+
+Hash values can range from 0 - m-1 where m is the length of the array to store the element in.
diff --git a/Key.md b/Key.md
@@ -0,0 +1,10 @@
+:data-structures: :cs:
+# Key
+
+Ch 5
+
+## Notes
+
+**Definition:** A key is list of attribute of an object x that uniquely identifies it from all other elements of our universe.
+
+In hashtables we hash the keys and then store the items. When openaddressing, if the queried for object is not the one at the address, we continue on with our probing algorithm until we find the item or find an empty spot (this assumes we don't remove items from our table).
diff --git a/LinearProbing.md b/LinearProbing.md
@@ -0,0 +1,10 @@
+:data-structures: :cs:
+# Linear Probing
+
+Ch 5
+
+## Notes
+
+**Definition:** Linear probing is a probing (open addressing) strategy that selects the next open index to place any objects that experienced a collission.
+
+The problem with linear probing is clustering. This is the process whereby elements that have collided grow into larger groupings such that the probability of the element after the cluster being selected is far higher than other elements in the array. This is problematic because we want our hashtable to be uniformly distributed. This is a problem that can often be solved by using quadratic probing.
diff --git a/LoadFactor.md b/LoadFactor.md
@@ -0,0 +1,8 @@
+:data-structures: :cs:
+# Load Factor
+
+Ch 5
+
+## Notes
+
+**Definition:** The load factor of a hashtable is the percentage of the underlying array that is full.
diff --git a/NaryOperations.md b/NaryOperations.md
@@ -0,0 +1,8 @@
+:computer-science:
+# N-ary Operations
+
+SS
+
+## Notes
+
+**Definition:** N-ary operations is a general term for operations that take a finite and specific number of inputs, but don't fall into the category of unary, binary, ternary, or in some cases quaternary.
diff --git a/PrincipleOfInclusionExclusion.md b/PrincipleOfInclusionExclusion.md
@@ -0,0 +1,20 @@
+:discrete: :prob: :counting:
+# Principle of Inclusion-Exclusion
+
+Ch 8.3 Rosen
+
+## Notes
+
+**Definition:** The principle of inclusion-exclusion is a principle used to count the number of elements in the union of a finite number of sets.
+
+Consider:
+
+$|A \cup B| = \text{ } ?$
+
+We know that all elements of A and all elements of B will be in the union, but there are some elements that may be in both. These are simply elements of $A \cap B$. As such we see:
+
+$|A \cup B| = |A| + |B| - |A \cap B|$.
+
+#### Theroem
+
+I will not write this out, but it should be understood that this can be stated simply as only counting the intersection of sets one time overall.
diff --git a/ProbingFunction.md b/ProbingFunction.md
@@ -0,0 +1,10 @@
+:data-structures: :cs:
+# Probing Function
+
+Ch 5
+
+## Notes
+
+**Definition:** A probing function is a function that takes in an ordered pair of inputs, the first which is a hashcode and the second which is the iteration and outputs a position between 0 and m-1.
+
+In the case of linear probing, the function takes in an input of the hashcode (address) and the iteration. It then returns the hashcode + iteration mod m-1, this ensures the next address is checked if the previous was occupied.
diff --git a/QuadraticProbing.md b/QuadraticProbing.md
@@ -0,0 +1,18 @@
+:cs: :data-structures:
+# Quadratic Probing
+
+Ch 5
+
+## Notes
+
+**Definition:** Quadratic probing is a probing strategy defined as follows:
+
+When i is odd: $f(e,i) = e + (ceil(i/2))^2$
+
+When i is even: $f(e,i) = e - (ceil(i/2)^2$
+
+Basically, we check first e then e + 1 then then e - 1 then e + 4 then e - 4 and so on.
+
+Note:
+
+This only works with specific array sizes because some sizes don't get entirely mapped to by the probing function for all valid values of e.
diff --git a/UnaryOperations.md b/UnaryOperations.md
@@ -0,0 +1,10 @@
+:computer-science:
+# Unary Operations
+
+SS
+
+## Notes
+
+**Definition:** Unary operations are operations that only take one input.
+
+These operations include increment, decrement, square root, etc.
diff --git a/VariadicOperations.md b/VariadicOperations.md
@@ -0,0 +1,10 @@
+:computer-science:
+# Variadic Operations
+
+SS
+
+## Notes
+
+**Definition:** Variadic operations are operations that can take a varying number of inputs.
+
+Some examples of these include sum, min, and max which would type in arbitrary lenght arrays in certain languages.
