<?xml version="1.0" encoding="UTF-8"?>
<rss version="2.0" xmlns:atom="http://www.w3.org/2005/Atom" xmlns:dc="http://purl.org/dc/elements/1.1/">
  <channel>
    <title>DEV Community: Pasquale Convertini</title>
    <description>The latest articles on DEV Community by Pasquale Convertini (@pasquale95).</description>
    <link>https://dev.to/pasquale95</link>
    <image>
      <url>https://media2.dev.to/dynamic/image/width=90,height=90,fit=cover,gravity=auto,format=auto/https:%2F%2Fdev-to-uploads.s3.amazonaws.com%2Fuploads%2Fuser%2Fprofile_image%2F804535%2Fbd53a882-9cf8-42a9-9ed9-5057e42eeddc.jpeg</url>
      <title>DEV Community: Pasquale Convertini</title>
      <link>https://dev.to/pasquale95</link>
    </image>
    <atom:link rel="self" type="application/rss+xml" href="https://dev.to/feed/pasquale95"/>
    <language>en</language>
    <item>
      <title>How to become a Brave Verified Creator</title>
      <dc:creator>Pasquale Convertini</dc:creator>
      <pubDate>Tue, 01 Feb 2022 08:09:35 +0000</pubDate>
      <link>https://dev.to/pasquale95/how-to-become-a-brave-verified-creator-4j43</link>
      <guid>https://dev.to/pasquale95/how-to-become-a-brave-verified-creator-4j43</guid>
      <description>&lt;h2&gt;
  
  
  Introduction
&lt;/h2&gt;

&lt;p&gt;Do you want to be able to receive tips from the people that read your content? Among the several options available today (e.g. Patreon or Ghost), there is a completely free option consisting in becoming a &lt;strong&gt;Brave Verified Creator&lt;/strong&gt; and offered by &lt;strong&gt;Brave&lt;/strong&gt;.&lt;/p&gt;

&lt;p&gt;&lt;a href="https://res.cloudinary.com/practicaldev/image/fetch/s--5Gvs7RsE--/c_limit%2Cf_auto%2Cfl_progressive%2Cq_auto%2Cw_880/https://cdn.hashnode.com/res/hashnode/image/upload/v1643619817360/SWrE6CnM5.png" class="article-body-image-wrapper"&gt;&lt;img src="https://res.cloudinary.com/practicaldev/image/fetch/s--5Gvs7RsE--/c_limit%2Cf_auto%2Cfl_progressive%2Cq_auto%2Cw_880/https://cdn.hashnode.com/res/hashnode/image/upload/v1643619817360/SWrE6CnM5.png" alt="brave-browser-logo.png" width="880" height="270"&gt;&lt;/a&gt;&lt;/p&gt;

&lt;h3&gt;
  
  
  What is Brave?
&lt;/h3&gt;

&lt;p&gt;Brave is a Chromium-based browser available on all platforms and that you can download &lt;a href="https://brave.com/download/"&gt;here&lt;/a&gt;. It is also completely open-source with its code pushed on this &lt;a href="https://github.com/brave/brave-browser"&gt;repository&lt;/a&gt;. The features offered by this browser are manifold and would require a dedicated post to analyse them all, but its raising popularity among the community is clearly due to its privacy-preserving shield. While you surf the internet and access websites you leave breadcrumbs in the form of events and triggers used for advertising and tracking purposes. &lt;/p&gt;

&lt;p&gt;&lt;a href="https://i.giphy.com/media/GFE5dagX3tKTqkRZg8/giphy.gif" class="article-body-image-wrapper"&gt;&lt;img src="https://i.giphy.com/media/GFE5dagX3tKTqkRZg8/giphy.gif" alt="Tracking breadcrumbs" width="360" height="360"&gt;&lt;/a&gt;&lt;/p&gt;

&lt;p&gt;Brave is able to block the majority of the ads and trackers automatically and natively, which means without the need of installing any external extension (as it would be required for other browsers). Therefore, if you're concerned about your privacy, Brave is surely a valid option to look at.&lt;/p&gt;

&lt;h3&gt;
  
  
  The Brave ecosystem
&lt;/h3&gt;

&lt;p&gt;Although Brave is able to block all ads on a page, its goal is not to kill advertising. On the contrary, it defines a new ecosystem where:&lt;/p&gt;

