<?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 Kirill Klimushin on Medium]]></title>
        <description><![CDATA[Stories by Kirill Klimushin on Medium]]></description>
        <link>https://medium.com/@kirklimushin?source=rss-302c8c5e7f8e------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/1*_H8agF5hzM1xxZm89p2m6g.jpeg</url>
            <title>Stories by Kirill Klimushin on Medium</title>
            <link>https://medium.com/@kirklimushin?source=rss-302c8c5e7f8e------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Wed, 18 Nov 2026 04:32:40 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@kirklimushin/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[The only 1 thing to know for interpreting almost any CNN-based model.]]></title>
            <link>https://medium.com/@kirklimushin/the-only-1-thing-to-know-for-interpreting-any-cnn-based-model-1d295bc9bb0b?source=rss-302c8c5e7f8e------2</link>
            <guid isPermaLink="false">https://medium.com/p/1d295bc9bb0b</guid>
            <category><![CDATA[convolutional-network]]></category>
            <category><![CDATA[interpretability]]></category>
            <category><![CDATA[deep-learning]]></category>
            <category><![CDATA[explainable-ai]]></category>
            <category><![CDATA[computer-vision]]></category>
            <dc:creator><![CDATA[Kirill Klimushin]]></dc:creator>
            <pubDate>Sat, 10 Feb 2024 13:11:00 GMT</pubDate>
            <atom:updated>2024-03-06T09:42:29.206Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="- upsplash.com -" src="https://cdn-images-1.medium.com/max/1024/1*lmA3K_FYQLkseAdyi_qIrA.jpeg" /><figcaption><a href="https://pixabay.com/photos/christmas-gift-christmas-tree-3485296/">Christmas gift</a> by AlexKlen. Pixabay</figcaption></figure><p>In the modern world of Computer Vision, necessity of having transparent model gradually escalates. As solutions become more complex and start to encompass larger audience, they still need to remain trustable by its users.</p><p>It encourages researchers to spend considerable portion of their time working on new algorithms for explaining model’s motives.</p><p>Unfortunately, the vast majority of them possess noticeable disadvantages and are tight to a specific problem domain, due to architectural constraints, speed of execution or quality of explanations, forcing Data Scientists and ML Engineers to use them in conjunction.</p><p>Leveraging all possible techniques to fill performance gaps is generally not practical, difficult to maintain and slows down development process.</p><h4>The solution:</h4><p>Is there a way, we could interpret large family of CNN-based networks using single approach? Luckily, back in 2016, researchers from Georgia Institute of Technology proposed a new ground breaking idea, which does exactly that and will serve as a main target of today’s talk. It’s name is “Grad-CAM” or “Gradient Class Activation Mapping”.</p><h3>Gradient Class Activation Mapping (Grad-CAM)</h3><p>This technique provide insights into regions of the input image were deemed important by the convolutional neural network for predicting a particular class. Essentially, it generates heat maps that highlight the importance of feature regions.</p><p>When we look at the cat, we subconsciously understand that it’s “cat”, by looking at the presence of core features, such as “cute sharp ears”, “colourful wool”, etc.</p><p>Grad-CAM gives us an opportunity to observe the same behaviour, but through the prism of CNN “eyes”, to understand how it thinks.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*_vKOYtLnpejL9lSmvjKVIA.png" /><figcaption>Figure 2. — Grad CAM output for “dog” class. The importance of features is represented as a gradient, flowing from blue to red. (<strong>blue</strong> is the background, while <strong>red</strong> indicates the highest priority feature, which heavily impacts model’s final decision). Logically, Fig.3 shows output for “cat” class. <a href="https://arxiv.org/pdf/1610.02391.pdf">Source</a></figcaption></figure><p>One of the main advantages of this algorithm lies in its simplicity. After looking at generated heat map diagram we can make our own judgements on how properly model understands the context of the image to predict the desirable class.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*kLw9dv1OEVZpYuEiD_HIpQ.png" /><figcaption>As you see, network thinks the waterfall belongs to “waterfall” class, because the presence of “water” feature. Same strategy applies to the rest of images. <a href="https://arxiv.org/pdf/1610.02391.pdf">Source</a></figcaption></figure><blockquote>If Grad-CAM heat maps does not mark the right features, it can be a sign, that your network has poor predictive power and might be either under or over fitted.</blockquote><h3><strong>How Grad CAM works technically?</strong></h3><p>Grad-CAM heavily relies on the concept of <a href="https://blog.mlreview.com/a-guide-to-receptive-field-arithmetic-for-convolutional-neural-networks-e0f514068807">Receptive Fields</a>, which is exceptional to CNN-based neural nets. Briefly, as we go further through the convolutional layers of the model, we manage to capture more and more complex features, starting from small patterns, like “edges”, “corners” and “lines” to gradually recovering depicted objects.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/850/1*N_8Izl-f8USiqvuzTfGpbA.png" /><figcaption>Overview of how CNN finds features on the image. Stages stand for “CNN layers”. <a href="https://arxiv.org/pdf/1610.02391.pdf">Source</a></figcaption></figure><p>Grad-CAM leverage this rule and gather all activations from last CNN layer, as it contains the complete set of features, network was able detect.</p><p>Then, it combines these activations with corresponding gradient maps, obtained from the backward pass, to compute final heat map.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/927/1*JmMz6O-AvPuOEBba1Rajxg.png" /><figcaption>Visualization of how Grad-CAM computes heatmap. Wn is mathematical mean of nth gradient map, calculated during backward pass of the CNN. <a href="https://arxiv.org/pdf/1610.02391.pdf">Source</a></figcaption></figure><blockquote>Wn — mathematical mean of nth gradient map, calculated during backward propagation phase of the CNN.</blockquote><p>Mathematically, computational formula can be written as:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*R7Cpi-XuORGelytyBMJXvA.png" /><figcaption>Mathematical formula for computing Grad-CAM heat map.</figcaption></figure><p>Now, let’s implement Grad-CAM algorithm using vanilla NumPy and a small grain of PyTorch.</p><p>For the sake of simplicity, I will use pretrained ResNet-50 to classify dogs and cats.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/52107db0c1a6d5485cf4ae796e915e4b/href">https://medium.com/media/52107db0c1a6d5485cf4ae796e915e4b/href</a></iframe><p>Here, inside ‘compute_grad_cam’ we perform the following steps:</p><ol><li>Track forward and backward passes of last CNN Layer using PyTorch hooks to save activations and their respective gradients.</li><li>Compute Grad-CAM heat map using derived mathematical formula.</li></ol><p>3. Apply normalization procedure to heat map.</p><p>4. Resize generated heat map to MxN, where (MxN is the shape of the input image), so we can project heat regions onto the input image later.</p><p>Further, you can use “visualize_grad_cam_map” method to visualize the result.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/4dafe20e3975f4fc6a8a9cf31549896a/href">https://medium.com/media/4dafe20e3975f4fc6a8a9cf31549896a/href</a></iframe><p>After running above code, we finally get this:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*Qd_wUJG7IwiZ1A4YV7yBeQ.png" /></figure><p>References to articles and youtube videos, you may find helpful</p><ul><li><a href="https://blog.mlreview.com/a-guide-to-receptive-field-arithmetic-for-convolutional-neural-networks-e0f514068807">Receptive Fields in Convolutional Neural Networks</a></li><li><a href="https://github.com/jacobgil/pytorch-grad-cam">PyTorch Grad-CAM library with over 9K stars</a></li><li><a href="https://arxiv.org/abs/1610.02391">Grad-CAM: Visual Explanations from Deep Networks via Gradient-based Localization</a>.</li><li><a href="https://towardsdatascience.com/understand-your-algorithm-with-grad-cam-d3b62fce353">Understand your Algorithm with Grad-CAM | by Daniel Reiff</a></li><li><a href="https://ch.mathworks.com/help/deeplearning/ug/gradcam-explains-why.html">Grad-CAM Reveals the Why Behind Deep Learning …</a></li><li><a href="https://www.youtube.com/watch?v=6YZoZ9Vtez0">Implementing Grad-CAM algorithms using Keras</a> (English)</li><li><a href="https://www.youtube.com/watch?v=ltUhbgGgSjY">Implementing Grad-CAM algorithm using PyTorch</a> (Chinese)</li><li><a href="https://www.youtube.com/watch?v=VmbBnSv3otc">Explaining CNNS: Class Attribution Maps</a></li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=1d295bc9bb0b" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Best Practices for ML in Production. Folders Organization, Code Style & Conflicts Resolution.]]></title>
            <link>https://medium.com/@kirklimushin/best-practices-for-ml-in-production-folders-organization-code-style-conflicts-resolution-10494aefd2d7?source=rss-302c8c5e7f8e------2</link>
            <guid isPermaLink="false">https://medium.com/p/10494aefd2d7</guid>
            <category><![CDATA[best-practices]]></category>
            <category><![CDATA[machine-learning]]></category>
            <dc:creator><![CDATA[Kirill Klimushin]]></dc:creator>
            <pubDate>Sun, 23 Jul 2023 17:13:47 GMT</pubDate>
            <atom:updated>2023-07-23T17:13:47.862Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*QsIOj7NCeTk9v1-9te7jmQ.jpeg" /></figure><p>In the rapidly evolving world of Machine Learning, it’s easy to overlook one of the most crucial aspects of software development — how to keep your project reliable.</p><p>While groundbreaking algorithms and sophisticated models grab the headlines, neglecting established rules can lead to a maintenance nightmare, hamper collaboration, and hinder the overall success of ML projects.</p><p>In this article, we will delve into the essential best practices for keeping your project clean and stable in the realm of Machine Learning.</p><h3>Project Structure (how to organize folders)</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/923/1*KjTxvuSuQyMFJLIxaMZm1w.jpeg" /></figure><p>Neglecting project structure can lead to big support issues. Make sure to keep in mind <strong>following tips</strong>:</p><ol><li><strong>Keep your data separated</strong>! Arrange your data across several directories for raw and preprocessed data. It’s important for reproducibility of your experiment.</li><li><strong>Store main functionality inside src file path</strong>. Everything related to Modeling, Preprocessing, Feature Engineering and Visualization should be there.</li><li>Have separated directory for your <strong>Notebooks and Experiments</strong>.</li><li><strong>Document and track Everything</strong>! I know it’s a boring task, but nowadays, especially in complex field of ML, having lack of details about conducted experiments just makes project impossible to maintain and improve in a long run.</li></ol><h3>Code Style (follow PEP8, maintain code clean)</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/800/1*YwvcdCHDwjFgVTV-26w1DA.jpeg" /></figure><h4><strong>1. Use Type annotations</strong></h4><p>It is generally a good practice to apply type annotations, as they allow you to track inputs of your methods and have clear expectations of the outputs.</p><h4>2. Use Autoformatters</h4><p>Autoformatters allows you to easily format your code according to PEP8. They help to make your code more readable and easier to understand. Common examples are <strong>AutoPEP8</strong> or <strong>Black </strong>formatters.</p><pre># example.py <br><br>import requests, json <br><br>def send_request(data: dict):<br>   response = requests.get(&quot;http://google.com&quot;, <br>   headers={&#39;Content-Type&#39;: &#39;application/json&#39;})<br>   return response.raw()</pre><pre>$ autopep8 example.py</pre><h4>3. Use Linters</h4><p>Linters allows you to scan your files to make sure your code follows specific style. You can even customize them, according to rules established on your team.</p><p>Common choices are: <strong>Flake8</strong> and <strong>PyLint.</strong></p><pre># example.py <br><br>import requests, json <br><br>def send_request(data: dict):<br><br>   response = requests.get(&quot;http://google.com&quot;, <br>   headers={&#39;Content-Type&#39;: &#39;application/json&#39;})<br>   return response.raw()</pre><pre>$ flake8 example.py</pre><pre>src/modeling/example.py:8:1: F401 &#39;numpy&#39; imported but unused<br>src/modeling/example.py:74:5: E303 too many blank lines (2)<br>src/modeling/example.py:103:1: W293 blank line contains whitespace<br>src/modeling/example.py:124:5: W292 no newline at end of file</pre><h3>Dependency management (don’t use standard pip)</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/800/1*c1IN5k-o87lmXwKqGdgdoQ.jpeg" /></figure><p>Standard <strong>pip</strong> manager does not have great flexibility in conflict resolution and is generally unreliable in production systems by their own. Highly recommend to try <strong>Poetry </strong>or<strong> Pipenv, </strong>as an additional dependency resolver<strong>. </strong>They are easy to setup and has mechanisms for separating development and production dependencies.</p><h3>Conclusion</h3><p>In this article, we briefly discussed some of the important practices you need to adapt to your ML project in order to keep it maintainable and reliable. Hope you enjoyed it. Don’t forget to hit the like button if you discovered something new.</p><p>Hope you have a great day ☕️</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=10494aefd2d7" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Power of Linked Lists. Why you need to learn them right now. # 3]]></title>
            <link>https://medium.com/@kirklimushin/power-of-linked-lists-why-you-need-to-learn-them-right-now-3-d39b2ecc920e?source=rss-302c8c5e7f8e------2</link>
            <guid isPermaLink="false">https://medium.com/p/d39b2ecc920e</guid>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[computer-science]]></category>
            <category><![CDATA[python]]></category>
            <category><![CDATA[python-programming]]></category>
            <category><![CDATA[data-structures]]></category>
            <dc:creator><![CDATA[Kirill Klimushin]]></dc:creator>
            <pubDate>Sat, 18 Mar 2023 16:19:41 GMT</pubDate>
            <atom:updated>2023-03-20T11:41:47.054Z</atom:updated>
            <content:encoded><![CDATA[<h3>Power of Linked Lists. Why you need to master this data structure # 3</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/1000/1*YooCNKLviBnVOo3hHjqRxg.jpeg" /></figure><p><strong>Linked List is one of the most essential and important data structures</strong>, that is highly popular and widely used in variety of real world projects.</p><p><strong>GPS Navigation</strong> in <strong>Google Maps</strong>, <strong>Music Player Queue</strong> in <strong>Spotify</strong>, History of visited websites in <strong>Google Chrome, </strong>almost everywhere<strong> </strong>in <strong>Windows Operating System</strong> and<strong> Git Version Control</strong>……</p><p>We can list it forever.</p><p>You know what?</p><p>Today I’m gonna teach you about<strong> What is Linked List, </strong>Why you need to know about this powerful data structure, and how you can effectively start using it for your own projects to become more experienced Software Engineer. Let’s get started!</p><h4><strong>Singly Linked List</strong></h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/869/1*7XXzAnt5fsEg930v6SFDWQ.png" /></figure><p>Let’s begin by breaking down the term of singly linked list. It is a <strong>list of the nodes</strong>, where <strong>every node do remember who goes after it</strong>. First node, knows, what node goes after it, third node knows what’s the next node after it, etc….</p><p>You cannot simply break this structure, and that’s why simple array operations like, <strong>insertion of new element</strong>, <strong>removal of the element</strong>, or <strong>search of the element</strong>, are relatively different and might look a bit complex to you.</p><p><strong>NEXT </strong>is just an attribute, that points to the next node of the array.</p><p><strong>HEAD </strong>is the current node we are on in Singly Linked List.</p><p><strong>Time Complexity</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/817/1*j_qpFBTun9Eclwx91zn_Lw.jpeg" /></figure><p><strong>Random Access </strong>in the Singly Linked List is <strong>O(n) , </strong>because nodes are not accessible by index, we are always starting out from the HEAD, and then moving to the bottom, which takes O(n) time.</p><p><strong>Insertion and Deletion</strong> <strong>at the Beginning</strong> is O(1), because initially we do have access to the first node in the Singly Linked List.</p><p><strong>Insertion and Deletion at the End</strong> is O(n), because, as I aforementioned, we do have access only to the first node initially, therefore we need to traverse to the end of Singly Linked List, until we will reach the last one, which takes O(n) time.</p><p><strong>Insertion or Deletion in Random Location </strong>is O(n), because we don’t know where the node is in the Singly Linked List, and we need to do traverse, until we’ll find it, which takes O(n) time.</p><p><strong>Important thing to mention about Linked List Node.</strong></p><blockquote>When you do return a linked list node, you don’t return just a single element, like you do in an ordinary array, you will also return all the nodes, that goes after this node, as it has a relationship by next pointer.</blockquote><blockquote>If you want to just return the <strong>Node A, then you need to break relationship with it’s next element, </strong>which is<strong> Node B, </strong>by setting <strong>A.nextNode </strong>to <strong>None.</strong></blockquote><figure><img alt="" src="https://cdn-images-1.medium.com/max/766/1*zBkC6V8SdIk7TrUQc-DeOg.png" /></figure><p><strong>Implementation of Singly Linked List in Python</strong></p><p>Down Below is the implementation of the <strong>Singly Linked List Node</strong>, <strong>Singly Linked List</strong> itself, and it’s <strong>basic operations</strong> like, reversing the list, inserting new element, removing the element and searching for the element.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*GOx5fwFcituu0q3okxXr2A.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*8WLXMknqSGQNHilSMqnO0g.png" /></figure><p><strong>Doubly Linked List</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/980/1*Um_6yCbhSQCoiAlNAPr02w.png" /></figure><p><strong>Doubly Linked List</strong> has more benefits in comparison to Singly Linked List, as it is optimized for traversing both directions, forward and backward, providing higher flexibility. You can even combine it with other data structures to reach better time complexity for your code.</p><p><strong>Key Difference from Singly Linked List</strong></p><ol><li>Unlike Singly Linked List, <strong>Doubly Linked List</strong> also have a pointer for previous node, which allows us to move backward.</li></ol><p>2. Has better time complexity.</p><p><strong>Time Complexity</strong></p><p>Time Complexity for Doubly Linked List is quite the same as for Singly Linked List, except it does have <strong>O(1)</strong> for deleting nodes. Pretty Impressive.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*ErO7a2WWZUo9l91E5BC-5A.png" /></figure><p><strong>Implementation of Doubly Linked List using Python</strong></p><p>Down Below is the python code for<strong> Doubly Linked List Node</strong> and <strong>Doubly Linked List</strong> itself.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*R-NEhwhNMCoWlrjaw_pUWQ.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*ESRPEcS2kPbmo4yZZI3XxQ.png" /></figure><p>Wahh, there is too much code! But once you get how it works the picture becomes brighter.</p><p>Highly recommend you to visit <a href="https://www.youtube.com/@BackToBackSWE"><strong>Back To Back SWE</strong></a>, <a href="https://www.youtube.com/@NeetCode"><strong>NeetCode</strong></a> channels<strong> </strong>on Youtube, and watch several videos about <strong>Linked List</strong> explanation. This guys made it ridiculously simple.</p><p><strong>Main Purpose and why it is important to master this DSA.</strong></p><p>Almost all low-level API’s in the world use Linked Lists, some of them indirectly, but now it became a fundamental thing every Software System cannot live without. Having a strong understanding of this concept will help you to get better at low-level design and have a better idea of how most of low-level mechanisms works under the hood.</p><p>Here are some problems to practice for both SLL and DLL.</p><p>For <strong>Singly Linked List</strong></p><ol><li><a href="https://leetcode.com/problems/reverse-linked-list/">Reverse Linked List</a> ~ [Easy]</li><li><a href="https://leetcode.com/problems/merge-two-sorted-lists/">Merge Two Sorted Lists</a> ~ [Easy]</li><li><a href="https://leetcode.com/problems/remove-nth-node-from-the-end-of-the-list">Remove N-th Node from the End Of The List</a> ~ [Easy]</li><li><a href="https://leetcode.com/problems/remove-duplicates-from-linked-list">Remove Duplicates from Linked List </a>~ [Easy]</li><li><a href="https://leetcode.com/problems/linked-list-cycle/">Linked List Cycle</a> ~ [Easy]</li><li><a href="https://leetcode.com/problems/rotate-list/">Rotate List</a> ~ [Medium]</li><li><a href="https://leetcode.com/problems/partition-list/">Partition List</a> ~ [Medium]</li><li><a href="https://leetcode.com/problems/swap-nodes-in-pairs/">Swap Nodes in Pairs</a> ~ [Medium]</li></ol><p>For <strong>Doubly Linked List</strong></p><ol><li><a href="https://leetcode.com/problems/lru-cache/">LRU Cache</a> ~ [Medium]</li><li><a href="https://leetcode.com/problems/lfu-cache/">LFU Cache</a> ~ [Hard]</li></ol><h4><strong>Conclusion</strong></h4><p>Today we’ve covered one of the most important data structures, where it is used, and why it is important for you as a software engineer to know about it.</p><p>If you’ve discovered something new, make sure to clap on this article and share with others.</p><p>In the next session, we will implement a <strong>Music Player Queue</strong> using <strong>Doubly Linked List</strong> and <strong>FastAPI Web Framework </strong>to<strong> </strong>try this DSA on the real world example.</p><p>Connect with me on<a href="https://www.linkedin.com/in/klimushin-kirill/"> LinkedIn</a>.</p><p>Have a great day :)</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=d39b2ecc920e" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[BFS vs DFS, Critical Difference.]]></title>
            <link>https://medium.com/@kirklimushin/bfs-vs-dfs-for-graphs-and-trees-whats-the-difference-9fc39ff8bf51?source=rss-302c8c5e7f8e------2</link>
            <guid isPermaLink="false">https://medium.com/p/9fc39ff8bf51</guid>
            <category><![CDATA[python]]></category>
            <category><![CDATA[algorithms]]></category>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[fb]]></category>
            <category><![CDATA[dfs]]></category>
            <dc:creator><![CDATA[Kirill Klimushin]]></dc:creator>
            <pubDate>Tue, 28 Feb 2023 11:54:41 GMT</pubDate>
            <atom:updated>2023-03-01T06:44:17.452Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/440/1*xSn4opAgKSk-DVXLAEnvOA.jpeg" /></figure><p>One of the most important and popular topics in DSA is <strong>Trees and Graphs.</strong> There are 2 general, proven techniques called, “<strong>Depth-First Search </strong>(<strong>DFS)</strong>” and “<strong>Breadth-First Search</strong> (<strong>BFS)</strong>”, that are widely used for these type of problems.</p><p>Understand the difference between these concepts, is crucial to effectively crack any Tree or Graph problem, especially on coding interviews.</p><p>In this article, I’m going to break down the difference between these 2 approaches, their pros and cons, including implementation in Python Programming Language.</p><p>Let’s create an example abstraction of the Tree, we’ll use for algorithms demonstration.</p><pre>import typing <br><br>class TreeNode(object):<br>  # Represents tree Node<br>  def __init__(self, value, leftChild=None, rightChild=None):<br>      self.value = value <br>      self.leftChild = leftChild<br>      self.rightChild = rightChild <br><br>class Tree(object):<br>  # Represents the tree<br>    def __init__(self, rootNode: TreeNode):<br>      self.rootNode = rootNode</pre><h4>Depth-First Search (DFS)</h4><blockquote><em>Algorithm for graph / tree traversal. The only catch here is, that, unlike trees, graphs may contain cycles (a node may be visited twice). To avoid processing a node more than once, use a boolean visited array.</em></blockquote><h4>Approach</h4><p>Walks through every node vertically from <strong>left to right</strong> at once.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/500/1*C4PNW6JKPrxGhNveGCOipA.gif" /></figure><h4>Implementation</h4><pre>root = TreeNode(value=1, leftChild=TreeNode(2), rightChild=TreeNode(3)<br>tree = Tree(rootNode=root) # creating tree<br><br>def dfs(rootNode):<br>  <br>  queue = [rootNode] <br>  while queue:<br><br>    currentNode = queue.pop() <br>    print(currentNode.value) # printing nodes to the console<br><br>    if currentNode.leftChild != None: <br>       queue.append(currentNode.leftChild) <br><br>    if currentNode.rightChild != None:<br>       queue.append(currentNode.rightChild)<br><br>dfs(tree.rootNode)</pre><p><strong>Pros</strong></p><ul><li>Tend to be less memory intensive, rather than<strong> BFS.</strong></li><li>More suitable for finding targets, which are away from source.</li></ul><p><strong>Cons</strong></p><ul><li>There is the possibility that many states keep re-occurring, and there is no guarantee of finding the solution.</li><li>DFS algorithm goes for deep down searching and sometime it may go to the infinite loop.</li></ul><p><strong>DFS Problems to practice</strong></p><p>Here is the <a href="https://leetcode.com/tag/depth-first-search/">link</a> to a list of DFS Problems, I highly recommend to solve, to get better understanding of how it works.</p><h4>Breadth-First Search (BFS)</h4><blockquote><em>Algorithm, similar to </em><strong><em>DFS</em></strong><em>. It starts at the tree’s root or graph and searches/visits all nodes at the current depth level before moving on to the nodes at the next depth level. Is typically used for solving graph theory problems.</em></blockquote><h4>Approach</h4><p>Walks horizontally through <strong>all nodes on the same level</strong>, before going to the next level.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/880/1*RYZ4terOf0kbSJxMy0CEKg.gif" /></figure><h4>Implementation</h4><p>Step 1. Construct a Graph. It is required prerequisite, because default Tree structure does not support horizontal traversing.</p><pre>import collections <br><br>def constructGraph(rootNode):<br><br>   queue = [(rootNode, 1)]<br>   graph = collections.defaultdict(list) # same as dictionary<br><br>   while queue:<br><br>      currentRoot, depth = queue.pop()<br>      graph[depth].append(currentRoot) # adding node at level &quot;depth&quot;.<br><br>      if currentRoot.leftChild: # if left child node is not None, traversing it<br>         queue.append((currentRoot.leftChild, depth+1))<br><br>      if currentRoot.rightChild: # if right child node is not None, traversing it as well <br>         queue.append((currentRoot.rightChild, depth+1))<br>   return graph</pre><p>Done! The code above takes <strong>Tree Root Node</strong> as an input, and converts it into the object, where, every node lays in the stack, based on it’s depth level.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*2ljNU4-emq5_OZyDaYLqeg.png" /></figure><p>Step 2. <strong>BFS Algorithm</strong> Implementation.</p><pre>tree = Tree()<br>graph = constructGraph(tree) <br><br>def bfs(graph):<br><br>  # Breadth-First Search Algorithm Implementation<br><br>  queue = [1] # default depth level is &quot;1&quot;<br>  visitedNodes = [] # To avoid cycling, we need mark traversed nodes <br>  # as visited ones<br><br>  while queue:<br>    depth = queue.pop() <br>    <br>    for neighbor in graph[depth]:<br>        if not neighbor in visitedNodes:<br>            visitedNodes.append(neighbor) <br>            print(neighbor.value)<br><br>    queue.append(depth+1) # going down the tree<br><br>bfs(graph)</pre><p><strong>Pros</strong></p><ul><li>BFS tends to find paths with fewer steps than other algorithms, such as DFS.</li><li>BFS can be easily parallelized, which means that it can take advantage of multiple processors to speed up the search.</li></ul><p><strong>Cons</strong></p><ul><li>It can be very memory intensive since it needs to keep track of all the nodes in the search tree.</li><li>It can be slow since it expands all the nodes at each level before moving on to the next level.</li><li>It can sometimes find sub-optimal solutions since it doesn’t explore all possible paths through the search tree.</li></ul><p><strong>BFS Problems to Practice</strong></p><p>Here is the <a href="https://leetcode.com/tag/breadth-first-search/">link</a> to a list of BFS Problems to train.</p><h4>Conclusion</h4><p>Today we’ve covered several most important techniques for solving Trees and Graphs problems. I hope this article was useful, and you’ve learned something new. If so, highly recommend you to subscribe to my channel, and share this post with others.</p><p>Have a great day 🤘🏻</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=9fc39ff8bf51" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Data Structures in Python. Binary Tree #1]]></title>
            <link>https://medium.com/@kirklimushin/data-structures-in-python-binary-tree-1-862ab15d8366?source=rss-302c8c5e7f8e------2</link>
            <guid isPermaLink="false">https://medium.com/p/862ab15d8366</guid>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[algorithms]]></category>
            <category><![CDATA[binary-tree]]></category>
            <category><![CDATA[data-structures]]></category>
            <dc:creator><![CDATA[Kirill Klimushin]]></dc:creator>
            <pubDate>Sun, 26 Feb 2023 13:36:32 GMT</pubDate>
            <atom:updated>2023-02-27T14:16:55.679Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*n6lMQYZVaNTGJSfdC_VsbA.png" /></figure><h3>Binary Tree</h3><p>One of the most common and popular implementations of Data Structure called “Tree”. Is widely used in variety of real world systems.</p><p>There are more advanced “Tree” implementations: (AVL Tree, Binary Search Tree, Trie, Red-Black Tree, etc…), which has their own unique approaches for efficient organization and management of data.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*OG34xw_xq3iTsX-t6ai3LA.jpeg" /></figure><h4>How does Binary Tree look like?</h4><p>Binary Tree represents the collection of the nodes with the following structure:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*PzmZZhFdD-Z5Q6-_C9Co9w.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/682/1*JTcBw3xVL4vkiMGQt1UHrw.png" /></figure><p>Every node is the “parent” and can have at most 2 “child” nodes: left child node and right child node.</p><h4>Operations</h4><p>Binary Tree, including other “Tree” Implementations does support only 3 following operations:</p><ul><li>Lookup &amp; Traversing</li><li>Insertion</li><li>Deletion</li></ul><h4>Insertion</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/488/1*IgVKhvHHYc1Xx50bBW12Sg.gif" /></figure><p>Insertion of the new node in “Binary Tree” goes from left to right. For example: If there are 2 places available to insert new node, the priority goes to the one, which is closer to the left side.</p><h4>Traversing &amp; Lookup</h4><p>To traverse the Binary Tree you can use one of the 2 famous graph algorithms, depending on your problem:</p><ol><li><strong>DFS (Depth-First-Search) Algorithm</strong>.</li><li><strong>BFS (Breadth-First-Search) Algorithm</strong>.</li></ol><p>Additionally, you can use <strong>Preorder</strong>, <strong>Inorder</strong>, and <strong>Postorder</strong> <strong>Traversal Algorithms, </strong>if you need to traverse Binary Tree in a specific order<strong>.</strong></p><p>Comprehensive review on each of them you can find <a href="https://www.educative.io/blog/essential-tree-traversal-algorithms">here</a>.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*xP3GnQssdFyxJvG_tCnKfw.gif" /></figure><h4>Time Complexity</h4><p>Binary Tree is an essential implementation of “Tree” Data Structure, and time complexity completely depends on algorithm you’ve picked up.</p><p>For Example <strong>DFS &amp; BFS Algorithms</strong> takes <strong>O(v + m)</strong> time for every operations. Here is a diagram for better understanding.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/745/1*bjQ0mRm4BCK7lzHicJRoPg.png" /></figure><h4>Implementation</h4><p>Here is an example of how you can construct “Binary Tree” from the array or stack.</p><p>Important note to cover, before diving into code…</p><blockquote>Every Array[i] element have a left child at Array[2 * i + 1] and right child at Array[2 * i + 2]</blockquote><pre>class BinaryTreeNode(object):<br>  def __init__(self, value, leftChild=None, rightChild=None):<br>      self.value = value <br>      self.leftChild = leftChild<br>      self.rightChild = rightChild <br><br>class BinaryTree(object):<br>  <br>  def constructBinaryTree(self, arrayOfData, currentElementIndex, length):<br>      root = None <br>      if currentElementIndex &lt; length: <br>          root = BinaryTreeNode(value=arrayOfData[currentElementIndex])<br>          root.leftChild = self.constructBinaryTree(arrayOfData, 2 * currentElementIndex + 1, length) <br>          root.rightChild = self.constructBinaryTree(arrayOfData, 2 * currentElementIndex + 2, length)<br>      return root<br><br>  def traverse_tree_preorder(self, binaryTree, preOrder):<br>    if binaryTree:<br>        preOrder.append(binaryTree.value)<br>        self.traverse_tree_preorder(binaryTree.leftChild, preOrder)<br>        self.traverse_tree_preorder(binaryTree.rightChild, preOrder)<br>    return preOrder<br><br>  def traverse_tree_inorder(self, binaryTree, inOrder):<br>    if binaryTree:<br>      self.traverse_tree_inorder(binaryTree.leftChild, inOrder) <br>      inOrder.append(binaryTree.value)<br>      self.traverse_tree_inorder(binaryTree.rightChild, inOrder)<br>    return inOrder <br><br>  def traverse_tree_postorder(self, binaryTree, postOrder):<br>    if binaryTree:<br>      self.traverse_tree_postorder(binaryTree.leftChild, postOrder)<br>      self.traverse_tree_postorder(binaryTree.rightChild, postOrder)<br>      postOrder.append(binaryTree.value)<br>    return postOrder<br><br>newTree = BinaryTree() <br><br>preOrder = []<br>inOrder = [] <br>postOrder = []<br><br>testData = [1, 2, 5, 6, 3, 1, 9, 8, 10] <br>constructedTree = newTree.constructBinaryTree(testData, 0, len(testData))<br><br>print(&quot;pre-order&quot;, newTree.traverse_tree_preorder(binaryTree=constructedTree, preOrder=preOrder)) <br>print(&quot;in-order&quot;, newTree.traverse_tree_inorder(binaryTree=constructedTree, inOrder=inOrder))<br>print(&quot;post-order&quot;, newTree.traverse_tree_postorder(binaryTree=constructedTree, postOrder=postOrder))<br><br><br>      </pre><h4>Binary Tree Problems to practice (from leetcode.com)</h4><p><a href="https://leetcode.com/tag/tree/">Binary Tree Problems</a> I highly recommend to solve, to have a better understanding of this concept.</p><h3>Conclusion</h3><p>Today we’ve covered one of the “Tree” Data Structure Implementations called “Binary Tree”. It provides high flexibility for sorting and lookup data and can be useful, when it comes to deal with large dataset manipulation.</p><p>If you like the content or have any recommendations what to talk about in the next session, don’t forget to hit the like button, write a comment, and share this post with others. Your feedback helps me to make better content.</p><p>Also, if you’ve found some English typos or incorrect usage of some words, please, mention about it down in the comment section as well.</p><p>I’m only starting out writing technical posts in English and it’s important for me to make sure, that it’s high-quality and does not contain any language-related mistakes.</p><p>Also you can connect with me on <a href="https://www.linkedin.com/in/klimushin-kirill/">LinkedIn</a> as well.</p><p>Have a great day☕️🤘🏻</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=862ab15d8366" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>