Differences

This shows you the differences between two versions of the page.

--- algorithm_techniques [2020/08/20 17:00]
paul [Graphs]
+++ algorithm_techniques [2020/10/09 19:39] (current)
@@ Line 92: / Line 92: @@
 {{ ::merge_sort.png?direct&400 |}}
+===== Heaps =====
+Heaps are implemented in C++ as priority_queue.
+See [[https://stackoverflow.com/questions/39514469/argument-for-o1-average-case-complexity-of-heap-insertion|this discussions]].
+Heaps allow us to put data into them and keep track of the mininum or maximum
+value. It does not ordered each individual element.
 ==== Heap Sort ====
@@ Line 270: / Line 279: @@
 {{:pasted:20200816-072543.png?500}}
+==== Iterative Postorder Traversal ====
+You can accomplish a postorder traversal iteratively with two stacks. Here is
+the algorithm:
+<code>
+. Put root in stack 1.
+. While Stack 1 isn't empty
+.   pop top element of stack one and put it in stack 2
+.   put the left and right child of that element in stack 1
+. Print contents of stack 2
+</code>
 ===== Greedy Algorithms =====
@@ Line 440: / Line 463: @@
 ===== Graphs =====
+Graphs are a great way of storing the way data depends on data.
+==== Types of Graphs =====
+=== Undirected Graphs and Directed Graphs ===
+Undirected Graphs don't have edges to them. You can go from A to B or B to A. No problems!
+{{:pasted:20200820-171741.png}}
+=== Directed Acyclical Graphs (DAGS) ===
+{{:pasted:20200820-171816.png?500}}
+These graphs don't have any cycles, so you can you explore the whole connected graph without entering a loop.
+==== Adjacency Lists ====
 Graphs can be represented by Adjacency Matrices, and Adjacency lists. Adjacency
@@ Line 446: / Line 487: @@
 {{:pasted:20200820-165811.png}}
-==== Adjacency Lists ====
 Adjacency lists
@@ Line 468: / Line 507: @@
 </code>
-Undirected Graphs: Graphs don't have edges to them. You can go from A to B or B to A. No problems!
+[[https://www.khanacademy.org/computing/computer-science/algorithms/graph-representation/a/representing-graphs| Resource for more info.]]
-{{:pasted:20200815-161634.png}}
-Assumptions to keep in mind. We only ever care about nodes reachable by our given start node.
-You can traverse a Graph in two ways, Depth First Traversal and Breath First Traversal.
 ==== Graph Edges ====
@@ Line 486: / Line 519: @@
 {{:pasted:20200820-025218.png?500}}
-==== Depth First Traversal ====
+==== Graph Traversal ====
+You can traverse a Graph in two ways, Depth First Traversal and Breath First Traversal.
+=== Depth First Traversal ===
+As the name implies, Depth First Traversal, or Depth First Search traversal,
+involves going all the way down to vertex that has no other possible unexplored
+vertices connected to it, and then backtracking to a previous node.
+The best analogy for this is leaving breadcrumbs while exploring a maze. If you
+encounter your breadcrumbs, turn back to the next closes turn, and turn into an
+explored area. Thanks to Erik Demaine for this analogy.
 {{:pasted:20200815-170533.png?400}}
@@ Line 542: / Line 586: @@
   - Sort input candidates.
   - Make a boolean flag array to track used elements.
-  - Recurse over the canditations, choosing and building a solution, and then unchoosing.
+  - Recurse over the candidates, choosing and building a solution, and then unchoosing.
   - If the next option is the same, skip it.
+===== Loop Detection / Floyd Algo =====