&lt;ul&gt;
&lt;li&gt;
&lt;strong&gt;users&lt;/strong&gt; have complete control of their privacy and are entrusted to choose if they want to receive ads and their quantity, earning revenues proportionally to the number of received ads;&lt;/li&gt;
&lt;li&gt;
&lt;strong&gt;publishers&lt;/strong&gt; earn revenues from ads (if they decide to activate them on their domain) and directly from user contributions;&lt;/li&gt;
&lt;li&gt;
&lt;strong&gt;advertisers&lt;/strong&gt; can run less intrusive and more effective ads without violating privacy.&lt;/li&gt;
&lt;/ul&gt;

&lt;p&gt;&lt;a href="https://res.cloudinary.com/practicaldev/image/fetch/s--wE7COSfJ--/c_limit%2Cf_auto%2Cfl_progressive%2Cq_auto%2Cw_880/https://cdn.hashnode.com/res/hashnode/image/upload/v1643620536449/ttMQP-HIt.png" class="article-body-image-wrapper"&gt;&lt;img src="https://res.cloudinary.com/practicaldev/image/fetch/s--wE7COSfJ--/c_limit%2Cf_auto%2Cfl_progressive%2Cq_auto%2Cw_880/https://cdn.hashnode.com/res/hashnode/image/upload/v1643620536449/ttMQP-HIt.png" alt="bat_logo.png" width="880" height="377"&gt;&lt;/a&gt;&lt;/p&gt;

&lt;p&gt;Using Brave as browser does not oblige the user to accept silently this ecosystem. Indeed the user can decide to completely shut down the Brave Shield or even turn it on just on specific websites. However, if the user decides to take part in this ecosystem, it will be rewarded receiving BAT.&lt;/p&gt;

&lt;h3&gt;
  
  
  What is a BAT?
&lt;/h3&gt;

&lt;p&gt;BAT is an acronym for &lt;em&gt;Basic Attention Token&lt;/em&gt; and indicates a blockchain-based token used as a currency inside Brave. Brave users receive BAT tokens proportionally to the number of ads they receive on the internal Brave wallet. &lt;/p&gt;

&lt;p&gt;&lt;a href="https://res.cloudinary.com/practicaldev/image/fetch/s--Z9YOuW1R--/c_limit%2Cf_auto%2Cfl_progressive%2Cq_auto%2Cw_880/https://cdn.hashnode.com/res/hashnode/image/upload/v1643627722095/YAkGsLnCC.png" class="article-body-image-wrapper"&gt;&lt;img src="https://res.cloudinary.com/practicaldev/image/fetch/s--Z9YOuW1R--/c_limit%2Cf_auto%2Cfl_progressive%2Cq_auto%2Cw_880/https://cdn.hashnode.com/res/hashnode/image/upload/v1643627722095/YAkGsLnCC.png" alt="bat_token.png" width="880" height="377"&gt;&lt;/a&gt;&lt;/p&gt;

&lt;p&gt;They can decide to transfer these tokens in other wallets, exchange them for fiat currencies or use them to reward the web content creators they like in the form of anonymous contributions.&lt;/p&gt;

&lt;h2&gt;
  
  
  Who is a Brave Verified Creator?
&lt;/h2&gt;

&lt;p&gt;If you are a web content creator and you own a channel (e.g. on YouTube) or a website registered at a specific domain and you want to be able to collect and claim BAT contributions from Brave users, then you must become a &lt;strong&gt;Brave Verified Creator&lt;/strong&gt;, meaning a publisher able to demonstrate that he controls the channel/website to verify.&lt;/p&gt;

&lt;p&gt;A Brave Verified Creator is automatically linked with a BAT wallet where Brave converges all the received payments for the channels belonging to the creator. The creator can link the wallet to an Uphold or Gemini account in order to exchange BAT for other tokens or currencies.&lt;/p&gt;

&lt;h2&gt;
  
  
  How to become a Brave Verified Creator
&lt;/h2&gt;

&lt;p&gt;To get the badge of a Brave Verified Creator, you must be able to prove you actually own the "channel" where you post your content. The channel can be:&lt;/p&gt;

&lt;ul&gt;
&lt;li&gt;a website (as a blog);&lt;/li&gt;
&lt;li&gt;a GitHub repository;&lt;/li&gt;
&lt;li&gt;a YouTube channel;&lt;/li&gt;
&lt;li&gt;a Twitch channel;&lt;/li&gt;
&lt;li&gt;a Vimeo channel;&lt;/li&gt;
&lt;li&gt;a Twitter account;&lt;/li&gt;
&lt;li&gt;a Reddit account.&lt;/li&gt;
&lt;/ul&gt;

