DEV Community: Avishek Patra

Kunth-Morris-Pratt(KMP) Algorithm For Pattern Searching

Avishek Patra — Thu, 19 Mar 2020 17:35:27 +0000

Introduction

Pattern searching is an important problem in computer science. When we do search for a string in notepad/word file or browser or database, pattern searching algorithms are used to show the search results. Here is the list of available algorithms available to for this Job

Read the whole article here

Kunth-Morris-Pratt(KMP) Algorithm For Pattern Searching | by Avishek Patra | Medium

Avishek Patra ・ Mar 19, 2020 ・ 7 min read
Medium

If you've liked this article then please follow me on twitter to encourage me to write more article like this.

Best way to get all prime numbers (Sieve of Eratosthenes)

Avishek Patra — Sun, 15 Mar 2020 16:00:22 +0000

Introduction

In almost every interviews, an optimized way of searching is a very common thing nowadays, especially when it comes to numbers it becomes more interesting. Today we will be discussing one of the most popular questions among the interviewers, finding all the prime numbers from a series of 0 to 1 million numbers. Looping through from 0 to 1 million number will definitely give you the desired outcome however in terms of performance and time complexity it will not perform good, so the catch is if this is not the ideal way of doing this then what will be the other option.

From the title, most of you have already guessed its something called "Sieve of Eratosthenes" well this is an ancient algorithm to eliminate all the prime numbers from a long series. Let's find out what does this algorithm says

Sieve of Eratosthenes

Wikipedia says "In mathematics, the Sieve of Eratosthenes is a simple and ingenious ancient algorithm for finding all prime numbers up to any given limit."

How does it do

It does so by iteratively marking as composite (i.e., not prime) the multiples of each prime, starting with the first prime number, 2. The multiples of a given prime are generated as a sequence of numbers starting from that prime, with a constant difference between them that is equal to that prime.[1] This is the sieve's key distinction from using trial division to sequentially test each candidate number for divisibility by each prime.

Algorithm & Implementation

The algorithm says the following

A prime number is a natural number that has exactly two distinct natural number divisors: the number 1 and itself.

To find all the prime numbers less than or equal to a given integer n by Eratosthenes' method:

Create a list of consecutive integers from 2 through n: (2, 3, 4, ..., n).
Initially, let p equal 2, the smallest prime number.
Enumerate the multiples of p by counting in increments of p from 2p to n, and mark them in the list (these will be 2p, 3p, 4p, ...; the p itself should not be marked).
Find the first number greater than p in the list that is not marked. If there was no such number, stop. Otherwise, let p now equal this new number (which is the next prime), and repeat from step 3.
When the algorithm terminates, the numbers remaining not marked in the list are all the primes below n.

See how cleverly it manage to find all the prime numbers in an efficient way. Now let's look at the implementation of the algorithm. We will be doing it by using javascript.

function GenerateSieve(max)
{
    // Creating an array indicating whether numbers are prime.
    const is_prime = new Array(max+1);

    for(let i=2; i<=max; i++)
    {
        is_prime[i]=true;
    }

    //Crossing out multiplies
    for(let i=2; i<=max; i++)
    {
        //Check if its prime
        if(is_prime[i])
        {
            //Eliminate the multiplies of i
            for(let j=i*2; j<=max; j+=i){
                is_prime[j]=false;
            }
        }
    }
    return is_prime;
}

Lets understand the code line by line

    // Creating an array indicating whether numbers are prime.
    const is_prime = new Array(max+1);

In the above snippet, you can see we are creating an array

   for(let i=2; i<=max; i++)
    {
        is_prime[i]=true;
    }

Through this loop, we are marking all the numbers in the array as a prime number, except 0,1 and 2 as we know already know about their prime and non-prime stands

0,1 being non-prime numbers and 2 being the smallest prime number, we have initialized the loop from 2 and mark all the numbers beyond that as prime numbers. So as of now, all the elements are prime numbers in the is_prime array.

    for(let i=2; i<=max; i++)
    {
        //Check if its prime
        if(is_prime[i])
        {
            //Eliminate the multiplies of i
            for(let j=i*2; j<=max; j+=i){
                is_prime[j]=false;
            }
        }
    }

Here in the first loop, we are iterating through each element starting from 2 and then in the second loop we are eliminating the composite numbers from the _is_prime array, so in forward we are already removing the composite numbers from the array so as a result the outer loop may run for nth number and inner loop will not run for that time as the following statement will stop it running

   if(is_prime[i])
   {
        ....
   }

Hope, the algorithm and its implementation now clear. The complete implementation of this algorithm can be found in both javascript and in c#

