commit 30b8ee6f676ed1b3657abd1c48114886fcf0d9d9
parent 813d6e0f685aa88779e78281e0d16bec6158f091
Author: Andrew <andrewlaack1@gmail.com>
Date: Wed, 21 Aug 2024 04:17:34 -0500
1 hour of dsa
Diffstat:
13 files changed, 172 insertions(+), 12 deletions(-)
diff --git a/Algorithms.md b/Algorithms.md
@@ -21,7 +21,13 @@ L2:
- [[Amortization.md]]
-#### Intro To Algorithms Textboo (CLRS)
+#### Intro To Algorithms Textbook (CLRS)
- - [[AsymptoticNotation.md]]
- - [[FundamentalOperations.md]]
+2.1
+ - [[InsertionSort.md]]
+ - [[LoopInvariant.md]]
+
+2.3
+ - [[Incremental.md]]
+ - [[DivideAndConquer.md]]
+ - [[MergeSort.md]]
diff --git a/AsymptoticNotation.md b/AsymptoticNotation.md
@@ -12,13 +12,13 @@ L1 MIT
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.
+ - Big Theta notation creates a tight bound about asymptotic behavior. This is a precise growth rate bound between O(f(n)) and Omega(f(n)).
2. Big Omega
- - Big Omega notation is used to describe the lower bound (best case) complexity.
+ - Big Omega notation is used to describe the lower bound (best case) complexity. This value describes a functions complexity as at least whatever is specified. As such a function with n^3 growth can be stated as Omega(n^c) where n <= 3. Subsequently, it is also true that Omega(n^1) can describe this function.
3. Big O
- - Big O notation is used to describe the upper bound (worst case) complexity.
+ - 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.
#### Common complexities
diff --git a/Contrapositive.md b/Contrapositive.md
@@ -1,12 +1,12 @@
-:math310: :proofs:
+:math310: :proofs: :discrete: :logic:
# Contrapositive
-Throughout TB
+Throughout TB - U1.7.2 Discrete TB
## Notes
-**Definition:** To prove and if then statement with contrapositive we assume the then statement is false. Following from here we then prove the if part must also be true for the then to be false. So it follows that if the first is true then the second is also true because the second is never true when the first is false.
+**Definition:** To prove an if then statement with contrapositive we assume the then statement is false. Following from here we then prove the if part must also be true for the then to be false. So it follows that if the first is true then the second is also true because the second is never true when the first is false.
-This is of the form $\neg q \to \neq p$ where we switch the statements and negate both. To just negate both we [[Inverse.md]] it.
+This is of the form $\neg q \to \neg p$ where we switch the statements and negate both. To just negate both we [[Inverse.md]] it.
This always has the same truth value as the original.
diff --git a/DirectProof.md b/DirectProof.md
@@ -1,7 +1,7 @@
-:proof: :math310:
+:proof: :math310: :logic: :discrete:
# Direct Proof
-Abstract Math Proof Technique
+Abstract Math + Discrete Math U1.7.1
## Notes
diff --git a/DiscreteMath.md b/DiscreteMath.md
@@ -41,3 +41,11 @@ Unit 1.4:
Unit 1.5:
- [[NestedQuantifier.md]]
+
+Unit 1.6:
+ - [[LawOfDetachment.md]]
+
+Unit 1.7:
+ - [[DirectProof.md]]
+ - [[Contrapositive.md]] - Also known as contraposition
+ - [[Contradiction.md]]
diff --git a/DivideAndConquer.md b/DivideAndConquer.md
@@ -0,0 +1,16 @@
+:algorithms:
+# Divide And Conquer
+
+CLRS 2.3.1
+
+## Notes
+
+**Definition:** Divide and conquer algorithms are algorithms that break a problem down into smaller sub-problems and then solve each subproblem.
+
+This algorithms are often, but not always, recursive.
+
+Steps:
+
+1. (Divide) Divide problem into subproblems
+2. (Conquer) Solve subproblems
+3. (Combine) Aggregate final result
diff --git a/FundamentalOperations.md b/FundamentalOperations.md
@@ -12,3 +12,5 @@ L1
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)
+
+Simple Arithemitic - Add, subtract, multiply, divide, remainder, floor, ceiling)
diff --git a/Incremental.md b/Incremental.md
@@ -0,0 +1,10 @@
+:algorithms:
+# Incremental
+
+CLRS 2.3
+
+## Notes
+
+**Definition:** Incremental algorithms are algorithms that solve the task in order (iteratively).
+
+An example of this is [[InsertionSort.md]].
diff --git a/InsertionSort.md b/InsertionSort.md
@@ -0,0 +1,42 @@
+:algorithms:
+# Insertion Sort
+
+CRLS 2.1
+
+## Notes
+
+**Definition:** Insertion sort is a sorting algorithm with a worst case complexity of n^2 that selects the next element in the array, moves it to the left side in the correctly sorted position, and then iterates through the list for all items.
+
+
+This can be thought of as sorting cards by hand. You start with all cards in the right hand. You then remove the first card and place it in the left hand. You then do the same thing for the next card in the right hand placing it in the sorted location. You continue this until are cards are in the left hand.
+
+The only issue with this analogy is that insertion sort uses only one array instead of two where you track the sorted part of the array and as elements are added all elements to the right are pushed over until reaching the spot where it was formerly.
+
+Implementation in python:
+
+```python3
+def insertion_sort(ls):
+ sortedLen = 0
+ for i in range(0, len(ls)):
+ x = sortedLen
+ added = False
+ while x >= 0:
+ if ls[x] < ls[i]:
+ move_and_offset(i, x + 1, ls)
+ added = True
+ break
+ x -= 1
+ if added == False:
+ move_and_offset(i, 0, ls)
+ sortedLen += 1
+ return ls
+
+def move_and_offset(posFrom, posTo, ls):
+ last = ls[posFrom]
+ i = posTo
+ while i < posFrom + 1:
+ temp = ls[i]
+ ls[i] = last
+ last = temp
+ i+=1
+```
diff --git a/LawOfDetachment.md b/LawOfDetachment.md
@@ -0,0 +1,12 @@
+:discrete: :logic:
+# Law of Detatchment
+
+U 1.6.1
+
+## Notes
+
+**Definition:** The law of detachment is a law that specifies a form that valid arguments can take.
+
+This form is $(p \wedge (p\to q) \to q$.
+
+Simply, this can be thought of as stating if you have a premise that implies something then that implied statement can be assumed true given that all premises are also true.
diff --git a/LinearAlgebra.md b/LinearAlgebra.md
@@ -75,3 +75,4 @@ Khan Unit 2:
Khan Unit 3:
- [[OrthogonalComplement.md]]
+ - [[Projection.md]]
diff --git a/LoopInvariant.md b/LoopInvariant.md
@@ -0,0 +1,16 @@
+:algorithms: :cs:
+# Loop Invariant
+
+CLRS 2.1
+
+## Notes
+
+**Definition:** A loop invariant is a condition that is true before and after a loop is ran.
+
+In the case of insertion sort the loop invariant is that [0 : p] is sorted where p is the number of prior iterations (prior elements sorted). See [[InsertionSort.md]] to understand this better.
+
+Given that this must be true before and after running, we know it must be initialized as true which can sometimes mean manual running to get it started outside the loop itself to ensure proper iteration.
+
+We call it maintenance when we are looping and making changes to ensure the invariance remains true.
+
+Termaination is then the end of the loop whereby some condition has been met.
diff --git a/MergeSort.md b/MergeSort.md
@@ -0,0 +1,47 @@
+:algorithms:
+# Merge Sort
+
+CLRS 2.3
+
+## Notes
+
+**Definition:** Merge sort is an algoritmh that uses [[DivideAndConquer.md]] to sort a list in log linear (n log(n)) time.
+
+Sample Implementation:
+
+```python3
+
+def merge(ls):
+
+ # Base case length of 1
+ if len(ls) == 1:
+ return ls
+
+ # Split list in half
+ pivot = int(len(ls) / 2)
+ left = ls[0 : pivot]
+ right = ls[pivot :]
+
+ # Recurse
+ left = merge(left)
+ right = merge(right)
+
+ leftPos = 0
+ rightPos = 0
+ sorted = []
+
+ # Merge lists (O(n))
+ while leftPos < len(left) and rightPos < len(right):
+ if left[leftPos] < right[rightPos]:
+ sorted.append(left[leftPos])
+ leftPos += 1
+ else:
+ sorted.append(right[rightPos])
+ rightPos += 1
+
+ sorted.extend(left[leftPos:])
+ sorted.extend(right[rightPos:])
+
+ return sorted
+
+```