&lt;p&gt;&lt;a href="https://res.cloudinary.com/practicaldev/image/fetch/s---j3u73nB--/c_limit%2Cf_auto%2Cfl_progressive%2Cq_auto%2Cw_880/https://cdn.hashnode.com/res/hashnode/image/upload/v1643477282226/NkeZs6r1n.png" class="article-body-image-wrapper"&gt;&lt;img src="https://res.cloudinary.com/practicaldev/image/fetch/s---j3u73nB--/c_limit%2Cf_auto%2Cfl_progressive%2Cq_auto%2Cw_880/https://cdn.hashnode.com/res/hashnode/image/upload/v1643477282226/NkeZs6r1n.png" alt="brave_creators_channels.png" width="880" height="896"&gt;&lt;/a&gt;&lt;/p&gt;

&lt;p&gt;Brave can update the list of supported channels, thus it is recommended to check the list of the current supported ones directly in your "Creator" homepage.&lt;/p&gt;

&lt;h3&gt;
  
  
  Sign up
&lt;/h3&gt;

&lt;p&gt;First thing to do is create an account on the &lt;a href="https://creators.brave.com/sign-up"&gt;Creators Brave&lt;/a&gt; website by inserting your email.&lt;/p&gt;

&lt;p&gt;&lt;a href="https://res.cloudinary.com/practicaldev/image/fetch/s--3kNJ_DXZ--/c_limit%2Cf_auto%2Cfl_progressive%2Cq_auto%2Cw_880/https://cdn.hashnode.com/res/hashnode/image/upload/v1643477652459/rH_QuV04I.png" class="article-body-image-wrapper"&gt;&lt;img src="https://res.cloudinary.com/practicaldev/image/fetch/s--3kNJ_DXZ--/c_limit%2Cf_auto%2Cfl_progressive%2Cq_auto%2Cw_880/https://cdn.hashnode.com/res/hashnode/image/upload/v1643477652459/rH_QuV04I.png" alt="Creators_Brave_sign_up.png" width="880" height="544"&gt;&lt;/a&gt;&lt;/p&gt;

&lt;p&gt;Once received the sign-up link in your mail inbox, click on it and proceed with the sign-up.&lt;/p&gt;

&lt;h3&gt;
  
  
  Add a channel
&lt;/h3&gt;

&lt;p&gt;After the sign-up, in your Creator homepage you need to click on "Add Channel" to add your channel and get the Brave Verified Creator badge. &lt;/p&gt;

&lt;p&gt;&lt;a href="https://res.cloudinary.com/practicaldev/image/fetch/s--hANMhbFx--/c_limit%2Cf_auto%2Cfl_progressive%2Cq_auto%2Cw_880/https://cdn.hashnode.com/res/hashnode/image/upload/v1643628974352/uol_ZO4I_.png" class="article-body-image-wrapper"&gt;&lt;img src="https://res.cloudinary.com/practicaldev/image/fetch/s--hANMhbFx--/c_limit%2Cf_auto%2Cfl_progressive%2Cq_auto%2Cw_880/https://cdn.hashnode.com/res/hashnode/image/upload/v1643628974352/uol_ZO4I_.png" alt="brave_creators_homepage.png" width="880" height="715"&gt;&lt;/a&gt;&lt;/p&gt;

&lt;p&gt;For &lt;strong&gt;account&lt;/strong&gt; and &lt;strong&gt;channel&lt;/strong&gt; options all you need to do is to verify you're the guy owning the credentials to log in. &lt;/p&gt;

&lt;p&gt;For the &lt;strong&gt;website&lt;/strong&gt; option the verification process is more tedious: you must be able to either edit a DNS record or be able to create a folder and upload a file on your hosting domain. If you can't do any of the two options you are not eligible to become a Brave Verified Creator.&lt;/p&gt;

&lt;h3&gt;
  
  
  Verify your website with a trusted file
&lt;/h3&gt;

&lt;p&gt;&lt;a href="https://res.cloudinary.com/practicaldev/image/fetch/s--C3JPno8R--/c_limit%2Cf_auto%2Cfl_progressive%2Cq_auto%2Cw_880/https://cdn.hashnode.com/res/hashnode/image/upload/v1643479408939/wtLTYT2kj.png" class="article-body-image-wrapper"&gt;&lt;img src="https://res.cloudinary.com/practicaldev/image/fetch/s--C3JPno8R--/c_limit%2Cf_auto%2Cfl_progressive%2Cq_auto%2Cw_880/https://cdn.hashnode.com/res/hashnode/image/upload/v1643479408939/wtLTYT2kj.png" alt="trusted_file_button.png" width="769" height="426"&gt;&lt;/a&gt;&lt;/p&gt;

