commit 32ca61a1b52ebb4d80dcda4a9f8df71aa02c3633
parent c5894452dceb794bf3161e3738e43995bd5b7f2f
Author: Andrew <andrewlaack1@gmail.com>
Date: Mon, 19 Aug 2024 13:16:24 -0500
Took notes on discrete and dsa
Diffstat:
14 files changed, 148 insertions(+), 4 deletions(-)
diff --git a/Algorithms.md b/Algorithms.md
@@ -8,3 +8,20 @@ This is an index for links to notes taken about algorithms. These are CS related
[[MonteCarloMethod.md]]
[[LasVegasMethod.md]]
[[PerlinNoise.md]]
+
+#### Intro To Algorithms (MIT)
+
+L1:
+ - [[AsymptoticNotation.md]]
+ - [[FundamentalOperations.md]]
+
+L2:
+ - [[LinkedLists.md]]
+ - [[DataStructureAugmentation.md]]
+ - [[Amortization.md]] - TODO
+
+
+#### Intro To Algorithms Textboo (CLRS)
+
+ - [[AsymptoticNotation.md]]
+ - [[FundamentalOperations.md]]
diff --git a/AsymptoticNotation.md b/AsymptoticNotation.md
@@ -0,0 +1,36 @@
+:cs: :algorithms:
+# Asymptotic Notation
+
+L1 MIT
+
+## Notes
+
+**Definition:** Asymptotic notation describes the running time of an algorithm.
+
+There are three different notations for this big O, beg Theta, and big Omega.
+
+1. Big Theta
+ - Big Theta notation encloses the lower and upper bounds of the algorithm. This can be used to then find the mean complexity.
+
+2. Big Omega
+ - Big Omega notation is used to describe the lower bound (best case) complexity.
+
+3. Big O
+ - Big O notation is used to describe the upper bound (worst case) complexity.
+
+
+#### Common complexities
+
+O(1) - Constant
+
+O(logn) - Logarithmic
+
+O(n) - Linear
+
+O(nlogn) - Log Linear
+
+O(n^2) - Quadratic time
+
+O(n^c) - Polymnomial time (arbitrary constant c)
+
+2^O(n) - Exponential Time
diff --git a/DataStructureAugmentation.md b/DataStructureAugmentation.md
@@ -0,0 +1,10 @@
+:algorithms: :data-structures:
+# Data Structure Augmentation
+
+L2
+
+## Notes
+
+**Definition:** Data structure augmentation is adding something to a data structure to improve it in some way.
+
+An example of this is to improve a singly linked list with a tail pointer so polling the tail can be done in O(1) instead of O(n) time. By doing this we could also have constant time additions onto the end of the list (ensure pointer is updated).
diff --git a/DiscreteMath.md b/DiscreteMath.md
@@ -33,5 +33,11 @@ Unit 1.3:
Unit 1.4:
- [[Predicate.md]]
+ - [[PropositionalFunction.md]]
- [[Quantifiers.md]]
- [[Universe.md]]
+ - [[Preconditions.md]]
+ - [[Postcondition.md]]
+
+Unit 1.5:
+ - [[NestedQuantifier.md]]
diff --git a/FundamentalOperations.md b/FundamentalOperations.md
@@ -0,0 +1,14 @@
+:cs: :algorithms:
+# Fundamental Operations
+
+L1
+
+## Notes
+
+**Definition:** Fundamental operations are operations that take constant time.
+
+#### List of fundamental operations
+
+Word-RAM - Accessing arbitrary memory address (smallest access size is a word, 64-bit)
+
+Memory Allocation/Deallocation - Allocate one word (linear time to make array of n length)
diff --git a/LinkedLists.md b/LinkedLists.md
@@ -1,4 +1,4 @@
-:c++: :cs202: :data-structures:
+:c++: :cs202: :data-structures: :algorithms:
# Linked Lists
This is from CS 221 W11 Lecture 13.
diff --git a/NestedQuantifier.md b/NestedQuantifier.md
@@ -0,0 +1,12 @@
+:discrete: :math: :logic:
+# Nested Quantifiers
+
+U 1.5.1
+
+## Notes
+
+**Definition:** Nested quantifiers are when there are multiple quantifiers in the same scope.
+
+Example:
+
+$\forall x \exists y (x+y=0)$
diff --git a/Postcondition.md b/Postcondition.md
@@ -0,0 +1,8 @@
+:math: :logic: :discrete: :cs:
+# Postcondition
+
+U 1.4.1
+
+## Notes
+
+**Definition:** Postconditions are the expected outputs of a function or program which are predicated upon the specified [[Preconditions.md]].
diff --git a/Preconditions.md b/Preconditions.md
@@ -0,0 +1,8 @@
+:math: :logic: :discrete: :cs:
+# Preconditions
+
+U 1.4.1
+
+## Notes
+
+**Definition:** Preconditions are necessarily specified inputs (or variables) to a function (or program) that are required prior to execution/evaluation.
diff --git a/Predicate.md b/Predicate.md
@@ -5,7 +5,7 @@ U 1.4.1
## Notes
-**Definition:** The predicate in a mathematical context is the part of a statement that gives us a truth value.
+**Definition:** The predicate in a mathematical context is the part of a statement that gives us a truth value when variables are at play.
In the case of 'x < 2' the predicate is 'less than 2'. This can be stated as a propositional function P(x). The following are valid inputs and outputs of said function:
diff --git a/PropositionalFunction.md b/PropositionalFunction.md
@@ -0,0 +1,24 @@
+:logic: :discrete: :math:
+# Propositional Function
+
+U 1.4.1
+
+## Notes
+
+**Definition:** A propositional function is a function that takes an arbitrary number of inputs and outputs a truth value.
+
+An example of a propositional function is the function P(x) defined as 'x > 2'. This function could then be evaluated as follows:
+
+1. P(1) | False
+2. P(2) | False
+3. P(3) | True
+
+Once a propositional function is evaluated with some object(s) and no longer contains any variables, it is then said to be a proposition.
+
+Given this, we know that the propositional function P(x,y) is still a propositional function when we specify P(1,y) because there is still a variable namely y.
+
+An interesting thing about propositional functions with the universal quantifier is that if the universe (U) is empty, the proposition is true as there are no counterexamples.
+
+## Bound and Free
+
+When we assign a variable of a propositional function it is said to be bound. Conversely, when a variable is not bound it is then free.
diff --git a/Quantifiers.md b/Quantifiers.md
@@ -12,7 +12,7 @@ The two common quantifiers are:
1. $\exists$ - There exists (existential quantifier)
2. $\forall$ - For all (universal quantifier)
-Another derived one is $\exists !$ which means there exists only one.
+Another derived one is $\exists !$ which means there exists only one. Another way to state this is $\exists_1$. By using this notation we can then specify there are only an arbitrary number of elements of the set that have some property.
### Propositional Functions
@@ -28,10 +28,14 @@ $P(1)$ - This is a proposition
When negating a for each we negate the propositional function (not P(x)) and flip the for each to be there exists.
-The oppossite is also true for negating a there exists.
+The opposite is also true for negating a there exists.
Examples:
For all - $\neg \forall x P(x) = \exists x \neg P(x)$
There exists - $\neg \exists P(x) = \forall x \neg P(x)$
+
+### Scope
+
+The scope of a quantifier is limited to what is contained in the parenthesis or preceeding propositional function when of the form $\forall x P(x)$. As such, $\forall x P(x) \to C(x)$ is not defined as we would need to specify $\forall x (P(x) \to C(x))$. This avoids an ambiguity in our statements.
diff --git a/Universe.md b/Universe.md
@@ -9,4 +9,6 @@ U 1.4.1
Often we state the universe as the variable U.
+This is also sometimes called the domain, universe of discourse, or the domain of discourse.
+
See also [[UniversalSet.md]] for the same concept. I created this note because the term bears remembering and I forgot what I called the universal set in the domain of stats and probability.
diff --git a/index.md b/index.md
@@ -49,3 +49,6 @@ ML
- [ ] Mamba
- [ ] Transformer
- [ ] KAN
+
+Algorithms
+ - [ ]
