<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by Abdul Salam on Medium]]></title>
        <description><![CDATA[Stories by Abdul Salam on Medium]]></description>
        <link>https://medium.com/@sleepingfish?source=rss-5ec37cc04460------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/2*RHFKYD9epC8TIpZJfatYaA.jpeg</url>
            <title>Stories by Abdul Salam on Medium</title>
            <link>https://medium.com/@sleepingfish?source=rss-5ec37cc04460------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Tue, 17 Nov 2026 07:43:37 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@sleepingfish/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[Solving Tower of Hanoi Puzzle in Python]]></title>
            <link>https://levelup.gitconnected.com/solving-tower-of-hanoi-puzzle-in-python-c56114f59c36?source=rss-5ec37cc04460------2</link>
            <guid isPermaLink="false">https://medium.com/p/c56114f59c36</guid>
            <category><![CDATA[writing]]></category>
            <category><![CDATA[python]]></category>
            <category><![CDATA[technology]]></category>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[algorithms]]></category>
            <dc:creator><![CDATA[Abdul Salam]]></dc:creator>
            <pubDate>Sun, 14 Mar 2021 11:14:43 GMT</pubDate>
            <atom:updated>2023-02-13T16:57:20.765Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*aXPG-isJuVfCqi28" /><figcaption>Photo by <a href="https://unsplash.com/@milada_vigerova?utm_source=medium&amp;utm_medium=referral">Milada Vigerova</a> on <a href="https://unsplash.com/?utm_source=medium&amp;utm_medium=referral">Unsplash</a></figcaption></figure><p>“The Tower of Hanoi is a mathematical game or puzzle. It consists of three rods and a number of disks of different sizes, which can slide onto any rod. The puzzle starts with the disks in a neat stack in ascending order of size on one rod, the smallest at the top, thus making a conical shape.</p><p>The objective of the puzzle is to move the entire stack to last rod, obeying the following simple rules:</p><ul><li>Only one disk can be moved at a time.</li><li>Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack or on an empty rod.</li><li>No larger disk may be placed on top of a smaller disk.” — <a href="https://en.wikipedia.org/wiki/Tower_of_Hanoi">Wikipedia</a>.</li></ul><h3><strong>The Algorithm</strong></h3><p>let say we have 3 rods, R1, R2 and R3 and N disks. Initially, all N disks are at R1 and we have to move all N disks to R3.</p><p>Since we know we can move one disk at a time from top of stacks, and no larger disk can be stacked on top of a smaller disk, the algorithms is as follows:</p><ul><li>From R1, move top N-1 disks to R2.</li><li>From R1, Move 1 (The biggest one) Disk to R3.</li><li>From R2, move N-1 disks to R3.</li></ul><p>and that’s it, that is all the algorithm.</p><h3><strong>The Code</strong></h3><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/149cc1a01a42aa0bf30b07880fda0b5f/href">https://medium.com/media/149cc1a01a42aa0bf30b07880fda0b5f/href</a></iframe><p>Calling the function with, foo(r1=0, r2=1, r3=2, n_pegs=3) . It gives,</p><pre>[&#39;123&#39;, &#39;&#39;, &#39;&#39;]<br>[&#39;23&#39;, &#39;&#39;, &#39;1&#39;]<br>[&#39;3&#39;, &#39;2&#39;, &#39;1&#39;]<br>[&#39;3&#39;, &#39;12&#39;, &#39;&#39;]<br>[&#39;&#39;, &#39;12&#39;, &#39;3&#39;]<br>[&#39;1&#39;, &#39;2&#39;, &#39;3&#39;]<br>[&#39;1&#39;, &#39;&#39;, &#39;23&#39;]<br>[&#39;&#39;, &#39;&#39;, &#39;123&#39;]</pre><h3>Time Complexity</h3><p>Above recursive function can be written as,</p><pre>F(N) = 2 * F(N - 1) + 1    and,<br>F(1) = 1</pre><pre>where,<br>N is number of pegs/disks</pre><p>and upon solving the above function,</p><pre>F(N) = 2^N - 1</pre><p>Thus, the time complexity of above algorithm is O(2^N).</p><h3>Extras</h3><p>In the algorithm, we are moving first N-1 disks first, then the last one, after that we are moving those first N-1 disks. Why do we not moving the fist disk first then the last N-1 disks and then the first disk?</p><p>Hint: see the comment of this blog.</p><h3>Resource</h3><p><a href="https://www.youtube.com/watch?v=WPSeyjX1-4s">MIT OCW’s lecture on recursion.</a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=c56114f59c36" width="1" height="1" alt=""><hr><p><a href="https://levelup.gitconnected.com/solving-tower-of-hanoi-puzzle-in-python-c56114f59c36">Solving Tower of Hanoi Puzzle in Python</a> was originally published in <a href="https://levelup.gitconnected.com/">Level Up Coding</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Dijkstra Algorithm in Python]]></title>
            <link>https://levelup.gitconnected.com/dijkstra-algorithm-in-python-8f0e75e3f16e?source=rss-5ec37cc04460------2</link>
            <guid isPermaLink="false">https://medium.com/p/8f0e75e3f16e</guid>
            <category><![CDATA[algorithms]]></category>
            <category><![CDATA[python]]></category>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[technology]]></category>
            <category><![CDATA[writing]]></category>
            <dc:creator><![CDATA[Abdul Salam]]></dc:creator>
            <pubDate>Sat, 13 Feb 2021 19:26:51 GMT</pubDate>
            <atom:updated>2021-02-23T15:09:48.912Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*wxCtdLF7f-xo6f92" /><figcaption>Photo by <a href="https://unsplash.com/@alinnnaaaa?utm_source=medium&amp;utm_medium=referral">Alina Grubnyak</a> on <a href="https://unsplash.com/?utm_source=medium&amp;utm_medium=referral">Unsplash</a></figcaption></figure><p>It is a well-known Algorithm used to find the shortest distance and shortest path from a single source node to all other nodes in a graph. This algorithm only works on graphs, where there are no negative cycles in them (i.e. a <a href="https://en.wikipedia.org/wiki/Cycle_(graph_theory)">cycle</a> whose edges sum to a negative value).</p><h3>The algorithm</h3><ol><li>Create a set “seen” to keep track of visited nodes.</li><li>Create a dictionary “<em>parentsMap</em>” for parents map to reconstruct the path after the execution of the algorithm.</li><li>Create a dictionary “<em>nodeCosts</em>” for keeping track of minimum costs for reaching different nodes from the source node, and initialize the cost for the source node as 0.</li><li>Create a priority queue data structure (in python use <em>heapq </em>module with list) and push a tuple (<em>0, source node</em>)<em> </em>in the Priority Queue (heap), representing (the cost to the node from the source node, the node itself).</li><li>loop inside a while loop until there is nothing in the priority queue. while looping, pop the node with minimum cost.</li><li>loop through all of the pop node’s adjacent nodes. if they have not been explored before, and have total costs minimum than the cost in the “<em>nodeCosts</em>” add them too to the priority queue and update the “<em>parentsMap</em>”.</li><li>Reconstruct the path from the “<em>parentsMap</em>”.</li></ol><h3>The CODE</h3><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/c83badc85558ac78a9d6e681019afa5f/href">https://medium.com/media/c83badc85558ac78a9d6e681019afa5f/href</a></iframe><p><em>Reconstruction of a path using parentsMap is trivial.</em></p><h3><strong>Extras</strong></h3><ul><li>If we just want the shortest path from some source node to some other node, say “end node”, we can early exit from while loop (when we are popping the minimum costs nodes from the heap and that node, happens to be the end node).</li><li>Above implementation is a lazy implementation of the Dijkstra algorithm (we are adding nodes to the heap but there may be that same node in that heap with a higher cost, which is coming from a different path) there is also eager implementation which one can find at <a href="https://github.com/abecus/DS-and-Algorithms/blob/master/graph/dijkstra.py">my GitHub</a>.</li></ul><p>If you found any error anywhere in the blog or want to suggest something to add to it, consider commenting the same.</p><p>Thanks for reading.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=8f0e75e3f16e" width="1" height="1" alt=""><hr><p><a href="https://levelup.gitconnected.com/dijkstra-algorithm-in-python-8f0e75e3f16e">Dijkstra Algorithm in Python</a> was originally published in <a href="https://levelup.gitconnected.com/">Level Up Coding</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Typing Effect in React]]></title>
            <link>https://levelup.gitconnected.com/typing-effect-in-react-56697def0473?source=rss-5ec37cc04460------2</link>
            <guid isPermaLink="false">https://medium.com/p/56697def0473</guid>
            <category><![CDATA[javascript]]></category>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[react]]></category>
            <category><![CDATA[web-development]]></category>
            <category><![CDATA[technology]]></category>
            <dc:creator><![CDATA[Abdul Salam]]></dc:creator>
            <pubDate>Mon, 30 Nov 2020 08:54:33 GMT</pubDate>
            <atom:updated>2022-01-12T10:07:50.789Z</atom:updated>
            <content:encoded><![CDATA[<p>Today, we will learn how to implement a Typing Effect in React from scratch.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*MJ2a1P8c2VpZ9RN1" /><figcaption>Photo by <a href="https://unsplash.com/@rafaelabiazi?utm_source=medium&amp;utm_medium=referral">Rafaela Biazi</a> on <a href="https://unsplash.com/?utm_source=medium&amp;utm_medium=referral">Unsplash</a></figcaption></figure><p>A working Example can be found <a href="https://abecus.github.io/portfolio/">here</a>.</p><h3><strong>Setting-Up</strong></h3><p>Start by creating a starter react app using npx create-react-app my-app or follow the procedure from <a href="https://reactjs.org/docs/create-a-new-react-app.html">here</a>.</p><p>Go to App.js, remove all redundant Elements, and add a h1tag where the typing effect will take place.</p><p>Now import to add additional hooks using import {useEfect, useState} from &quot;react&quot;;</p><p>Create an array of words that will be type one by one.</p><p>Now we have to keep track of the index of the word array for typing a specific word, so we will use the useState hook because we also want to update the index on the runtime (after a word has been typed). For this use const [index, setIndex] = useState(0);</p><p>Also, we will be displaying substrings of words, and each time in typing effect the length of that substring will be change. let make it first increasing and then decreasing. so we have to keep track of the length of the substring and whether the length is increasing or decreasing. for this add additional useStates,</p><pre>const [subIndex, setSubIndex] = useState(0);<br>const [reverse, setReverse] = useState(false);</pre><p>Also, add a useState hook for that straight typing line, to tell when to blink. Now the full code looks like this,</p><pre>import React, { useState, useEffect } from &quot;react&quot;;<br>const words = [&quot;Developer&quot;, &quot;Programmer&quot;];</pre><pre>export default function App() {<br>  const [index, setIndex] = useState(0);<br>  const [subIndex, setSubIndex] = useState(0);<br>  const [blink, setBlink] = useState(true); <br>  const [reverse, setReverse] = useState(false);</pre><pre>return (<br>  &lt;&gt;<br>    &lt;h1&gt;<br>      {`${words[index].substring(0, subIndex)}${blink ? &quot;|&quot; : &quot;&quot;}`}<br>    &lt;/h1&gt;<br>  &lt;/&gt;)<br>}</pre><p>In the above code, the line in h1 displays a substring of length subIndex, of the word at index from the words array concatenated with “|” when the blink is true else “ ”.</p><p>Now we have to add logic to update the index, subIndex, and blink.</p><h3><strong>Adding Logic</strong></h3><p>we will use useEffect hook with setTimeout function for updating the values.</p><pre>export default function App() {</pre><pre><em>  ...<br>  // blinker<br>  </em>useEffect(() =&gt; {<br>    const timeout2 = setTimeout(() =&gt; {<br>    setBlink((prev) =&gt; !prev);<br>    }, 500);<br>    return () =&gt; clearTimeout(timeout2);<br>  }, [blink]);<br>  ...<br>return (<br>...<br>}</pre><p>The function inside useEffect will toggle the blink’s value at every 0.5sec. for more information on why the setTimeout function has to be in this way read <a href="https://overreacted.io/making-setinterval-declarative-with-react-hooks/">this</a>.</p><p>Now we will add logic for changing index’s and subIndex’s values.</p><pre>export default function App() {<br> ...</pre><pre><em>// typeWriter<br> </em>useEffect(() =&gt; {<br>  if (<br>    index === words.length - 1 &amp;&amp;<br>    subIndex === words[index].length<br>    ) {<br>      return;<br>    }</pre><pre>  if (<br>    subIndex === words[index].length + 1 &amp;&amp;<br>    index !== words.length - 1 &amp;&amp;<br>    !reverse<br>    ) {<br>      setReverse(true);<br>      return;<br>     }<br>   <br>  if (subIndex === 0 &amp;&amp; reverse) {<br>    setReverse(false);<br>    setIndex((prev) =&gt; prev + 1);<br>    return;<br>     }</pre><pre>   const timeout = setTimeout(() =&gt; {<br>   setSubIndex((prev) =&gt; prev + (reverse ? -1 : 1));<br>   }, 200);<br>   <br>   return () =&gt; clearTimeout(timeout);<br>   }, [subIndex, index, reverse]);<br> ...<br>}</pre><p>The code inside reads,</p><p>If the index equals the “words” array’s length -1 and subIndex equals last word’s length, don’t do anything. We have typed all words.</p><p>If subIndex is the current word’s length+1 (we have typed the word) and we are not at last word of words array (to make sure we don’t start decreasing the length of the substring of the last word) and reverse’s value is false, then we set the reverse value to true and return.</p><blockquote>Changing values of reverse, index and subIndex will rerender the component, and useEffect will be called again as the dependency array is set to it.</blockquote><p>In the next if statement, we check if the subIndex is 0 and reverse is true, then we increase the value of index and set the reverse to false.</p><p>Now the main part, we set the setTimeout function to increase if the reverse is false and decrease if the reverse is true by one every 0.2sec, which will make it like typing.</p><p>In the setTimeout function, the time for timeout is simple for both sides, but we can make it random when we are typing a word (the reverse is false) and small when we are removing the word (the reverse is true). to do that we may replace the time 200 with more complex logic Math.max(reverse ? 75 : subIndex===words[index].legth ? 1000:150, parseInt(Math.random()*350)));</p><p>And, that&#39;s it we have a type-writer now.</p><p><strong>Full Code</strong></p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/ff99ec51814df057655efb99d9e533e8/href">https://medium.com/media/ff99ec51814df057655efb99d9e533e8/href</a></iframe><p>Thanks for reading, if you found anything wrong in this blog or want to suggest something, your words will be welcomed.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=56697def0473" width="1" height="1" alt=""><hr><p><a href="https://levelup.gitconnected.com/typing-effect-in-react-56697def0473">Typing Effect in React</a> was originally published in <a href="https://levelup.gitconnected.com/">Level Up Coding</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[All Pythagorean Triplets less than equal N in Optimal Time Complexity]]></title>
            <link>https://levelup.gitconnected.com/all-pythagorean-triplets-less-than-equal-n-in-optimal-time-complexity-babfbe742337?source=rss-5ec37cc04460------2</link>
            <guid isPermaLink="false">https://medium.com/p/babfbe742337</guid>
            <category><![CDATA[education]]></category>
            <category><![CDATA[python]]></category>
            <category><![CDATA[technology]]></category>
            <category><![CDATA[mathematics]]></category>
            <category><![CDATA[startup]]></category>
            <dc:creator><![CDATA[Abdul Salam]]></dc:creator>
            <pubDate>Wed, 26 Aug 2020 19:53:45 GMT</pubDate>
            <atom:updated>2020-11-13T16:08:05.976Z</atom:updated>
            <content:encoded><![CDATA[<h3>All Pythagorean Triplets Less Than Equal to N in Optimal Time Complexity</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*kQfRs44MJgeLqkx5" /><figcaption>Photo by <a href="https://unsplash.com/@jannerboy62?utm_source=medium&amp;utm_medium=referral">Nick Fewings</a> on <a href="https://unsplash.com/?utm_source=medium&amp;utm_medium=referral">Unsplash</a></figcaption></figure><p>Pythagorean Triplets are set of three ordered positive integers (x,y,z) such that</p><pre>                       x^2 + y^2 = z^2    --- (1)<br>where,<br>x &lt; y &lt; z &lt;= N</pre><p>There are several techniques for generating Pythagorean Triplets for example using <a href="https://en.wikipedia.org/wiki/Gaussian_integers">Gaussian Integers</a> and using <a href="https://en.wikipedia.org/wiki/Formulas_for_generating_Pythagorean_triples">Euclid’s formula</a>. They can be used to generate all primitive Pythagorean Triplets, which again can be used to generate all non-primitive Pythagorean triplets by using the fact that the non Primitive Pythagorean triples are a positive integer multiple of primitive Pythagorean Triplets.</p><p>Generating Pythagorean triplets simply using two loops by iterating over x and y for all possible x and y, and checking if they satisfy Equation (1), takes time O(N² ). Also using the above methods for generating primitive Pythagorean triplets and from them generating all Pythagorean triples may take time O(N² ).</p><p>I used Equation (2) which easily follows from Equation (1) by solving the quadratic equation for x, thus for “ <em>x &gt; 0 ”,</em></p><pre>                      x = (b - a) + sqrt{2b(b - a)} --- (2)</pre><pre>where,<br>a = y - x,<br>b = z - x and<br>0 &lt; a &lt; b</pre><p>To find all Pythagorean Triples, we need to find the all values for <em>a</em> and <em>b</em> such that they are integers and Equation (2) holds. To find values for a and b, first, we will go step by step by finding ranges of each.</p><p>From the definition of <em>a</em>, it’s upper and lower limits depends upon <em>b</em> and can be written as</p><pre>                             1 ≤ a ≤ b − 1</pre><p>Since <em>b &gt;</em> <em>a</em> and since the lower limit of <em>a</em> is 1 thus lower limit of <em>b</em> is 2. Now we need To find the upper limit of <em>b</em>.</p><p>we know <em>0&lt; z ≤ N</em>, from (<em>b = z − x) </em>⇒ (<em>x + b ≤ N)</em>, thus from Equation (2) and <em>a = b − 1,</em></p><pre>                      (b − a) + sqrt{2b(b − a)} + b ≤ N           <br>                       ⇒ b + 1 + sqrt{2b} ≤ N<br>                       ⇒ 0 ≤ b ≤ N − sqrt{2N − 1}</pre><pre>Since first pythagorean Triple is (3,4,5), which makes N ≥ 5</pre><p>Let,<em> v = 2b(b − a)</em>, since <em>x</em> is a positive integer and <em>1 &lt; a &lt; b, </em>thus from Equation (2),</p><pre>                        2b ≤ v ≤ 2b(b − 1) and <br>                        sqrt{v} ∈ <strong>N</strong>        and <br>                        v (mod 2b) = 0</pre><p>To find actual values for <em>v</em>, We use <a href="https://www.mathsisfun.com/prime-factorization.html">prime factorization</a> of <em>2b</em>,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/319/1*S0ztM5WNll-GdKtKaPd1pA.jpeg" /><figcaption>Equation(3): Prime factorization of 2b</figcaption></figure><p>Where, p_i are k prime numbers, each of order α_i .</p><p>Using the prime factors of 2b we can calculate values for <em>v</em> by Equation,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/620/1*YHBAPO4diP3nXDGSEAUUnQ.jpeg" /><figcaption>Equation(4): solution for sqrt{v}</figcaption></figure><p>Where, p_j are k prime numbers, each of order ceil{a_j /2} and p_i = p_j and α_i = α_j for all i and j from Equation (3) and Equation (4) respectively. Equaltion (4) can be proved which is not rivial but not hard also.</p><h3><strong>The Algorithm</strong></h3><p>Everything has been setup, now we look at the pseudocode of the algorithm:</p><figure><a href="https://i.imgur.com/sOitf6i.jpg"><img alt="" src="https://cdn-images-1.medium.com/max/724/1*r3Lr6Jd1Ip11qjh1xNcFLQ.jpeg" /></a><figcaption>Psuedocode for generating Pythagorean Triples</figcaption></figure><p>Above algorithm in python can be written as,</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/f88de8ceb1959897e314f457729a6ece/href">https://medium.com/media/f88de8ceb1959897e314f457729a6ece/href</a></iframe><p>In the above algorithm, the for-loop runs for <em>N-sqrt{2N-1}</em> times, in it, we are calculating the prime factor of <em>2b </em>and then <em>γ </em>which can be calculated in time <em>O(ln N)</em> See Theorem 2. Since the number of Pythagorean Triplets <em>(x, y, z) </em>with <em>z ≤ N</em> are of order <em>O(N ln N)</em>[1][2], and in while loop we are computing Triples till <em>z ≤ N</em>, each time we iterate, we find a Pythagorean Triplet in order <em>O(1)</em>, because we are just doing multiplication to find <em>v</em> because v = (iγ)^2 and from <em>v</em> we are calculating <em>q </em>which is <em>b-a</em> by floor division of <em>v </em>by <em>2b</em>, having <em>q</em> and <em>v</em> we calculate, Triplets by</p><pre>                   x = (b − a) + sqrt{2b(b − a)}<br>                 ⇒ x = q + √(v)  </pre><pre>                   y = x + a<br>                 ⇒ y = a + √(v) </pre><pre>                   z = x + b <br>                 ⇒ z = q + √(v) + b</pre><p>and since operations in the while loop takes <em>O(1)</em> time, so, the while-loop takes <em>O(ln(N))</em> time, making the whole algorithm take <em>O(N ln N)</em> time and take <em>O(N)</em> space.</p><h3><strong>Computing SPF Array</strong></h3><p>For computing the smallest prime factor of each integer less than equal to N we can use the Eratosthenes Sieve Algorithm. This algorithm is not the optimal algorithm but since it does not hurt the runtime complexity of the whole algorithm its good.</p><p>There are other algorithms better than the Eratosthenes Sieve Algorithm, but for just as illustration and for sake of simplicity, we will stick with Eratosthenes Sieve Algorithm.</p><figure><a href="https://i.imgur.com/PQDJSzR.jpg"><img alt="" src="https://cdn-images-1.medium.com/max/898/1*nM2P97jbulO3EKAvC_R9NQ.jpeg" /></a><figcaption>Psuedocode for computing spf array</figcaption></figure><p>And, the above algorithm can be written in python as:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/62e3690a36fbda10e120853ba8f164c4/href">https://medium.com/media/62e3690a36fbda10e120853ba8f164c4/href</a></iframe><p>We can pre-compute the Lowest Prime Factor of each positive integer less than <em>N</em> in linear time[3] and store it in an array say <em>spf</em>, and use <em>spf </em>to compute the prime factors of <em>x </em>by Using <a href="https://en.wikipedia.org/wiki/Trial_division"><em>Trial dividion method</em></a><em> </em>. The Trial division using spf array takes time <em>O(ln x)</em> and <em>spf </em>array itself takes space <em>O(N)</em>[3] (space for storing an integer less than 2N).</p><h3><strong>Computing Gamma</strong></h3><p>By slightly changing Trial Division, we can also compute the <em>γ </em>using <em>spf </em>directly, See Algorithm below,</p><figure><a href="https://i.imgur.com/qVkcg13.jpg"><img alt="" src="https://cdn-images-1.medium.com/max/936/1*RtZ2zitgnfmJa9jCO6NfMA.jpeg" /></a><figcaption>Psuedocode for Computing gamma using spf array</figcaption></figure><p>above algorithm can be written in python as,</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/f7491e1d6e5250f2825a3009507412cf/href">https://medium.com/media/f7491e1d6e5250f2825a3009507412cf/href</a></iframe><p>If we do not want to store Lowest Prime Factors of each integer or in some conditions we have less storage space to work on, we need to calculate the prime factor of <em>2b</em> from start each time and then calculate <em>γ </em>for that, which can easily be done in <em>O(N^0.5) (</em>See Algorithm below),<em> </em>simply by replacing the “getReducedFactorization” function in final Algorithm with Trial division method and doing some changes, similar to the getReducedFactorization function to compute <em>γ</em>, thus making the final Algorithm take <em>O(N^1.5)</em>.</p><figure><a href="https://i.imgur.com/5nB2heG.jpg"><img alt="" src="https://cdn-images-1.medium.com/max/852/1*QXSL9UDc56Tn4TlRmVQtlA.jpeg" /></a><figcaption>Psuedocode for computing gamma directly</figcaption></figure><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/b6730d7d699ba245e5ffe1c17f7c3c44/href">https://medium.com/media/b6730d7d699ba245e5ffe1c17f7c3c44/href</a></iframe><p>Final Algorithm where all functions are in one python file can be found <a href="https://github.com/abecus/DS-and-Algorithms/blob/master/pytriplets/pythagoreanTriplets.py">Here</a>.</p><p>If you find any error please let me know so that other readers can get corrected results.</p><h3><strong>References</strong></h3><p>[1] Nowak, W. G., &amp; Recknagel, W. ”The distribution of Pythagorean triples and a threedimensional divisor problem”, Math. J. Okayama Univ, 31, 213–220, 1989.</p><p>[2] Manuel Benito, Juan L.Varona, ”Pythagorean triangles with legs less than n”, Journal of Computational and Applied Mathematics, Elsevier, 143, 117–126, 2002.</p><p>[3] David Gries, Jayadev Misra. ”A Linear Sieve Algorithm for Finding Prime Numbers”, 1978</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=babfbe742337" width="1" height="1" alt=""><hr><p><a href="https://levelup.gitconnected.com/all-pythagorean-triplets-less-than-equal-n-in-optimal-time-complexity-babfbe742337">All Pythagorean Triplets less than equal N in Optimal Time Complexity</a> was originally published in <a href="https://levelup.gitconnected.com/">Level Up Coding</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Mandelbrot Set with Python]]></title>
            <link>https://levelup.gitconnected.com/mandelbrot-set-with-python-983e9fc47f56?source=rss-5ec37cc04460------2</link>
            <guid isPermaLink="false">https://medium.com/p/983e9fc47f56</guid>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[education]]></category>
            <category><![CDATA[art]]></category>
            <category><![CDATA[productivity]]></category>
            <category><![CDATA[design]]></category>
            <dc:creator><![CDATA[Abdul Salam]]></dc:creator>
            <pubDate>Sun, 15 Mar 2020 09:46:21 GMT</pubDate>
            <atom:updated>2021-02-13T18:15:39.536Z</atom:updated>
            <content:encoded><![CDATA[<p><em>“A </em><a href="https://mathworld.wolfram.com/MandelbrotSet.html"><em>Mandelbrot set</em></a><em> marks the set of points in the </em><a href="https://mathworld.wolfram.com/ComplexPlane.html"><em>complex plane</em></a><em> such that the corresponding </em><a href="https://mathworld.wolfram.com/JuliaSet.html"><em>Julia set</em></a><em> is </em><a href="https://mathworld.wolfram.com/ConnectedSet.html"><em>connected</em></a><em> and not </em><a href="https://mathworld.wolfram.com/ComputableNumber.html"><em>computable</em></a><em>. The Mandelbrot set is the set obtained from the recurrence relation, Z_(n) = Z²_(n-1) + c, where, Z_(0) = c. where c is a complex number”</em> — Wolfram Mathworld.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/555/1*3NMRrHfC0BMw_BggU8GPvg.png" /><figcaption>Mandelbrot Set</figcaption></figure><p>The colors in a Mandelbrot set represents the iterations at which that complex number diverges to infinity (we can use here some threshold instead of infinity). Generally, the black color is for numbers that converge to zero (here we can use some maximum iteration limit under which if the number is not greater than the threshold value we assume it is converging to zero) and <em>that&#39;s all in a Mandelbrot set (not really)</em>.</p><h3><strong>Let’s Code</strong></h3><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/f7bbfd9f0a669086f30b61a70551d5a4/href">https://medium.com/media/f7bbfd9f0a669086f30b61a70551d5a4/href</a></iframe><p>The above code is used to find if a complex number diverges under max_steps and if it does then when.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/19ddabef4b3f4471461802558b7c99a2/href">https://medium.com/media/19ddabef4b3f4471461802558b7c99a2/href</a></iframe><p>Line 4: Maps the image coordinate to the real-valued number in the range [-2,0.47] for x and in the range [-1.12,1.12] for y (with a margin of 0.01 on all sides), which will be used to make complex numbers. Because it is known that the set is bounded with “<em>The left-most extent of the set ends with the spike at x = -2, and the right side extends out to approximately x = 0.47. The top and bottom are at approximately y = ± 1.12, respectively</em>” — <a href="https://www.fractalus.com/kerry/articles/area/mandelbrot-area.html">fractalus</a>.</p><p>Line 5: Creates a Numpy array of shape N*N, to store the pixel values of Mandelbrot Set.</p><p>Line 6–8: We loop through all pixels coordinates, using two loops, and calculate the pixel value for that coordinate (it is really the iteration value).</p><p>Line 9–10: put the pixel value in the image. I used<em> “img[y][x]=255-it” </em>because more iterations mean heading toward brack color<em>. (</em>I don’t know why does the image gets rotated -90 degree, but I rotated it 90 degrees by using <em>“img[y][x]=255-it” instead of using “img[x][y]=255-it”) </em>and returned the image “img”.</p><p>And that’s it we have the script, Now let&#39;s make some images.</p><pre>n=1000<br>img = plotter(n, thresh=4, max_steps=50)<br>plt.imshow(img, cmap=&quot;plasma&quot;)<br>plt.axis(&quot;off&quot;)<br>plt.show()</pre><p>The above code creates an image.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/640/1*7tXE2Hq2sWhqulBWJC7ZpQ.png" /></figure><p>For more pixels in image increase N, for more details increase max_steps and don’t change thresh value else you will be doing redundant work (why?).</p><p>Try changing the argument for color map (cmap) in plt.imshow method from <a href="https://matplotlib.org/3.1.0/tutorials/colors/colormaps.html">here</a>, to get different color effects.</p><h3><strong>References</strong></h3><p><a href="http://The beauty of complex numbers">The beauty of complex numbers</a> by Zack Start.</p><p><a href="https://mathworld.wolfram.com/MandelbrotSet.html">Mandelbrot Set</a>, Wolfram Alfa MathWorld.</p><p><a href="https://www.fractalus.com/kerry/articles/area/mandelbrot-area.html">A Statistical Investigation of the Area of the Mandelbrot Set</a>, fractalus.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=983e9fc47f56" width="1" height="1" alt=""><hr><p><a href="https://levelup.gitconnected.com/mandelbrot-set-with-python-983e9fc47f56">Mandelbrot Set with Python</a> was originally published in <a href="https://levelup.gitconnected.com/">Level Up Coding</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Search Technique on Graphs: Breadth-First Search]]></title>
            <link>https://medium.com/better-programming/search-technique-on-graphs-breadth-first-search-dab467f73ff8?source=rss-5ec37cc04460------2</link>
            <guid isPermaLink="false">https://medium.com/p/dab467f73ff8</guid>
            <category><![CDATA[artificial-intelligence]]></category>
            <category><![CDATA[python]]></category>
            <category><![CDATA[algorithms]]></category>
            <category><![CDATA[education]]></category>
            <category><![CDATA[programming]]></category>
            <dc:creator><![CDATA[Abdul Salam]]></dc:creator>
            <pubDate>Tue, 04 Feb 2020 16:16:06 GMT</pubDate>
            <atom:updated>2020-02-04T16:16:06.216Z</atom:updated>
            <content:encoded><![CDATA[<h4>Search far and wide</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*p4bHowcZgckG1dNjACgPWg.jpeg" /><figcaption>Image by <a href="https://www.pinterest.co.uk/brashash/">AnaSophia Eiseman</a></figcaption></figure><p><em>Breadth-first search</em> (BFS) is a common search technique on graphs. BFS is a companion of <em>depth-first search</em> (DFS). While DFS traverses the graph depth-wise, BFS does it breadth-wise. It’s used to find a node in a graph. It may also be used to get the path to that node from a given node or to just traverse all the nodes and edges in a graph.</p><h4>Why use BFS over DFS?</h4><p>Let’s say we want to find a node in a tree where we know in advance the tree is not bushy (higher diameter) and the node lies somewhere in the middle of the tree. Then we use BFS over DFS.</p><p>It’s generally used to find the shortest path to a node from some given node when the edges have no or the same weights on them.</p><p>All the <a href="https://github.com/abecus/DS-and-Algorithms/tree/master/graph">code used in this piece</a> can be found on GitHub.</p><h3>Breadth-First Search</h3><p>In the breadth-first search technique, we traverse the graph level by level. First, from a starting node, we store all its adjacent nodes. Then we explore the stored nodes and store all their adjacent nodes in such a manner that the nodes stored first will be explored first.</p><p>We’re maintaining the traversal of the graph in such a way that we’re exploring all the nodes of a level, and then the level below it, and so on.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/343/1*NfWwd4xZg28zmVWvIq1tNQ.png" /></figure><p>In the above graph, we want to go to all nodes from node 3 using BFS. Let’s say we’re on level 0 ( because our natural number starts with 0). We store the node 3 in a queue. (A queue is defined as a data structure that supports at least the removal of items from the front and the addition of items to the back or an appending operation in constant time, and is generally implemented using a doubly-linked list.) Now say our queue is [3].</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/343/1*dgI7khaiWnA1XY-dGXRu8w.png" /></figure><p>By popping items from the front of the queue, which is node 3, and traversing it, we go to its adjacent node 2 at level 1. Now we append node 2 in the queue [2].</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/343/1*8t0h_W3ujorvjspSTxOZCA.png" /></figure><p>Again we pop items from the front of the queue, which is node 2, and go to all adjacent nodes of node 2, namely 0 and 4 at level 2. Then we append these nodes to the queue [0,4].</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/343/1*G8V_IDUGTfPbBdxZyn0daA.png" /></figure><p>Again we pop items from the front of the queue, which are nodes 0 and 4. Then from node 0, we go to its adjacent node 6, append it to the queue, and the queue becomes [6]. We do the same for node 4’s adjacent nodes 5 and 1, and the queue becomes [6,5,1], which are at level 3. That’s how we traverse using the BFS technique in graphs.</p><h3>Let’s Code It</h3><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/3a4ffe8f04a50e43414f703bcfb5d645/href">https://medium.com/media/3a4ffe8f04a50e43414f703bcfb5d645/href</a></iframe><pre>from collections import deque <br>def bfs(G, start, end):<br>    ...</pre><p>In the first line, we’re importing Python’s built-in queue module. Then we’re creating a function bfs that takes arguments graph, start node, and end node.</p><pre>if start in Graph.graph:<br>    visited = set()        <br>    parent = {}        <br>    queue = deque([])    <br>    visited.add(start)        <br>    queue.append(start)<br>    ...</pre><p>In the second line, we’re checking whether the start node is in the graph. If it is, then we’re initializing the visited set to check whether a node has been visited before or not, there is a parent dictionary to work as parent pointer to recreate the path, and a queue to store the nodes at a level. After that, we’re inserting the start node in the visited set and in the queue.</p><pre>while queue:            <br>    ...</pre><p>Now we’re looping until the queue is empty.</p><pre>node = queue.popleft()<br>if node==end:                <br>    return backtrace(parent, start, end)  <br>visited.add(node)<br>...</pre><p>Now we pop the node from the front of the queue and check whether the node is the end node. If it is, then we call a function backtrace, which we use to recreate the path to the end node. If the node was not the end node, then we will add the node to the visited set.</p><pre>for child, _ in G.getAdjacentNodes(node):                <br>    if child not in visited:                    <br>        parent[child]=node                    <br>        queue.append(child)<br>...</pre><p>Now we loop through all the adjacent nodes of the node. If they have not been visited before, we’ll append them to the queue (i.e., add them to the end), and mark their parent as node<em> </em>in the parent dictionary.</p><pre>return f&quot;Path does not exists between the Nodes ({start} to {end})&quot;</pre><p>If the end node was not found or the start node is not in the graph, we return a message.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/b2f516c2126471cba876d98dd0a9df59/href">https://medium.com/media/b2f516c2126471cba876d98dd0a9df59/href</a></iframe><p>To recreate the path, we take the parent dictionary and loop using the end node until we find the start node. Along the way, we append the nodes we’re looping through in an array or list. In the last line, we return the reversed list because we were appending for the path from end to start node.</p><h3>Run the Code</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/343/1*NfWwd4xZg28zmVWvIq1tNQ.png" /></figure><pre>G=Graph()<br>G.add(3, [2])<br>G.add(2, [0,4])<br>G.add(0, [6,5])<br>G.add(4, [5,1])</pre><p>Create a graph as above, using <a href="https://github.com/abecus/DS-and-Algorithms/blob/master/graph/graph.py">Graph</a> class.</p><pre>print(bfs(G, 3, 5))<br># [3,2,0,5]</pre><p>Running the bfs function for 3 as the start node and 5 as the end node prints [3,2,0,5].</p><h3>Time Complexity</h3><p>Similar to DFS, BFS’s time complexity is O(V+E) because visiting every node once and checking whether the node has been visited takes constant time. Also, we have represented the graph using an adjacency list (using nested dictionaries and sets).</p><p>In the next piece, I’ll go through the topological sort algorithm.</p><h3>Resources</h3><p>You can find all the <a href="https://github.com/abecus/DS-and-Algorithms/tree/master/graph">code I’ve used above</a> on my GitHub.</p><p>Thanks for reading!</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=dab467f73ff8" width="1" height="1" alt=""><hr><p><a href="https://medium.com/better-programming/search-technique-on-graphs-breadth-first-search-dab467f73ff8">Search Technique on Graphs: Breadth-First Search</a> was originally published in <a href="https://betterprogramming.pub/">Better Programming</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Vanilla Search Technique on Graphs: Depth-First Search]]></title>
            <link>https://medium.com/swlh/vanilla-search-techniques-on-graphs-dfs-and-bfs-c5cff5d0937d?source=rss-5ec37cc04460------2</link>
            <guid isPermaLink="false">https://medium.com/p/c5cff5d0937d</guid>
            <category><![CDATA[python]]></category>
            <category><![CDATA[web-development]]></category>
            <category><![CDATA[development]]></category>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[graph]]></category>
            <dc:creator><![CDATA[Abdul Salam]]></dc:creator>
            <pubDate>Wed, 22 Jan 2020 19:09:55 GMT</pubDate>
            <atom:updated>2020-11-15T19:37:37.309Z</atom:updated>
            <content:encoded><![CDATA[<h3>Search Technique on Graphs: Depth-First Search</h3><h4>Dive into search</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*Sufk8bfmJcaFJz1e" /><figcaption>Photo by <a href="https://unsplash.com/@mitchel3uo?utm_source=medium&amp;utm_medium=referral">Mitchell Luo</a> on <a href="https://unsplash.com/?utm_source=medium&amp;utm_medium=referral">Unsplash</a></figcaption></figure><p>Depth-First Search (DFS) is a common search technique on graphs. It is used to find a node in a graph and may also be used to get the path to that node from a given node or to just traverse all the nodes and edges in a graph.</p><p>It can also be augmented to do many more interesting things such as finding connected components, strongly connected components, minimum spanning tree, cycles in graphs, topological sort, etc.</p><p>For a refresher and basic concepts on graphs visit my <a href="https://medium.com/better-programming/graph-theory-algorithms-simplified-9a6868cc222">previous post, <em>graph theory algorithms simplified</em></a>.</p><p><a href="https://medium.com/better-programming/graph-theory-algorithms-simplified-9a6868cc222">Graph Theory Algorithms “Simplified”</a></p><p>All the code used in this series can be found <a href="https://github.com/abecus/DS-and-Algorithms/tree/master/graph">on GitHub</a>.</p><h3><strong>Creating Graph Class</strong></h3><p>To implement the search algorithms on the graph we need to create a Graph class with some useful methods, such as to get all nodes of the graph, all edges of the graph, all the adjacent nodes of a given node, etc.</p><p>A class for creating graphs with useful methods can be found on my <a href="https://github.com/abecus/DS-and-Algorithms/blob/master/graph/graph.py">GitHub</a>.</p><p>In the above code (on GitHub), we are creating a graph class with methods add, addFromDict, addHeuristicFromDict, nodes, getAdjcentNodes, isEdgeBetweenNodes, edges, get weight, etc. Now, back to depth-first search.</p><h3><strong>Depth-First Search</strong></h3><p>In the depth-first search technique, we choose a start node, then we add all its adjacent nodes to a *stack and do the same to all its adjacent nodes until we find the goal node (the node we want to find).</p><p>Recursion uses the stacks for its internal function calls, so we will be using it and it is easy to implement and also it is more intuitive.</p><p>We call this technique <em>depth-first search</em> because we start exploring (recursive call to the same function) adjacent nodes of the original node immediately after they have been found.</p><p>Also, if we look at its execution on a tree, it looks like it first goes in a branch say left until all the left branches have been explored, then it goes to the right branch incrementally.</p><p><em>Stack: A stack is a data structure that at least supports adding data to its end and removing data from the end just like a stack of books where we take the upper-most book if we need or put another book on top of stack. If you still haven’t got it, think of it like a first-come-last-served service.</em></p><h3>Let’s Code It</h3><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/0a1528d0a3a0321d924376efe5b6ab65/href">https://medium.com/media/0a1528d0a3a0321d924376efe5b6ab65/href</a></iframe><p>In the above code, we are creating a function called dfs that takes arguments Graph, Start Node, End Node.</p><pre>if start==end:<br>  return end</pre><p>Then we are checking if the start node is the end node. If they are, we are returning the end node.</p><pre>visited = set() # keeps the visited nodes</pre><p>Creating a visited set<strong> </strong>to keep track of visited nodes.</p><pre>def helper(node, path):<br>  ...</pre><p>Now, we are creating a helper function<strong> </strong>which is the main function and passing the start node to it as its argument.</p><pre>if node == end: # found the end node<br>  return node</pre><pre>visited.add(node)  # add node to visited</pre><p>In the helper function<strong>,</strong> we are checking if the given node as an argument to the function is the end node. If it is, then we return the node and if it is not the end node, we are adding the node to the visited set.</p><pre>for child, _ in G.getAdjacentNodes(node):<br>  # looping through all node which are<br>  # connected by edges</pre><pre>    if child not in visited:<br>      # if nodes are not visited before explore it</pre><pre>      if helper(child, path)!=None:<br>        path.append(child)<br>        return path</pre><p>Now we call the same function with the node’s adjacent nodes if they have not been visited before. Since, at the beginning of the helper method, we made a return statement <em>if start==end: return end, </em>if the function returns from there, then in its *callback we will collect all the nodes in the recursion’s *call stack which led to the end node and returns the collected nodes.</p><p><em>Call Stack: In all programming languages, recursion internally uses a stack to keep the past data about tasks it was doing and when a task is done, it does other tasks of that stack by taking the next task from the top of the stack, if there are any tasks to do.</em></p><p><em>Callback: when the call stack pops its tasks the operation is called as callback of that recursion.</em></p><pre>if start in G.graph:<br>  path = helper(start, path)</pre><pre>if path != None:   # if path has been found return it<br>  return [*reversed(path+[start])]</pre><pre>return f&quot;Path does not exists between the Nodes ({start} to {end})&quot;</pre><p>The dfs function checks if the path (list of nodes) has returned from the helper function.</p><p>Then it adds the start node to it, reverses the entire path list, and returns it if the helper returns nothing or None, it gives a message showing <em>path does not exist between the given start and end nodes</em>.</p><h3>Run the Code</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/421/1*SP_b2xtHBXO31Nck_wVwxw.png" /><figcaption>An example graph. Image from <a href="https://www.youtube.com/channel/UCD8yeTczadqdARzQUp29PJw">William Fiset</a></figcaption></figure><p>Creating a graph as given above.</p><pre>G = Graph()<br>G.add(&quot;a&quot;, [&#39;d&#39;], edgeType=1)<br>G.add(&quot;d&quot;, [&#39;h&#39;, &#39;g&#39;], edgeType=1)<br>G.add(&quot;h&quot;, [&#39;j&#39;, &#39;i&#39;], edgeType=1)<br>G.add(&quot;g&quot;, [&#39;i&#39;], edgeType=1)<br>G.add(&quot;i&quot;, [&#39;l&#39;], edgeType=1)<br>G.add(&quot;j&quot;, [&#39;i&#39;, &#39;m&#39;], edgeType=1)<br>G.add(&quot;j&quot;, [&#39;i&#39;, &#39;m&#39;], edgeType=1)<br>G.add(&quot;c&quot;, [&#39;a&#39;, &#39;b&#39;], edgeType=1)<br>G.add(&quot;b&quot;, [&#39;d&#39;], edgeType=1)<br>G.add(&quot;e&quot;, [&#39;d&#39;, &#39;a&#39;, &#39;f&#39;], edgeType=1)<br>G.add(&quot;f&quot;, [&#39;j&#39;, &#39;k&#39;], edgeType=1)<br>G.add(&quot;f&quot;, [&#39;j&#39;, &#39;k&#39;], edgeType=1)<br>G.add(&quot;k&quot;, [&#39;j&#39;], edgeType=1)</pre><p>Here the edgeType=1 indicating a directional edge and we can put 0 there for undirectional edges.</p><pre>&gt;&gt;&gt; print(dfs(G, “a”, “m”))<br>[&#39;a&#39;, &#39;d&#39;, &#39;h&#39;, &#39;j&#39;, &#39;m&#39;]</pre><p>Now, after calling the function on graph G from node “A” to node “M”, and printing it, it prints a path (list of nodes) which we can confirm from the image.</p><h3>Time Complexity</h3><p>Since we are calling the dfs function on all edges going out from the start node and then doing the same on its adjacent nodes, in the worst case, the program may go to all the nodes of the graph which is “N” (number of nodes in the graph).</p><p>And also to all the edges (while using the getAdjcentNodes method) of each node, “E” (number of edges in Graph), but we are calling each node once (by keeping track of visited nodes) thus rather than O(V*E), the algorithms get its time complexity of O(V+E).</p><p>We used a <em>visited</em> set to keep track of visited nodes in the graph, but if we already knew whether that graph is a tree, then we don’t need to use the visited node because, by definition, in a tree, there is only one path to a node from any other node.</p><p>In graph algorithms, the time complexity of them highly depends upon the graph representation techniques we use.</p><p>For example, if I were to use the adjacency matrix above to represent that graph, then the dfs function would have time complexity of O(V²) because, for each node, we would have to traverse an entire row of length V in the matrix to discover all its outgoing edges.</p><p>In the next post, I will go through the <a href="https://medium.com/better-programming/search-technique-on-graphs-breadth-first-search-dab467f73ff8">breadth-first search</a> technique.</p><p><a href="https://medium.com/better-programming/search-technique-on-graphs-breadth-first-search-dab467f73ff8">Search Technique on Graphs: Breadth-First Search</a></p><h3><strong>Resources</strong></h3><ul><li>For the code above, visit my <a href="https://github.com/abecus/DS-and-Algorithms/tree/master/graph">GitHub</a>.</li></ul><p>Thanks for reading!</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=c5cff5d0937d" width="1" height="1" alt=""><hr><p><a href="https://medium.com/swlh/vanilla-search-techniques-on-graphs-dfs-and-bfs-c5cff5d0937d">Vanilla Search Technique on Graphs: Depth-First Search</a> was originally published in <a href="https://medium.com/swlh">The Startup</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Graph Theory Algorithms “Simplified”]]></title>
            <link>https://medium.com/better-programming/graph-theory-algorithms-simplified-9a6868cc222?source=rss-5ec37cc04460------2</link>
            <guid isPermaLink="false">https://medium.com/p/9a6868cc222</guid>
            <category><![CDATA[computer-science]]></category>
            <category><![CDATA[algorithms]]></category>
            <category><![CDATA[python]]></category>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[graph-theory]]></category>
            <dc:creator><![CDATA[Abdul Salam]]></dc:creator>
            <pubDate>Mon, 20 Jan 2020 18:29:34 GMT</pubDate>
            <atom:updated>2020-12-10T13:15:24.430Z</atom:updated>
            <content:encoded><![CDATA[<h4>Graph theory 101</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*3wUddlYo5oG7r_qpuxs55g.png" /><figcaption>The City of Königsberg, <a href="http://visualhistory.livejournal.com/39249.html">Historic Cities Research Project</a></figcaption></figure><p>Graph theory is a very broad branch of mathematics and it is highly applicable in real-world problems. Originally, graph theory was “invented” to solve real-world problems and after that, it was hijacked by abstract mathematicians like all other branches of mathematics.</p><p>In this tutorial and subsequent tutorials, we will look at some graph theory algorithms and their implementations in Python. Now, back to the meat of the subject.</p><h3><strong>What Is a Graph?</strong></h3><p>In a nutshell, a graph is a set of vertices/nodes and edges. If you are not comfortable with “set” replace it with collection.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/546/1*ovOhVpUg4IlecaOOec4tbg.png" /><figcaption>A simple graph showing connections among people. Image From <a href="https://www.youtube.com/channel/UCD8yeTczadqdARzQUp29PJw">William Fiset</a></figcaption></figure><h4><strong>What is vertice/node?</strong></h4><p>In the above graph, a vertice/node will be the person.</p><p>Vertices are fundamental units of a graph. It can represent almost any entity and generally it is represented as a circle.</p><h4><strong>What is an edge?</strong></h4><p>In the above graph, the lines connecting the people are edges.</p><p>A line or connection between the vertices is called an edge. It can represent any kind of relation between the vertices.</p><h3><strong>Types of Graph</strong></h3><h4><strong>Directed graph</strong></h4><p>A graph with edges that have direction on them is called a <em>directed graph</em>. It may be used to show relations to predecessors (arrow from parents to their child) or ancestors (arrow from children to their parents).</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/579/1*hGbDR_VDF3BcXcR-naX0mg.png" /><figcaption>A Directed Graph. Image From <a href="https://www.youtube.com/channel/UCD8yeTczadqdARzQUp29PJw">William Fiset</a></figcaption></figure><h4><strong>Undirected graph</strong></h4><p>A graph with edges without directions on them is called an undirected graph. It may be used to show a two-way road.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/557/1*gVKflN6oBKLMB4okGiTFgQ.png" /><figcaption>A Un-Directed Graph. Image From <a href="https://www.youtube.com/channel/UCD8yeTczadqdARzQUp29PJw">William Fiset</a></figcaption></figure><h4><strong>Weighted graph</strong></h4><p>A graph in which the edges have a number on them to represent the cost of a transaction, fair of a journey, the distance between cities, etc. It can have any type of edge.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/580/1*gaAV7-CBG3bN-oxeS30_4Q.png" /><figcaption>A Weighted Graph. Image From <a href="https://www.youtube.com/channel/UCD8yeTczadqdARzQUp29PJw">William Fiset</a></figcaption></figure><h4><strong>Tree</strong></h4><p>An undirected graph with no cycles in it is a <em>tree</em>. Here, cycle means that there is only one way to go to a node by following edges from a given other node.</p><p>A tree has all its nodes connected by an edge to some other node and has N nodes with N-1 edges.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/629/1*t_SebbH8wcT8nU7DKINogA.png" /><figcaption>Trees. Image From <a href="https://www.youtube.com/channel/UCD8yeTczadqdARzQUp29PJw">William Fiset</a></figcaption></figure><h3><strong>Representing Graphs</strong></h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/247/1*sEyS8PsyN3H7Vb19yF7bEg.png" /><figcaption>A Graph Example. Image From <a href="https://www.youtube.com/channel/UCD8yeTczadqdARzQUp29PJw">William Fiset</a></figcaption></figure><p>There are many ways to represent a graph, two of the most common ones are:</p><h4><strong>Adjacency matrix</strong></h4><p>Let’s say we have <em>N</em> nodes in a graph. We can represent it using a matrix with <em>N</em> rows and <em>N</em> columns where a row and column of that matrix will represent a node and entry in them represents a directed edge (with or without weight).</p><p>They form the node representing the row to the node representing the column. Generally, 0 or infinity is used to represent no edge between the nodes. In Python, the adjacency matrix can be represented as:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/15915db665f100c5fdde61a9b0873271/href">https://medium.com/media/15915db665f100c5fdde61a9b0873271/href</a></iframe><h4><strong>Adjacency list</strong></h4><p>Similarly, with graphs of <em>N</em> nodes, we can represent the graph using an adjacency list, where all edges of a node are kept in a list of tuples (node, weight). In python, it can be represented as:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/64488716c11e85855f96bdfc074bdd3c/href">https://medium.com/media/64488716c11e85855f96bdfc074bdd3c/href</a></iframe><h4><strong>Nested dictionary</strong></h4><p>I represent the graph using nested dictionaries (this is what I call it) and dictionaries with sets (if the node does not has any edge with weight).</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/4cf0c64d34af3fa040745b14feaf16b0/href">https://medium.com/media/4cf0c64d34af3fa040745b14feaf16b0/href</a></iframe><p>In the <a href="https://medium.com/swlh/vanilla-search-techniques-on-graphs-dfs-and-bfs-c5cff5d0937d">next post</a>, I will be posting the Python code for an elaborated graph class with different methods, and we will be using that to implement a <a href="https://medium.com/swlh/vanilla-search-techniques-on-graphs-dfs-and-bfs-c5cff5d0937d">depth-first search</a>.</p><p><a href="https://medium.com/swlh/vanilla-search-techniques-on-graphs-dfs-and-bfs-c5cff5d0937d">Vanilla Search Technique on Graphs: Depth-First Search</a></p><p>For further information see <a href="http://youtube.com/watch?v=09_LlHjoEiY">this video on YouTube</a> by freecodecamp, or for a much deeper dive, click <a href="http://math.tut.fi/~ruohonen/GT_English.pdf">here</a>.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=9a6868cc222" width="1" height="1" alt=""><hr><p><a href="https://medium.com/better-programming/graph-theory-algorithms-simplified-9a6868cc222">Graph Theory Algorithms “Simplified”</a> was originally published in <a href="https://betterprogramming.pub/">Better Programming</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
    </channel>
</rss>