&lt;p&gt;If you can access the filesystem of your hosting machine (e.g. a virtual machine hosted on AWS), you can use the option involving the creation of a trusted file. To do that, click on the option "I'll use a trusted file". Once clicked, you should be prompted with the content you need to write inside the file.&lt;/p&gt;

&lt;p&gt;On host side, you need to create a folder named &lt;code&gt;.well-known&lt;/code&gt; under your domain root folder and create a file called &lt;code&gt;brave-rewards-verification.txt&lt;/code&gt; inside the just created folder. Assuming your host machine is Linux-based, you should do something like:&lt;br&gt;
&lt;/p&gt;

&lt;div class="highlight js-code-highlight"&gt;
&lt;pre class="highlight plaintext"&gt;&lt;code&gt;$ cd $DOMAIN_ROOT_FOLDER
$ mkdir .well-known &amp;amp;&amp;amp; cd .well-known
$ touch brave-reward-verification.txt
&lt;/code&gt;&lt;/pre&gt;

&lt;/div&gt;



&lt;p&gt;Then you need to write inside the file &lt;code&gt;brave-rewards-verification.txt&lt;/code&gt; the content indicated in the webpage you landed, which has a format like the following:&lt;br&gt;
&lt;/p&gt;

&lt;div class="highlight js-code-highlight"&gt;
&lt;pre class="highlight plaintext"&gt;&lt;code&gt;This is a Brave Rewards publisher verification file.

Domain: test.com
Token: 31d19738f1b2192e6f87c739e1edf9b48344159ec47870dcce5c1611fd04e133
&lt;/code&gt;&lt;/pre&gt;

&lt;/div&gt;



&lt;p&gt;At this point, click on the &lt;strong&gt;Verify&lt;/strong&gt; button and your website should obtain the "Brave Verified Creator" badge.&lt;/p&gt;

&lt;h3&gt;
  
  
  Verify your website with a DNS record
&lt;/h3&gt;

&lt;p&gt;&lt;a href="https://res.cloudinary.com/practicaldev/image/fetch/s--REwuawSS--/c_limit%2Cf_auto%2Cfl_progressive%2Cq_auto%2Cw_880/https://cdn.hashnode.com/res/hashnode/image/upload/v1643628817360/w4WFOyJ8i.png" class="article-body-image-wrapper"&gt;&lt;img src="https://res.cloudinary.com/practicaldev/image/fetch/s--REwuawSS--/c_limit%2Cf_auto%2Cfl_progressive%2Cq_auto%2Cw_880/https://cdn.hashnode.com/res/hashnode/image/upload/v1643628817360/w4WFOyJ8i.png" alt="dns_record_button.png" width="792" height="496"&gt;&lt;/a&gt;&lt;/p&gt;

&lt;p&gt;If you cannot create the file on your website hosting machine, you can still complete the verification by adding a DNS &lt;strong&gt;TXT record&lt;/strong&gt; for your domain (a procedure similar to the one used for the domain verification in Google Search Console). The record TXT data looks like the following:&lt;br&gt;
&lt;/p&gt;

&lt;div class="highlight js-code-highlight"&gt;
&lt;pre class="highlight plaintext"&gt;&lt;code&gt;brave-ledger-verification=0e5e9be6d9a40ff3da74315f3ba41383a3a5f9ec0a83c2040b78eb77543ab3582721ea
&lt;/code&gt;&lt;/pre&gt;

&lt;/div&gt;



&lt;p&gt;The procedure to add a TXT record inside your DNS varies according to the web hosting provider you use, but the result should be the same: querying the DNS servers for a TXT record on the domain we want to verify should return us the inserted token. On Linux and macOS you can verify running the command &lt;code&gt;dig&lt;/code&gt;:&lt;br&gt;
&lt;/p&gt;

&lt;div class="highlight js-code-highlight"&gt;
&lt;pre class="highlight shell"&gt;&lt;code&gt;&lt;span class="nv"&gt;$ &lt;/span&gt;dig TXT &amp;lt;your_domain&amp;gt;
&lt;/code&gt;&lt;/pre&gt;

&lt;/div&gt;



&lt;p&gt;If you run on Windows, you can use instead &lt;code&gt;nslookup&lt;/code&gt;:&lt;br&gt;
&lt;/p&gt;

