Differences

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

--- algorithm_techniques [2020/08/20 16:58]
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 447: / Line 488: @@
 {{:pasted:20200820-165811.png}}
-Undirected Graphs: Graphs don't have edges to them. You can go from A to B or B to A. No problems!
+Adjacency lists
+Representing a graph with adjacency lists combines adjacency matrices with edge lists. For each vertex iii, store an array of the vertices adjacent to it. We typically have an array of |V| adjacency lists, one adjacency list per vertex. Here's an adjacency-list representation of the social network graph:
-{{:pasted:20200815-161634.png}}
+{{:pasted:20200820-165933.png}}
-Assumptions to keep in mind. We only ever care about nodes reachable by our given start node.
+In code, we represent these adjacency lists with a vector of vector of ints:
+<code>
+[ [1, 6, 8],
+  [0, 4, 6, 9],
+  [4, 6],
+  [4, 5, 8],
+  [1, 2, 3, 5, 9],
+  [3, 4],
+  [0, 1, 2],
+  [8, 9],
+  [0, 3, 7],
+  [1, 4, 7] ]
+</code>
-You can traverse a Graph in two ways, Depth First Traversal and Breath First Traversal.
+[[https://www.khanacademy.org/computing/computer-science/algorithms/graph-representation/a/representing-graphs| Resource for more info.]]
 ==== Graph Edges ====
@@ Line 465: / 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 521: / 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 =====