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/15 19:10]
127.0.0.1 external edit 		algorithm_techniques [2020/10/09 19:39] (current)
Line 1: Line 1:
 ====== Algorithm Techniques ====== ====== Algorithm Techniques ======
 +
 +For explanations of problems see [[Algorithm Problems]].
 +
 +For helpful reference, see [[Coding Cheat Sheet]].
  
 An algorithm is a well-defined computational procedure that takes in a set of values as inputs and produces a set of values as outputs. An algorithm is thus a sequence of computational steps that transform input into output. An algorithm is a well-defined computational procedure that takes in a set of values as inputs and produces a set of values as outputs. An algorithm is thus a sequence of computational steps that transform input into output.
Line 88: 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 260: Line 273:
 When traversing recursively, always thing of the following: When traversing recursively, always thing of the following:
  
-1. What is my base case that I am checking for? +  - What is my base case that I am checking for? 
-2. What nodes will I call again recursively?+  - What nodes will I call again recursively? 
 + 
 +{{:pasted:20200816-072505.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 434: 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}}
  
-DFT is accomplished with a **Stack**. Algorithm:+DFT is accomplished with a **Stack**.  
 + 
 +The basic algorithm:
  
 <code> <code>
Line 458: Line 549:
 8.      pop vertex off top of the stack  8.      pop vertex off top of the stack 
 </code> </code>
 +
 +For **Directed Graphs** or graphs that contain disconnected graphs, we need an extra step to make sure we visit all vertices in the graph.
 +
 +
 +{{:pasted:20200820-014828.png?400}}{{:pasted:20200820-014702.png?400}}
 +
 +V is a set of vertices in our graph. Adj is the adjacency list.
 +
 +{{:pasted:20200820-021645.png?500}}
 +   
  
 ==== Breath First Traversal ==== ==== Breath First Traversal ====
Line 470: 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 485: 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.1597518655.txt.gz
  • Last modified: 2020/08/15 19:10
  • by 127.0.0.1