&lt;div class="highlight js-code-highlight"&gt;
&lt;pre class="highlight shell"&gt;&lt;code&gt;&lt;span class="nv"&gt;$ &lt;/span&gt;nslookup &lt;span class="nt"&gt;-q&lt;/span&gt;&lt;span class="o"&gt;=&lt;/span&gt;TXT &amp;lt;your_domain&amp;gt;
&lt;/code&gt;&lt;/pre&gt;

&lt;/div&gt;



&lt;p&gt;If you're not familiar with command-line tools, you can check if the record is propagating by using a service as &lt;a href="https://dnschecker.org/"&gt;DNSChecker&lt;/a&gt;.&lt;/p&gt;

&lt;p&gt;&lt;a href="https://res.cloudinary.com/practicaldev/image/fetch/s--aw91oquc--/c_limit%2Cf_auto%2Cfl_progressive%2Cq_auto%2Cw_880/https://cdn.hashnode.com/res/hashnode/image/upload/v1643483170286/h84MO07lP.png" class="article-body-image-wrapper"&gt;&lt;img src="https://res.cloudinary.com/practicaldev/image/fetch/s--aw91oquc--/c_limit%2Cf_auto%2Cfl_progressive%2Cq_auto%2Cw_880/https://cdn.hashnode.com/res/hashnode/image/upload/v1643483170286/h84MO07lP.png" alt="dns_check.png" width="518" height="122"&gt;&lt;/a&gt;&lt;/p&gt;

&lt;p&gt;Once you've added the record, the verification process is not as immediate as the one done by using the trusted file since it requires the propagation of the TXT record among the DNS servers. &lt;/p&gt;

&lt;p&gt;Anyway, once you see the record being propagated on the majority of the DNS servers, you can click on the "Verify" button and your website should obtain the "Brave Verified Creator" badge.&lt;/p&gt;

&lt;h3&gt;
  
  
  Double check the verification
&lt;/h3&gt;

&lt;p&gt;To double check whether your website has been verified, you can go to your website within the Brave browser and look at the BAT icon usually located at the right of the address bar. If your website has been verified, the icon should present the verification badge consisting in a check mark:&lt;/p&gt;

&lt;p&gt;&lt;a href="https://res.cloudinary.com/practicaldev/image/fetch/s--2EsIupt8--/c_limit%2Cf_auto%2Cfl_progressive%2Cq_auto%2Cw_880/https://cdn.hashnode.com/res/hashnode/image/upload/v1643484097755/044NV7QOG.png" class="article-body-image-wrapper"&gt;&lt;img src="https://res.cloudinary.com/practicaldev/image/fetch/s--2EsIupt8--/c_limit%2Cf_auto%2Cfl_progressive%2Cq_auto%2Cw_880/https://cdn.hashnode.com/res/hashnode/image/upload/v1643484097755/044NV7QOG.png" alt="verified_badge.png" width="439" height="32"&gt;&lt;/a&gt;&lt;/p&gt;

&lt;p&gt;If not present, it could be because the status has been not refreshed. To refresh, click on the BAT icon and then on "&lt;strong&gt;Refresh Status&lt;/strong&gt;" in the submenu that appears:&lt;/p&gt;

&lt;p&gt;&lt;a href="https://res.cloudinary.com/practicaldev/image/fetch/s--8Cxk4JW4--/c_limit%2Cf_auto%2Cfl_progressive%2Cq_auto%2Cw_880/https://cdn.hashnode.com/res/hashnode/image/upload/v1643483906042/INKLgaRrF.png" class="article-body-image-wrapper"&gt;&lt;img src="https://res.cloudinary.com/practicaldev/image/fetch/s--8Cxk4JW4--/c_limit%2Cf_auto%2Cfl_progressive%2Cq_auto%2Cw_880/https://cdn.hashnode.com/res/hashnode/image/upload/v1643483906042/INKLgaRrF.png" alt="refresh_status.png" width="365" height="84"&gt;&lt;/a&gt;&lt;/p&gt;

&lt;p&gt;The check mark should appear. If not, the cause is likely related to some issues in the verification process and the recommended option would be to perform it again.&lt;/p&gt;

&lt;h2&gt;
  
  
  Conclusion
&lt;/h2&gt;

&lt;p&gt;As a web content creator is important to provide good quality content and a great user experience, which is sometimes ruined by aggressive ads. Becoming a &lt;em&gt;Brave Verified Creator&lt;/em&gt; allows to give a better experience to the users without necessarily turn down the revenues from advertising. Stay tuned for the next post!&lt;/p&gt;