So if you've liked this article then please like it, this will give me confidence to write more article in future. Also if you want to get daily updates or resolve any of your doubts on your #100daysofcode program then feel free to DM me on twitter. My twitter handle is @avishekp86

Generics in Typescript

Avishek Patra — Sat, 14 Mar 2020 18:59:38 +0000

Introduction

A major part of software engineering is building components that not only have well-defined and consistent APIs but are also reusable. Components that are capable of working on the data of today, as well as the data of tomorrow, will give you the most flexible capabilities for building up large software systems.
In languages like C# and Java, one of the main ways for creating reusable components is generics, that is, being able to create a component that can work over a variety of types rather than a single one. This allows users to consume these components and use their own types.

Interested to know more? Read the complete article from here

How to Create Generics in Typescript | Medium

Avishek Patra ・ Mar 14, 2020 ・ 6 min read
Medium

If you want me to write the entire article on dev.to then please let me know via comments here or twitter. My twitter handle is https://twitter.com/avishekp86

Step by Step building a PWA in Angular 8

Avishek Patra — Fri, 06 Mar 2020 14:10:38 +0000

Creating a Progressive Web Application, the application which can be run as like a native app from the mobile devices and regular sites from a browser, using Angular 8, I have consumed a simple REST API and displayed the data in the landing page.

Read the detailed article here in medium

Step by Step building a PWA in Angular 8 | by Avishek Patra | Medium

Avishek Patra ・ Mar 6, 2020 ・ 11 min read
Medium

The source code is available on (GitHub)[https://github.com/patravishek/pwa-angular]

On completion of the tutorial, you should be able to build a similar application like shown below

If you love the tutorial please like or comment so more tutorial can bring afterwards.

Creating Extension for VS-Code

Avishek Patra — Wed, 26 Feb 2020 11:46:57 +0000

Originally posted on Medium.com. I am sharing the medium embedded link here, if you want me to repost the entire article on dev.to then let me know by the comments section.

Creating Extension for VS-Code. Almost all of us have used extensions… | by Avishek Patra | Medium

Avishek Patra ・ Mar 12, 2020 ・ 7 min read
Medium

Adding swagger through VSCode

Avishek Patra — Fri, 21 Feb 2020 11:18:42 +0000

API is the backbone of any website, now when you develop and API then documenting the API would be a very important part. Now manual documentation is good but interactive documentation with tests always better than the previous. So what if there are some tools that are already present which do your job almost automatically.

"Swagger"(https://swagger.io/) does this work very swiftly. It's an Open Source product, it takes care of the following areas of an API Project very swiftly

API Design
API Development
API Documentation
API Testing
API Mocking and Virtualization

It can be integrated with any of the languages that supports API development.

Today we’ll be going through the steps through which we can add swagger in our API Project.

We will see the implementation of the swagger on an AspNetCore API project using vs-code.

Now, let’s Open the .NET CLI or console and write the following command

dotnet new webapi

This will create a web API project without swagger added.

Directory Structure will look something like below since I'm using vs-code to develop the API the screenshot is showing the vs-code explorer window

Now let's follow the steps below to add swagger Nuget in our project.

Step 1: Add NuGet Package

Open the vs-code terminal and run the following command

dotnet add TodoApi.csproj package Swashbuckle.AspNetCore

Step 2: Add & Configure Swagger to Middleware

Now we have to modify the ConfigureServices Method

public void ConfigureServices(IServiceCollection services)
{
services.AddMvc();
services.AddSwaggerGen(c =>
{
c.SwaggerDoc("v1", new Info { Title = "My API", Version = "v1" });
});
}

Now add using Swashbuckle.AspNetCore.Swagger; so that compiler could know from where the reference of Info class should be taken.

Step 3: Letting the middleware know about the swagger UI and the endpoint information

Navigate to the configure method of Startup.cs and add the following code

app.UseSwagger();

// Enable middleware to serve swagger-ui (HTML, JS, CSS, etc.), specifying the Swagger JSON endpoint.

app.UseSwaggerUI(c =>
{
c.SwaggerEndpoint("/swagger/v1/swagger.json", "My API V1");
});

And we are done, so let's test our implementation, open the vs-code terminal again and then run the following command:

dotnet run

This should run the application, once it starts running we can see how swagger is managing the API documentation.

Open Chrome or any other browser of your choice and post the following URL

http://localhost:/swagger/

you should be using the port number on which your application has been started. Now on your browser you should see the swagger documentation like below

So simple right. If you've liked this tutorial then please follow me on twitter and dev.to