commit ff57f1026407568cacbe09a61466a478b5a32c03
parent d1ebfeabfc4ced0f317250c5874540688e1e3b82
Author: Andrew <andrewlaack1@gmail.com>
Date: Tue, 3 Sep 2024 06:27:41 -0500
Took notes from yesterday for cs 303
Diffstat:
16 files changed, 121 insertions(+), 10 deletions(-)
diff --git a/AbstractDataType.md b/AbstractDataType.md
@@ -1,4 +1,4 @@
-:cs202: :c++:
+:cs202: :c++: :cs303:
# Abstract Data Type (ADT)
CS 202 L14
@@ -6,3 +6,5 @@ CS 202 L14
## Notes
**Definition:** An ADT is a datatype that specifies it's interfaces but not implementation. This is similar to the relationship between an [[ISA.md]] and [[MicroArchitecture.md]].
+
+These are a focus of CS 303 and include things such as [Stack](Stack.md) and [Queue](Queue.md).
diff --git a/Algorithm.md b/Algorithm.md
@@ -5,6 +5,10 @@ Computer Architecture L2
## Notes
-**Definition: ** A step by step procedure to solve a problem where each step is definite (quantifiable), computable, and finite (ends eventually).
+**Definition:** A step by step procedure to solve a problem where each step is definite (quantifiable), computable, and finite (ends eventually).
This was described in computer architecture as despite algorithms being implemented in software, there are also algorithms involved in computer architecture.
+
+## CS 303
+
+**Definition:** An algorithm is a finite list of instructions written in a formal language to perform a specific task which will always terminate after a finite number of instructions have been executed and will always complete the task correctly.
diff --git a/Algorithms.md b/Algorithms.md
@@ -10,6 +10,28 @@ This is an index for links to notes taken about algorithms. These are CS related
[[PerlinNoise.md]]
[[FisherYatesShuffle.md]]
+#### CSCI 303 (DS&A)
+
+Ch 0 (algorithms):
+ - [[Algorithm.md]]
+ - [[Task.md]]
+ - [[TimeComplexity.md]]
+ - [CountingPrinciple](CountingPrinciple.md)
+
+Ch 1 (stacks and queues):
+ - [AbstractDataType](AbstractDataType.md)
+ - [Stack](Stack.md)
+ - [Queue](Queue.md)
+
+Ch 2 (Big-O and Asymptotic Complexity):
+ - [BigONotation](BigONotation.md)
+ - [AsymptoticNotation](AsymptoticNotation.md) (include asymptotic complexity class)
+ - [BigThetaNotation](BigThetaNotation.md)
+ - [Linearithmic](Linearithmic.md)
+
+Ch 3 (state analysis):
+ - [StateAnalysis](StateAnalysis.md)
+
#### Intro To Algorithms (MIT)
L1:
diff --git a/AsymptoticNotation.md b/AsymptoticNotation.md
@@ -1,4 +1,4 @@
-:cs: :algorithms:
+:cs: :algorithms: :cs303:
# Asymptotic Notation
L1 MIT
diff --git a/BigONotation.md b/BigONotation.md
@@ -0,0 +1,10 @@
+:cs303:
+# Big O Notation
+
+Ch 2
+
+## Notes
+
+**Definition:** Big O Notation is a system agnostic way to describe worst case runtime for an algorithm. With Big O Notation we formally state f(x) = O(g(x)) for some c and N such that f(n) <= c(g(x)) for all x >= N.
+
+Basically, there must be some constant multiple and some starting point such that the growth rate of the function f(x) does not ever surpass g(x). Note that the equality is a bit contentious as O(g(x)) describes a family of functions with coefficients c.
diff --git a/BigThetaNotation.md b/BigThetaNotation.md
@@ -0,0 +1,8 @@
+:cs303:
+# Big Theta Notation
+
+CS 303 Ch 2
+
+## Notes
+
+**Definition:** We use big theta notation to state that an algorithm has exactly the same asymptotic complexity as some other algorithm. This means big theta of f is equivalent to big theta of g where each of them will (almost always) have a unique value for c (constant multiplier) and a unique value for N (where N <=x).
diff --git a/CountingPrinciple.md b/CountingPrinciple.md
@@ -0,0 +1,8 @@
+:cs303:
+# Counting Principle
+
+Ch 0
+
+## Notes
+
+**Definition:** The counting principle is an enumeration technique where you determine the branching factor at each step and multiply all branching factors to find the total number of possible paths.
diff --git a/Linearithmic.md b/Linearithmic.md
@@ -0,0 +1,8 @@
+:cs303:
+# Linearithmic
+
+Ch 2
+
+## Notes
+
+**Definition:** Linearithmic time complexity (or linear log or just n log n) is a commonly used name to describe n log n time complexity.
diff --git a/MutuallyIndependent.md b/MutuallyIndependent.md
@@ -0,0 +1,8 @@
+:prob:
+# Mutually Independent
+
+Ch 1.4
+
+## Notes
+
+**Definition:** A set of mutually independent events is a set such that all conditional probabilities (any combination) are equivalent to the unconditioned probabilities.
diff --git a/PairwiseIndependence.md b/PairwiseIndependence.md
@@ -0,0 +1,8 @@
+:prob:
+# Pairwise Independent
+
+Ch 1.4
+
+## Notes
+
+**Definition:** Pairwise independent events are two events such that the conditional probabilities of either are equivalent to the unconditioned probabilities.
diff --git a/Queue.md b/Queue.md
@@ -1,7 +1,7 @@
-:cs202: :c++:
+:cs202: :c++: :cs303:
# Queue
-CS202 L14
+CS202 L14 / CS303 Ch 1
## Notes
diff --git a/Stack.md b/Stack.md
@@ -1,7 +1,7 @@
-:cs202: :c++:
+:cs202: :c++: :cs303:
# Stack
-CS202 L14
+CS202 L14 / CS303 Ch 1
## Notes
@@ -13,6 +13,6 @@ peek: get top element. This can also be implemented by doing pop then pushing th
pop: remove from top
-This can be imlemented as a [[SinglyLinkedList.md]]
+This can be implemented as a [[SinglyLinkedList.md]]
See [[Queue.md]] for information about the fifo implementation.
diff --git a/StateAnalysis.md b/StateAnalysis.md
@@ -0,0 +1,8 @@
+:cs303:
+# State Analysis
+
+Ch 3
+
+## Notes
+
+**Definition:** State analysis, in the context of algorithms, is a strategy for computing the time complexity of an algorithm that analyzes the state of the algorithm instead of describing each line of code and their associated complexity which becomes unruly as algorithms become more complex.
diff --git a/StatisticsAndProbability.md b/StatisticsAndProbability.md
@@ -35,9 +35,16 @@ Chapter 1.3:
Chapter 1.4:
- [ConditionalProbability](ConditionalProbability.md)
+
+Chapter 1.5:
- [IndependentEvents](IndependentEvents.md)
- - PairwiseIndependence
- - MutuallyIndependent
+ - [PairwiseIndependence](PairwiseIndependence.md)
+ - [MutuallyIndependent](MutuallyIndependent.md)
+
+Chapter 1.6:
+ - Bayes Theroem
+ - Prior Probabilities
+ - Posterior Probabilities
---
diff --git a/Task.md b/Task.md
@@ -0,0 +1,10 @@
+:cs303: :algorithms:
+# Task
+
+Ch 0
+
+## Notes
+
+**Definition:** A task is a function from I to O where I is the set of all valid inputs and O is the set of all valid outputs.
+
+In this definition we are using the formal definition of a function from math.
diff --git a/TimeComplexity.md b/TimeComplexity.md
@@ -0,0 +1,8 @@
+:cs303: :algorithms:
+# Time Complexity
+
+Ch 2
+
+## Notes
+
+**Definition:** Let A be an algorithm. The worst case, best case, or average case time complexity of A is the function f: N->N where f(n) is the max, min, or average number of instructions executed by the algorithm for all inputs of size n bytes.