</description>
      <category>advice</category>
      <category>browsers</category>
      <category>privacy</category>
      <category>crypto</category>
    </item>
    <item>
      <title>Algorithms vs Heuristics</title>
      <dc:creator>Pasquale Convertini</dc:creator>
      <pubDate>Thu, 27 Jan 2022 10:54:44 +0000</pubDate>
      <link>https://dev.to/pasquale95/algorithms-vs-heuristics-58c</link>
      <guid>https://dev.to/pasquale95/algorithms-vs-heuristics-58c</guid>
      <description>&lt;h2&gt;
  
  
  Introduction
&lt;/h2&gt;

&lt;p&gt;Given a problem, finding a procedure which brings to the right solution can be a tough task. Programmers knows the feeling of believing to have solved a problem by writing down an algorithm, but then realize that it does not work perfectly in every situation, most likely because built focusing on a specific &lt;em&gt;scenario&lt;/em&gt; instead of looking at the general case.&lt;/p&gt;

&lt;p&gt;This is presumably true when working on &lt;strong&gt;optimization problems&lt;/strong&gt; where the goal is to find out the best possible solution to the given problem. An example of optimization problem is known as &lt;strong&gt;TSP&lt;/strong&gt;, acronym standing for &lt;em&gt;Travelling salesman problem&lt;/em&gt;, where you are given with a set of vertices and you must find the shortest path connecting them all by visiting each vertex just once. To make things clearer, let's image to have the following set of vertices:&lt;/p&gt;

&lt;p&gt;&lt;a href="https://res.cloudinary.com/practicaldev/image/fetch/s--FU8lqet6--/c_limit%2Cf_auto%2Cfl_progressive%2Cq_auto%2Cw_880/https://cdn.hashnode.com/res/hashnode/image/upload/v1643036904398/dAqwj-2a1.png" class="article-body-image-wrapper"&gt;&lt;img src="https://res.cloudinary.com/practicaldev/image/fetch/s--FU8lqet6--/c_limit%2Cf_auto%2Cfl_progressive%2Cq_auto%2Cw_880/https://cdn.hashnode.com/res/hashnode/image/upload/v1643036904398/dAqwj-2a1.png" alt="6.png" width="880" height="495"&gt;&lt;/a&gt;&lt;/p&gt;

&lt;p&gt;The scenario consists in the 4 vertices of a square. An approach could be to randomly choose a vertex as starting point and move to the nearest unvisited vertex. Once visited, remove the vertex from the set of unvisited vertices and repeat the approach until all vertices have been visited. At this point we connect with an edge the last visited vertex with the first one. In pseudocode it would be something like:&lt;/p&gt;

&lt;pre&gt;
Pick a random vertex v0 from the set of unvisited vertices V
v = v0
Mark v as visited and remove from V
Until V is not empty:
    Choose the point w as the nearest point to v
    Visit w and remove it from V
    v = w
Connect v with v0
&lt;/pre&gt;

&lt;p&gt;Following this approach, we would find the following solution to the previous defined scenario:&lt;/p&gt;

&lt;p&gt;&lt;a href="https://res.cloudinary.com/practicaldev/image/fetch/s--6hulMHQJ--/c_limit%2Cf_auto%2Cfl_progressive%2Cq_auto%2Cw_880/https://cdn.hashnode.com/res/hashnode/image/upload/v1643036913371/L1tNsOd2O.png" class="article-body-image-wrapper"&gt;&lt;img src="https://res.cloudinary.com/practicaldev/image/fetch/s--6hulMHQJ--/c_limit%2Cf_auto%2Cfl_progressive%2Cq_auto%2Cw_880/https://cdn.hashnode.com/res/hashnode/image/upload/v1643036913371/L1tNsOd2O.png" alt="3.png" width="880" height="495"&gt;&lt;/a&gt;&lt;/p&gt;

&lt;p&gt;where we defined the path &lt;code&gt;A-&amp;gt;B-&amp;gt;C-&amp;gt;D-&amp;gt;A&lt;/code&gt;. The solution is optimal and we could think that such approach is actually the right algorithm to solve the TSP problem. But let's apply the same approach to the following scenario where we pick the vertex &lt;strong&gt;A&lt;/strong&gt; as the starting vertex:&lt;/p&gt;

