commit db3bd2d675567bcd5434b1554fad841593e4023e
parent 325457d2f05a2639c95e13dcb9741bc06e7f0912
Author: Andrew <andrewlaack1@gmail.com>
Date: Thu, 18 Apr 2024 07:00:44 -0500
completed cs202 l14
Diffstat:
20 files changed, 145 insertions(+), 6 deletions(-)
diff --git a/AbstractDataType.md b/AbstractDataType.md
@@ -0,0 +1,8 @@
+:cs202: :c++:
+# Abstract Data Type (ADT)
+
+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]].
diff --git a/Adder.md b/Adder.md
@@ -0,0 +1 @@
+:todo:
diff --git a/BinaryTree.md b/BinaryTree.md
@@ -0,0 +1,12 @@
+:cs202:
+# Binary Tree
+
+CS202 L14
+
+## Notes
+
+**Definition:** For any node n, all elements in the left subtree are less than the current node and everything in the right subtree is greater than the current node.
+
+For a generic binary tree, there is no necessitation that the left a right trees are in any way balanced.
+
+A balanced binary tree has a logn time complexity
diff --git a/BloomFilter.md b/BloomFilter.md
@@ -0,0 +1 @@
+:todo:
diff --git a/BreadthFirstSearch.md b/BreadthFirstSearch.md
@@ -0,0 +1,10 @@
+:cs202: :graphs: :trees: :c++:
+# BFS
+
+CS 202 L14
+
+## Notes
+
+**Definition:** Search algorithm that moves its way outward from the root node. This is different than [[DepthFirstSearch.md]] as it does not go all the way down and then search but instead moves away from the root.
+
+This uses a [[Queue.md]] to search.
diff --git a/CS202.md b/CS202.md
@@ -7,4 +7,10 @@ This is the index for my cs 202 notes.
[[LinkedLists.md]]
[[MemoryManagement.md]]
-
+[[AbstractDataType.md]]
+[[Stack.md]]
+[[Queue.md]]
+[[Tree.md]]
+[[BinaryTree.md]]
+[[DepthFirstSearch.md]]
+[[BreadthFirstSearch.md]]
diff --git a/Cache.md b/Cache.md
@@ -1,4 +1,4 @@
-:computer-architecture: :cpu: :cache:
+:todo: :computer-architecture: :cpu: :cache:
# Cache
## Notes
diff --git a/CircularDoublyLinkedList.md b/CircularDoublyLinkedList.md
@@ -0,0 +1,9 @@
+# Circular Doubly Linked List
+
+CS202 L14
+
+## Notes
+
+**Definition:** This is a doubly linked list where the last pointer points to the first and the first pointer of the first element points to the last.
+
+Can be used wherever [[CircularLinkedList.md]]s are used and are better when bi-directional movement is required. I am having trouble thinking of when this would ever be useful.
diff --git a/CircularLinkedList.md b/CircularLinkedList.md
@@ -0,0 +1,9 @@
+# Circular Linked List
+
+CS202 L14
+
+## Notes
+
+**Definition:** This is a singly linked list where the last node points back to the first node.
+
+This could be useful when implementing OS based threads as you would need to cycle through threads of execution when one thread gets blocked. There are not many other uses for this datastructure beyond this.
diff --git a/ComputerArchitecture.md b/ComputerArchitecture.md
@@ -24,6 +24,7 @@ Links to information learned from computer architecture course
[[DRAMRowHammer.md]]
[[VonNeumannModel.md]]
[[BarrierSynchronization.md]]
+[[MicroArchitecture.md]]
To do:
@@ -31,7 +32,7 @@ To do:
[[PipelineControl.md]]
[[CircuitTechnology.md]]
[[SRAM.md]]
-[[MicroArchitecture.md]]
+[[Adder.md]]
[[Cache.md]]
[[BloomFilter.md]]
-
+[[CriticalPath.md]]
diff --git a/CriticalPath.md b/CriticalPath.md
@@ -0,0 +1 @@
+:todo:
diff --git a/DepthFirstSearch.md b/DepthFirstSearch.md
@@ -0,0 +1,12 @@
+:cs202: :c++: :graphs: :trees:
+# DFS
+
+CS202 L14
+
+## Notes
+
+**Definition:** Searching algorithm that traverses until reaching a leaf node then going back by one and doing the same on the other subtree.
+
+This normally uses the call [[Stack.md]] to search.
+
+Also see [[BreadthFirstSearch.md]]
diff --git a/Graphs.md b/Graphs.md
@@ -9,8 +9,7 @@ Abstract Math 10.2.
**Cycle:** A cycle in a graph is a set of vertices such that traversal can be done back to itself.
-**Tree:** Trees are defined simply as graphs without cycles. There is no implication about split numbers or anything of the sort, but something interesting is that in all cases it must be true that the number of edges is one less than the number of vertices. This can be proved through [[StrongInduction.md]].
-
+Also see [[Tree.md]]
diff --git a/LinkedLists.md b/LinkedLists.md
@@ -11,5 +11,12 @@ Inserting into and removing from linked lists is faster than arrays when resizin
## Types
+Acyclic Linked Lists:
+
[[SinglyLinkedList.md]]
[[DoublyLinkedList.md]]
+
+Cyclic Linked Lists:
+
+[[CircularLinkedList.md]]
+[[CircularDoublyLinkedList.md]]
diff --git a/MicroArchitecture.md b/MicroArchitecture.md
@@ -6,3 +6,5 @@ Computer Architecture L2
## Notes
**Definition:** The implementation of an agreed upon ISA. These are the underlying mechanics that are not exposed to the OS/System developer.
+
+There are many micro architecture implementations of each ISA, but very few different ISAs because changes to ISAs breaks compatibility.
diff --git a/PipelineControl.md b/PipelineControl.md
@@ -0,0 +1 @@
+:todo:
diff --git a/Queue.md b/Queue.md
@@ -0,0 +1,16 @@
+:cs202: :c++:
+# Queue
+
+CS202 L14
+
+## Notes
+
+**Definition:** This is a datatype that works on a first in first out basis. This is often implemented using a [[SinglyLinkedList.md]] with a link to the tail (where more nodes would be added). This is also often implemented such that you add to the end and remove from the start.
+
+enqueue: add to queue
+
+dequeue: remove from queue
+
+peek: view the front element
+
+It is important to note, generally, people implement these to add to the back and remove from the start although either direction is functionally equivalent. See [[Stack.md]] for information about a lifo approach.
diff --git a/SRAM.md b/SRAM.md
@@ -0,0 +1 @@
+:todo:
diff --git a/Stack.md b/Stack.md
@@ -0,0 +1,18 @@
+:cs202: :c++:
+# Stack
+
+CS202 L14
+
+## Notes
+
+**Definition:** This is a data structure that uses the lifo approach where you add to the top and remove from the top of the struct.
+
+push: add to stack
+
+peek: get top element. This can also be implemented by doing pop then pushing the result.
+
+pop: remove from top
+
+This can be imlemented as a [[SinglyLinkedList.md]]
+
+See [[Queue.md]] for information about the fifo implementation.
diff --git a/Tree.md b/Tree.md
@@ -0,0 +1,25 @@
+:c++: :math310: :cs202:
+# Tree
+
+Abstract Math and CS202
+
+## Notes
+
+**Definition:** Trees are graphs without cycles. Additionally, at least in cs, you can only have one root as a node can have no more than one parent.
+
+There is no implication about split numbers or anything of the sort, but something interesting is that in all cases it must be true that the number of edges is one less than the number of vertices. This can be proved through [[StrongInduction.md]].
+
+
+**Root:** This is a node that has no parents
+
+**Parent:** The node above a given node
+
+**Child:** A node below a given node
+
+**Leaf:** These are nodes without children
+
+**Subtree:** A subtree is a section of a tree that is based upon a new root node that cuts off everything above it.
+
+See [[LinkedLists.md]] as linked lists (when non-cyclic) are a form of tree.
+
+Also see [[BinaryTree.md]] for a specific tree type.
