Differences

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

Link to this comparison view

Both sides previous revision Previous revision
Next revision 		Previous revision
algorithm_techniques [2020/08/20 02:17]
paul [Depth First Traversal] 		algorithm_techniques [2020/10/09 19:39] (current)
Line 92: Line 92:
  
 {{ ::merge_sort.png?direct&400 |}} {{ ::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 ==== ==== Heap Sort ====
Line 270: Line 279:
  
 {{:pasted:20200816-072543.png?500}} {{:pasted:20200816-072543.png?500}}
 +
 +==== Iterative Postorder Traversal ====
 +
 +You can accomplish a postorder traversal iteratively with two stacks. Here is
 +the algorithm:
 +
 +<code>
 +1. Put root in stack 1.
 +2. While Stack 1 isn't empty
 +3.   pop top element of stack one and put it in stack 2
 +4.   put the left and right child of that element in stack 1
 +5. Print contents of stack 2
 +</code>
 +
 ===== Greedy Algorithms ===== ===== Greedy Algorithms =====
  
Line 441: Line 464:
 ===== Graphs ===== ===== Graphs =====
  
-Undirected Graphs: Graphs don't have edges to them. You can go from A to B or B to A. No problems!+Graphs are a great way of storing the way data depends on data.
  
-{{:pasted:20200815-161634.png}}+==== Types of Graphs =====
  
-Assumptions to keep in mind. We only ever care about nodes reachable by our given start node.+=== 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 
 +Matrices are rarely used because they take up ''V²'' space. Adjacency Matrices 
 +are 2D boolean arrays that specify if a vertex I is connected to vertex J. 
 + 
 +{{:pasted:20200820-165811.png}} 
 + 
 +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:20200820-165933.png}} 
 + 
 +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> 
 + 
 +[[https://www.khanacademy.org/computing/computer-science/algorithms/graph-representation/a/representing-graphs| Resource for more info.]] 
 + 
 +==== Graph Edges ==== 
 + 
 +A **Back Edge** is an edge that connects a vertex to a vertex that is discovered before it's parent. 
 + 
 +Think about it like this: When you apply a DFS on a graph you fix some path that the algorithm chooses. Now in the given case: 0->1->2->3->4. As in the article mentioned, the source graph contains the edges 4-2 and 3-1. When the DFS reaches 3 it could choose 1 but 1 is already in your path so it is a back edge and therefore, as mentioned in the source, a possible alternative path. 
 + 
 +Are 2-1, 3-2, and 4-3 back edges too? For a different path they can be. Suppose your DFS chooses 0->1->3->2->4 then 2-1 and 4-3 are back edges. 
 + 
 +{{:pasted:20200820-025218.png?500}} 
 + 
 +==== Graph Traversal ====
  
 You can traverse a Graph in two ways, Depth First Traversal and Breath First Traversal. You can traverse a Graph in two ways, Depth First Traversal and Breath First Traversal.
  
-==== Depth 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}} {{:pasted:20200815-170533.png?400}}
Line 490: Line 571:
 3. While queue not empty 3. While queue not empty
 4.    Pop front of the queue. 4.    Pop front of the queue.
-4.    Visit all neighboring verticles  +5.    Visit all neighboring verticles  
-      If they are not seen +6.    If they are not seen 
-5.      Push them onto the queue.+7.      Push them onto the queue.
 </code> </code>
  
Line 505: Line 586:
   - Sort input candidates.   - Sort input candidates.
   - Make a boolean flag array to track used elements.   - 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.   - If the next option is the same, skip it.
 +
 +===== Loop Detection / Floyd Algo =====
  
  
  • algorithm_techniques.1597889846.txt.gz
  • Last modified: 2020/08/20 02:17
  • by paul