&lt;p&gt;&lt;a href="https://res.cloudinary.com/practicaldev/image/fetch/s--RBqMsbKo--/c_limit%2Cf_auto%2Cfl_progressive%2Cq_auto%2Cw_880/https://cdn.hashnode.com/res/hashnode/image/upload/v1643036922139/P0VYjC7wM.png" class="article-body-image-wrapper"&gt;&lt;img src="https://res.cloudinary.com/practicaldev/image/fetch/s--RBqMsbKo--/c_limit%2Cf_auto%2Cfl_progressive%2Cq_auto%2Cw_880/https://cdn.hashnode.com/res/hashnode/image/upload/v1643036922139/P0VYjC7wM.png" alt="1.png" width="880" height="124"&gt;&lt;/a&gt;&lt;/p&gt;

&lt;p&gt;As you can see, the solution is not optimal. You might argue that we could always choose the leftmost vertex as starting point instead of picking randomly, and it would work fine for both the scenarios depicted above. But what about the one below?&lt;/p&gt;

&lt;p&gt;&lt;a href="https://res.cloudinary.com/practicaldev/image/fetch/s--UND7oN5d--/c_limit%2Cf_auto%2Cfl_progressive%2Cq_auto%2Cw_880/https://cdn.hashnode.com/res/hashnode/image/upload/v1643036959467/h3AJm1DSx.png" class="article-body-image-wrapper"&gt;&lt;img src="https://res.cloudinary.com/practicaldev/image/fetch/s--UND7oN5d--/c_limit%2Cf_auto%2Cfl_progressive%2Cq_auto%2Cw_880/https://cdn.hashnode.com/res/hashnode/image/upload/v1643036959467/h3AJm1DSx.png" alt="4.png" width="880" height="495"&gt;&lt;/a&gt;&lt;/p&gt;

&lt;p&gt;As you can see, it is evident how the method is doomed to fail at some point. This procedure is indeed not an algorithm, but an &lt;strong&gt;heuristic&lt;/strong&gt;, known as &lt;em&gt;nearest neighbour heuristic&lt;/em&gt;. &lt;/p&gt;

&lt;h2&gt;
  
  
  What is an algorithm?
&lt;/h2&gt;

&lt;p&gt;To understand the difference between algorithms and heuristics we need to give some definitions. So, when can we consider a procedure eligible to be named "algorithm"?&lt;/p&gt;

&lt;blockquote&gt;
&lt;p&gt;An algorithm is a procedure with a finite number of steps that always produce a correct solution for a given problem.&lt;/p&gt;
&lt;/blockquote&gt;

&lt;p&gt;Let's break down this definition. First, an algorithm must bring to a solution in a &lt;strong&gt;limited number of steps&lt;/strong&gt;. The reason of this definition lies on the fact that algorithms must produce a solution on finite machines (e.g. computers) which have limited time and limited space. Think for example to the problem of defining π: would you choose between an algorithm which produces all the digits of π but never ends or would you pick one producing only the first 100 digits of π but ends after some milliseconds? I would go for the second option.&lt;/p&gt;

&lt;p&gt;&lt;a href="https://i.giphy.com/media/BmmfETghGOPrW/giphy.gif" class="article-body-image-wrapper"&gt;&lt;img src="https://i.giphy.com/media/BmmfETghGOPrW/giphy.gif" alt="Computing_GIF" width="560" height="240"&gt;&lt;/a&gt;&lt;/p&gt;

&lt;p&gt;Second, an algorithm needs a &lt;strong&gt;proof of correctness&lt;/strong&gt;, which is a demonstration, based on a set of hypothesis, that a procedure cannot lead to an incorrect result for a given problem. They are usually defined in mathematical language and are very complex to make. We are not going in the details of demonstrating correctness, but you can have an example watching this video:&lt;/p&gt;

&lt;p&gt;&lt;iframe width="710" height="399" src="https://www.youtube.com/embed/SElE4RlAji0"&gt;
&lt;/iframe&gt;
&lt;/p&gt;

&lt;h2&gt;
  
  
  What is an heuristic?
&lt;/h2&gt;

&lt;p&gt;On the other side, an heuristic can be defined as follows:&lt;/p&gt;

&lt;blockquote&gt;
&lt;p&gt;An heuristic is a procedure for solving a problem without proof of correctness.&lt;/p&gt;
&lt;/blockquote&gt;

&lt;p&gt;Demonstrating incorrectness is easier than doing the inverse. It only requires to find a &lt;em&gt;counter-example&lt;/em&gt;: indeed nobody could claim for correctness after a counter-example has been found. If you look back at what we've done before, it's exactly the process of showing incorrectness.&lt;/p&gt;

&lt;p&gt;Does this mean that heuristics are wrong and useless? &lt;em&gt;Absolutely not&lt;/em&gt;. On the contrary they are widely used for finding an approximate solution to problems whose exact solution would be impossible to find for time or space constraints. The TSP problem is again a valid example: as a combinatorial NP-problem, its exact solution can only be found with a &lt;em&gt;brute-force search&lt;/em&gt; algorithm, which has an &lt;strong&gt;O(n!)&lt;/strong&gt; complexity.&lt;/p&gt;

&lt;h2&gt;
  
  
  How to find counter-examples
&lt;/h2&gt;

&lt;p&gt;Finding counter-examples is an essential skills for developers, as it speeds up the process of spotting weaknesses in the &lt;em&gt;design phase&lt;/em&gt; of an algorithm, which usually starts with the definition of a &lt;em&gt;greedy heuristic&lt;/em&gt; that is refined fail after fail until it starts looking more and more as an algorithm. This skill can be useful in many situations, from work to interviews. Thus, let me give some tips in the hunt for counter-examples:&lt;/p&gt;

&lt;ul&gt;
&lt;li&gt;&lt;p&gt;&lt;em&gt;Hack the greedy rules&lt;/em&gt;: greedy heuristics are usually based on some basic choices to move from a state to the next until a solution has been found. These choices often give a good starting point for our hunt, thus we could focus on them to find a valid counter-example. Think at the rule &lt;em&gt;"...always take the leftmost..."&lt;/em&gt; proposed in the TSP heuristic and at the proposed counter-example;&lt;/p&gt;&lt;/li&gt;
&lt;li&gt;&lt;p&gt;&lt;em&gt;Go for a tie&lt;/em&gt;: greedy heuristics move forward chasing for differences. What if we present a scenario where there are no differences? The approach could fail and the just found counter-example would be useful to improve the procedure. In the case of the TSP heuristics based on the &lt;em&gt;"...always take the leftmost..."&lt;/em&gt; rule, we could for example present the following scenario where no point is on the left of the others:&lt;/p&gt;&lt;/li&gt;
&lt;/ul&gt;

&lt;p&gt;&lt;a href="https://res.cloudinary.com/practicaldev/image/fetch/s--0y_1khPb--/c_limit%2Cf_auto%2Cfl_progressive%2Cq_auto%2Cw_880/https://cdn.hashnode.com/res/hashnode/image/upload/v1643036974676/qmPB_dFOk.png" class="article-body-image-wrapper"&gt;&lt;img src="https://res.cloudinary.com/practicaldev/image/fetch/s--0y_1khPb--/c_limit%2Cf_auto%2Cfl_progressive%2Cq_auto%2Cw_880/https://cdn.hashnode.com/res/hashnode/image/upload/v1643036974676/qmPB_dFOk.png" alt="2.png" width="880" height="495"&gt;&lt;/a&gt;&lt;/p&gt;

&lt;ul&gt;
&lt;li&gt;
&lt;em&gt;Work on extremes&lt;/em&gt;: greedy heuristics can define bounds to pick the next move to perform. If so, there's a good chance that the counter-example we're seeking sits on the bound: what if we present a scenario where we reach this bound? Does the greedy approach handle it? Does it give a correct result?&lt;/li&gt;
&lt;/ul&gt;

&lt;h2&gt;
  
  
  Conclusion
&lt;/h2&gt;

&lt;p&gt;Algorithm design is a tedious refinement process which can require a lot of time. Improving the ability to spot algorithm weaknesses sharpens the intuition and allows to be faster, write better algorithms and be more productive.&lt;/p&gt;

&lt;p&gt;&lt;a href="https://i.giphy.com/media/PoImGf3Takz1BtpNSG/giphy.gif" class="article-body-image-wrapper"&gt;&lt;img src="https://i.giphy.com/media/PoImGf3Takz1BtpNSG/giphy.gif" alt="Thinking_GIF" width="700" height="700"&gt;&lt;/a&gt;&lt;/p&gt;

&lt;p&gt;In this post we depicted the difference between heuristics and algorithms, focusing on the process of spotting counter-examples to better distinguish between what is indeed an algorithm solving a problem and what is an heuristic solving just a specific instance of that problem. Stay tuned for the next post!&lt;/p&gt;




&lt;h2&gt;
  
  
  Sources
&lt;/h2&gt;

&lt;ul&gt;
&lt;li&gt;The Algorithm Design Manual (Skiena)&lt;/li&gt;
&lt;/ul&gt;

</description>
      <category>algorithms</category>
      <category>programming</category>
      <category>productivity</category>
      <category>computerscience</category>
    </item>
  </channel>
</rss>
