Quick look into Machine Learning workflow

Before we jump into various ML concepts and algorithms, let’s have a quick look into basic workflow when we apply Machine Learning to a problem.

ml-header

A short brief about Machine Learning, it’s association with AI or Data Science world is here.

How does Machine Learning help?

Machine Learning is about having a training algorithm that helps predict an output based on the past data. This input data can keep on changing and accordingly the algorithm can fine tune to provide better output.

It has vast applications across. For example, Google is using it to predict natural disasters like floods. A very common use we hear these days in news are usage in Politics and how to attack the demography of voters.

How does Machine Learning work?

Data is the key here. More the data is, better the algorithm can learn and fine tune. For any problem output, there would be multiple factors at play. Some of them would have more affect then others. Analyzing and applying all such findings are part of a machine learning problem. Mathematically, ML converts a problem output as a function of multiple input factors.

Y = f(x)

Y = predicted output
x = multiple factors as an input

How does a typical ML workflow look?

There is a structured way to apply ML on a problem. I tried to put the workflow in a pictorial view to easily visualize and understand it:

ml-workflow

It’s goes in a cycle and once we have some insights from the published model, it goes back into the funnel as learning to make output better.

datascience-process

Roughly, Data scientists spend 60% of their time on cleaning and organizing data

Walk through an example?

Let’s use dataset of Titanic survivors found here and run through basic workflow to see how certain features like traveling class, sex, age and fare are helping us assess survival probability.

Load data from file

Data could be in various format. Easiest is to have it in a csv and then load it using pandas. More details around how to play with data is discussed here.
.

# lets load and see the info of the dataset

titanicdf = pd.read_csv("data-files/titanic.csv")
print(titanicdf.info())
<class 'pandas.core.frame.DataFrame'>
RangeIndex: 1309 entries, 0 to 1308
Data columns (total 14 columns):
 #   Column     Non-Null Count  Dtype  
---  ------     --------------  -----  
 0   pclass     1309 non-null   int64  
 1   survived   1309 non-null   int64  
 2   name       1309 non-null   object 
 3   sex        1309 non-null   object 
 4   age        1046 non-null   float64
 5   sibsp      1309 non-null   int64  
 6   parch      1309 non-null   int64  
 7   ticket     1309 non-null   object 
 8   fare       1308 non-null   float64
 9   cabin      295 non-null    object 
 10  embarked   1307 non-null   object 
 11  boat       486 non-null    object 
 12  body       121 non-null    float64
 13  home.dest  745 non-null    object 
dtypes: float64(3), int64(4), object(7)
memory usage: 143.3+ KB
None
# A quick sample view
titanicdf.head(3)
 pclasssurvivednamesexagesibspparchticketfarecabinembarkedboatbodyhome.dest
011Allen, Miss. Elisabeth Waltonfemale290024160211.3375B5S2NaNSt Louis, MO
111Allison, Master. Hudson Trevormale0.916712113781151.55C22 C26S11NaNMontreal, PQ / Chesterville, ON
210Allison, Miss. Helen Lorainefemale212113781151.55C22 C26SNaNNaNMontreal, PQ / Chesterville, ON
Data cleanup – Drop the irrelevant columns

It’s not always that the data captured is the only data you need. You will have a superset of data that has additional information which are not relevant for your problem statement. This data will work as a noise and thus it’s better to clean the dataset before starting to work on them for any ML algorithm.
.

# there seems to be handful of columns which 
# we might not need for our analysis 
# lets drop all those column that we know 
# are irrelevant
titanicdf.drop(['embarked','body','boat','name',
'cabin','home.dest','ticket', 'sibsp', 'parch'],
axis='columns', inplace=True)

titanicdf.head(2)
 pclasssurvivedsexagefare
011female29211.3375
111male0.9167151.55
Data analysis

There could be various ways to analyze data. Based on the problem statement, we would need to know the general trend of the data in discussion. Statistics Probability Distribution knowledge help here. For gaining insights to understand more around correlations and patterns, data visualization based insights help.
.

# let's see if there are any highly corelated data
# if we observe something, we will remove that 
# one of the feature to avoid bias

import seaborn as sns
sns.pairplot(titanicdf)

# looking at graphs, seems we don't have 
# anything right away to remove.
titanic-graph
Data transform – Ordinal/Nominal/Datatype, etc

In order to work through data, it’s easy to interpret once they are converted into numbers (from strings) if possible. This helps them input them into various statistics formulas to get more insights. More details on how to apply numerical modifications to data is discussed here.
.

# There seems to be 3 class of people, 
# lets represent class as numbers
# We don't have info of relative relation of 
# class so we will one-hot-encode it
titanicdf = pd.get_dummies(titanicdf,
                              columns=['pclass'])


# Lets Convert sex to a number 
from sklearn import preprocessing
le = preprocessing.LabelEncoder()
titanicdf["sex"] = le.fit_transform(titanicdf.sex) 

titanicdf.head(2)
 survivedsexagefarepclass_1pclass_2pclass_3
01029211.3375100
1110.9167151.55100
Data imputation: Fill the missing values

There are always some missing data or an outlier. Running algorithms with missing data could lead to inconsistent results or algorithm failure. Based on the context, we can choose to remove them or fill/replace them with an appropriate value.
.

# When we saw the info, lots of age were missing
# Missing ages values filled with mean age. 
 
titanicdf.loc[ titanicdf["age"].isnull(), "age" ] = 
titanicdf["age"].mean()

# titanicdf.loc[ titanicdf["fare"].isnull(), "fare"] 
# = titanicdf["fare"].mean() 
# => can do but we will use another way 

titanicdf.info()
<class 'pandas.core.frame.DataFrame'>
RangeIndex: 1309 entries, 0 to 1308
Data columns (total 7 columns):
 #   Column    Non-Null Count  Dtype  
---  ------    --------------  -----  
 0   survived  1309 non-null   int64  
 1   sex       1309 non-null   int64  
 2   age       1309 non-null   float64
 3   fare      1308 non-null   float64
 4   pclass_1  1309 non-null   uint8  
 5   pclass_2  1309 non-null   uint8  
 6   pclass_3  1309 non-null   uint8  
dtypes: float64(2), int64(2), uint8(3)
memory usage: 44.9 KB
# When we saw the info,
# 1 fare was missing
# Lets drop that one record
titanicdf.dropna(inplace=True)
titanicdf.info()

#<class 'pandas.core.frame.DataFrame'>
#Int64Index: 1308 entries, 0 to 1308
Normalize training data

At times, various data in context are of different scales. In such cases, if the data is not normalized, algorithm can induce bias towards the data that has higher magnitude. Eg, feature A value range is 0-10 and feature B range is 0-10000. In such case, even though a small change in magnitude of A can make a difference but if data is not normalized, feature B will influence results more (which could be not the actual case).
.

X = titanicdf
y = X['survived']
X = X.drop(['survived'], axis=1)

# Scales each column to have 0 mean and 1 std.dev
from sklearn import preprocessing
X_scaled = preprocessing.scale(X)
Split data – Train/Test dataset

It’s always best to split the dataset into two unequal parts. Bigger one to train the algorithm and then then smaller one to test the trained algorithm. This way, algorithm is not biased to just the input data and results for test data can provide better picture.
.

from sklearn.model_selection import train_test_split

X_train, X_test, y_train, y_test = 
                        train_test_split(X_scaled,y)
X_train.info()
<class 'pandas.core.frame.DataFrame'>
Int64Index: 981 entries, 545 to 864
Data columns (total 6 columns):
 #   Column    Non-Null Count  Dtype  
---  ------    --------------  -----  
 0   sex       981 non-null    int64  
 1   age       981 non-null    float64
 2   fare      981 non-null    float64
 3   pclass_1  981 non-null    uint8  
 4   pclass_2  981 non-null    uint8  
 5   pclass_3  981 non-null    uint8  
dtypes: float64(2), int64(1), uint8(3)
memory usage: 33.5 KB
Run ML algorithm data

Once we have our training dataset ready as per our need, we can apply machine learning algorithms and find which model fits in best.
.

# for now, picking any one of the classifier - KN
# Ignore details or syntax for now
from sklearn.neighbors import KNeighborsClassifier

dtc = KNeighborsClassifier(n_neighbors=5)
dtc.fit(X_train,y_train)
Check the accuracy of model

In order to validate the model, we use test dataset where comparing the predicted value by model to actual data helps us know about ML model accuracy.
.

import sklearn.metrics as met

pred_knc = dtc.predict(X_test)
print( "Nearest neighbors: %.3f" 
      % (met.accuracy_score(y_test, pred_knc)))
Nearest neighbors: 0.817


Voila! With basic workflow, we have a model that can predict the survivor with more than 80% probability.

Download

Entire Jupyter notebook with more samples can be downloaded or forked from my GitHub to look or play around: https://github.com/sandeep-mewara/machine-learning

Currently, it covers examples on following datasets:

  • Titanic Survivors
  • Sci-kit Iris
  • Sci-kit Digits
  • Bread Basket Bakery

Over time, I would continue building on the same repository with more samples with different algorithms.

Closure

Believe, now it’s pretty clear on how we can attack any problem for an insight using Machine learning. Try out and see for yourself.

We can apply Machine Learning to multiple problems in multiple fields. I have shared a pictorial view of sectors in the AI section that are already leveraging it’s benefit.


Keep learning!

samples GitHub Profile Readme
Learn Python – Beginners step by step – Basics and Examples
Sandeep Mewara Github
Sandeep Mewara Learn By Insight
Matplotlib plot samples
Sandeep Mewara Github Repositories
Learn Microsoft Tech via Videos LiveTV Streams
Machine Learning workflowMicrosoft .NET5

Microsoft AI support for COVID-19

In January 2020, Microsoft launched AI for Health program. Goal is to use Artificial Intelligence (AI) and data to help improve the health of people worldwide. Post COVID-19 hit world wide, Microsoft took steps to support & empower researchers, nonprofits and policymakers with resources.

ai-health

There have been more than 50 million confirmed cases of Covid-19 and more than 1.25 million deaths globally

World Health Organization

Research has accelerated with large-scale computing and open data.

Highlights from Grantees World wide

ai-health-covid-response
Credit: Microsoft

As shared here, few of them are:

  • A grassroots employee volunteer effort at Belgian biopharmaceutical company UCB.
  • UC Riverside researchers utilize quantum-based methods to more accurately predict the effectiveness of proposed Covid-19 inhibitors.
  • IHME, a global health research organization at the University of Washington School of Medicine, forecasts the Covid-19 pandemic.
  • Professor Amanda Randles at Duke University is conducting hundreds of millions of simulations required to help more patients have access to critical ventilators.

Partnership with Organizations

As shared here, few of them are:

  • Partnering with the White House Office of Science and Technology Policy’s (OSTP) High Performance Computing Consortium to support researchers and academia.
  • Working with Brown University’s School of Public Health and the Edmond J. Safra Center for Ethics at Harvard to visualize a common set of measures on testing and risk levels to help everyone know where we are with the pandemic and help policymakers guide their response.
  • Joining University of Oxford and their Government Response Tracker initiative to track and compare government and policy responses to address Covid-19 around the world.

The rapid progress means researchers can more quickly identify potential solutions to combat Covid-19 and provide timely information to policymakers for data-driven decisions that protect communities, cities and regions.

Microsoft blog

Public Information

Using publicly available information from partners, Microsoft have created:

  • a number of interactive visualizations to provide transparency into Covid-19 trends globally.
  • a unique measure called Progress to Zero to help everyone understand, progress in reducing Covid-19 cases, hospitalizations and deaths.
india-progress-to-zero

My Take

There are some great work being done world wide to fight Covid-19 in all possible ways. Organizations like Microsoft are making an active effort to help partners and grantees for Covid-19 response. There is much to do and supports like these will help mankind avert Pandemic.


Keep exploring!

Sandeep Mewara Github
News Update
Tech Explore
Data Explore
samples GitHub Profile Readme
Learn Machine Learning with Examples
Machine Learning workflow
What is Data Science
Word Ladder solution
What is Dynamic Programming
Learn Microsoft Tech via Videos LiveTV Streams Microsoft .NET5

Microsoft .NET 5 – all you need to know

As announced earlier, Microsoft released .NET 5 on Nov. 10 during .NET Conf 2020. It’s a major release with many new features and improvements to .NET Core 3. Keeping cross platform support and open source development as key base, going forward it kind of merges off .NET Framework and .NET Core.

dotnet-header

Plan

Microsoft started it’s journey of cross platform and open source in 2015. .NET 5 is a major milestone of this transition as .NET Framework 4.8 was the last major version of .NET Framework. Microsoft published a blog to explain how .NET 5 relates to .NET Framework.

.NET 5.0 is the main implementation of .NET going forward and .NET Framework 4.x is still supported.

dotnet-schedule
Source: Microsoft
dotnet-unified
Source: Microsoft

.NET 5 has been called as .NET Core vNext for quite some time now. It has following key principles:

– Produce a single .NET runtime and framework that can be used everywhere and that has uniform runtime behaviors and developer experiences.

– Expand the capabilities of .NET by taking the best of .NET Core, .NET Framework, Xamarin and Mono.

– Build that product out of a single code-base that developers (Microsoft and the community) can work on and expand together and that improves all scenarios.

Microsoft

Highlights

There are many improvements in .NET 5 like:

  • Performance across many components
  • Performance in .NET Libraries
  • Language C# 9 & F# 5
  • Application deployment options
  • Platform scope (includes Windows Arm64 & WebAssembly)

Details about these enhancements are here.

dot.net and Bing.com are already running on .NET 5 for months now

References

IDE

You need Visual Studio 16.8 or later to use .NET 5.0 on Windows and the latest version of Visual Studio for Mac on macOS. Latest C# extension for Visual Studio Code already supports .NET 5.0 and C# 9.

Impacts

There are few breaking changes with upgrade to .NET 5:

  • while migrating from version 3.1 of .NET Core, ASP.NET Core, or EF Core to version 5.0 of .NET, ASP.NET Core, or EF Core are captured here.
  • in Roslyn in C# 9.0 introduced with .NET 5 are captured here.
  • for migration from .NET Framework to .NET Core are captured here.
  • obsolete features in .NET 5 are captured here.

Deprecated

.NET 5 does not have few of the known technologies:

  • ASP.NET WebForms – Microsoft’s recommendation is to move to Blazor
  • Windows Communication Foundation (WCF) – Microsoft’s recommendation is to use gRPC
  • Windows Workflow Foundation (WWF) – recommendation is to look at CoreWF, a form of WF runtime

Wrap Up

.NET 5 is a major step of the .NET journey planned ahead. Next would be .NET 6 next year (late in 2021), which will also be a long term (multi year) supported (LTS) version.

Microsoft is working towards a defined vision – same .NET API and languages working across operating system, application types and architectures.

With active support to previous .NET versions, we have time to assess, plan and adapt the new path.


Keep exploring!

Sandeep Mewara Github
News Update
Tech Explore
Data Explore
samples GitHub Profile Readme
Learn Machine Learning with Examples
Machine Learning workflow
What is Data Science
Word Ladder solution
What is Dynamic Programming
Learn Microsoft Tech via Videos LiveTV Streams Microsoft .NET5

Find missing number from 1 to N?

Last week, there was a discussion in my team on the problem of finding missing number(s). We had different thoughts and approaches and thus I thought to share it across.

find-missing-number

Problem statement was something like:

– An array of size (n) has numbers from 1 to (n+1). Find the missing one number.

– An array of size (n) has numbers from 1 to (n+2). Find the missing two numbers.

First thought …

Keep track of numbers found while traversing. At the end, use it to find the missing number. So kind of brute force approach.

We can maintain a hash or a boolean array of n size and keep on updating the hash or the array index location based on number found while traversing. Use it now to find the missing number. It would cover both one as well as two missing numbers case.

This would have two traversals of n (one for filling in the structure and another to find the missing one). Thus overall, time complexity of O(n). This would need an extra space to keep track of all numbers found and thus a space complexity of O(n).

Q: Now, can we avoid extra space or two times traversal?

Second thought …

We know how to calculate the sum of n natural numbers, i.e.: n*(n+1)/2. With it, we can traverse the given array and keep a sum of all numbers. Difference of the sum from formula to sum found would give us the missing number. Nice!

# Keep track of sum
def sumOfGivenNumbers(nos, n):
    sum = 0
    # calculate sum
    for i in range(0, n):
        sum += nos[i]
    return sum

# Input
numbers = [4, 2, 1, 6, 5, 7] 

# number range 
n = len(numbers) + 1
expectedSum = n*(n+1)/2
numbersSum = sumOfGivenNumbers(numbers,len(numbers))

print('Missing number:', expectedSum - numbersSum)

# Output
# Missing number: 3.0

This would help is solve one missing number in single traversal, thus time complexity of O(n). No extra space was used and thus space complexity of O(1).

Q: Can we extend this to two missing numbers now?

Yes, we can extend it. Along with sum, we can also use the product of n natural number as an expression. With it, we will have two equations and two numbers to find:

Missing1 = x1
Missing2 = x2
Sum of provided numbers = N1
Sum of n Natural numbers = N
Product of provided numbers = P1
Product of n Natural numbers = P

x1 + x2 + N1 = N
x1 * x2 * P1 = P

We can solve it to find the two missing numbers. It does have the quadratic flavor associated though. It maintains the time complexity as O(n) and space complexity as O(1). Nice!

Q: Does the solution help with large integers? Think of possible overflow?

Third thought …

Let’s look at possible way for 1 missing number first.

We will traverse through all the numbers of the array. While doing so, maintain a number that would be sum of all numbers traversed so far reduced by sum of all the indexes traversed (+1 if index starts from 0). It is still making use of n natural numbers (in form of indexes) to keep a check on sum to a defined limit.

# Keep track of sum
def getMissingNumber(nos, n):
    sum = 0
    # calculate sum
    for i in range(0, n):
        sum += (i+1)
        sum -= nos[i]

    # last number to add from n+1 natural nos.
    return sum+n+1

# Input
numbers = [4, 2, 1, 6, 5, 7] 

missingNumber =getMissingNumber(numbers,len(numbers))

print('Missing number:', missingNumber)

# Output
# Missing number: 3.0

This looks good and we maintain the same complexities along with solving for overflow.

We can probably try a similar thing for two missing numbers where we keep on multiple and divide the traversed number by index but it still could have overflow issues in worst case. Further, there could be round off issues.

Fourth thought …

Looking more, it seems we can make use of XOR operation to find the missing numbers. We can make use of XOR’s property to nullify the duplicate pair. We will take XOR of provided numbers and XOR of natural numbers. Combining both again with XOR will leave with missing numbers XOR output.

For one missing number, this would be easy and covers all the hurdles discussed earlier keeping same performance.

# Keep track of XOR data
def getMissingNumber(nos, n):
    x1 = nos[0]
    xn = 1

    # start from second
    for i in range(1, n):
        x1 = x1 ^ nos[i]
        xn = xn ^ (i+1)
    
    # last number to XOR
    xn = xn ^ (n+1)

    # find the missing number
    return x1 ^ xn

# Input
numbers = [4, 2, 1, 6, 5, 7] 

missingNumber =getMissingNumber(numbers,len(numbers))

print('Missing number:', missingNumber)

# Output
# Missing number: 3.0

For two missing numbers, using a similar logic of XOR above, we will have an output of XOR value of both missing numbers. Now, given the XOR value will not be zero, the XOR corresponding valid bit in missing1 and missing2 must be different to make it “1”.

# Keep track of XOR data
def getTwoMissingNumber(nos, n):
    x1 = nos[0]
    xn = 1

    # start from second
    for i in range(1, n-2):
        x1 = x1 ^ nos[i]
        xn = xn ^ (i+1)
    
    # last numbers to XOR
    xn = xn ^ (n-1) ^ (n)

    # XOR of two missing numbers
    # Any set bit in it must be 
    # set in one missing and 
    # unset in other missing number 
    XOR = x1 ^ xn

    # Get a rightmost set bit of XOR  
    set_bit_no = XOR &amp; ~(XOR-1) 
  
    # Divide elements in two sets 
    # by comparing rightmost set bit of XOR 
    # with bit at same position in each element. 
    x = 0
    y = 0 
    for i in range(0,n-2): 
        if nos[i] &amp; set_bit_no:    
            # XOR of first set in nos[]  
            x = x ^ nos[i]   
        else: 
            # XOR of second set in nos[]  
            y = y ^ nos[i]   

    for i in range(1,n+1): 
        if i &amp; set_bit_no: 
            # XOR of first set in nos[]  
            x = x ^ i        
        else: 
            # XOR of second set in nos[]  
            y = y ^ i
    
    print ("Missing Numbers: %d %d"%(x,y)) 
    return

# Input
numbers = [4, 2, 1, 6, 7, 5] 

# total length will be provided count+2 missing ones
getTwoMissingNumber(numbers, len(numbers) + 2)

# Output
# Missing Numbers: 3 8

This overcomes the overflow issue and was easier to solve (compared to solving a quadratic equation). Though it took more than one traversal, overall it maintains the time complexity as O(n) and space complexity as O(1). Nice!

Closure …

There could be multiple ways to solve for one or more missing numbers. One can look at it based on ease and need.


Keep solving!

Sandeep Mewara Github
News Update
Tech Explore
Data Explore
samples GitHub Profile Readme
Learn Machine Learning with Examples
Machine Learning workflow
What is Data Science
Word Ladder solution
What is Dynamic Programming
Learn Microsoft Tech via Videos LiveTV Streams

POC Guide for Developers by Microsoft

Few weeks back, Microsoft Azure published a white paper about a Proof Of Concept (POC) guide for developers. Intent of the paper is to share what POC is and how it would help minimize risk and reduce cost while exploring new technology or an idea.

proof-of-concept

Guide uses Azure application as an example on how to create and execute a POC.

POC guide can be downloaded from here.

Brief Overview

Guide touch-bases and share details around:

  • POC Introduction
  • Steps of a POC
  • Example 1: Sample Azure web app
  • Example 2: Sample Azure chatbot

Additionally, it covers overview of Azure and where to find interactive learning path for beginners. It also shares additional resources that can help develop an Azure based application.

What is Proof of Concept?

Proof of concept (POC) is validating an idea or a concept about it’s feasibility, capability and provides helpful insights. They are scoped to limited features and are generally done in a quick and dirty manner to acquire some metrics.

A proof of concept is an important first step in cultivating business innovations.

How to prepare for and start your POC?

We can get a good POC following a defined set of basic steps:

  1. Defining a goal with success criteria
  2. Setting up a timeline and cost boundaries
  3. Scoping the feature(s) for the POC
  4. Designing, Implementing & Testing
  5. Measure metrics to deduce insights
  6. Take decisions based on the insights

Closing Thoughts

POCs are great way to validate an idea or a technology or a concept. With it, we can take a data back decision for a project that would reduce risk, provide a higher success probability and a conscious cost decision. It also help gauge probable next steps needed once adopted as a mainstream solution.

Provided document is a nice compile and provides a systematic approach for building a POC. With couple of examples, it demonstrates the steps in action. Definitely worth a read.

Don’t ever shy away from building and using a POC to explore and learn.


Keep exploring!

Sandeep Mewara Github
News Update
Tech Explore
Data Explore
samples GitHub Profile Readme
Learn Machine Learning with Examples
Machine Learning workflow
What is Data Science
Word Ladder solution
What is Dynamic Programming
Learn Microsoft Tech via Videos LiveTV Streams

Learn AI ML with Netflix’s Fei Fei!

Off late, Microsoft has been working on providing more and more learning materials. This is as per their Global Skills Initiative aimed at helping 25 million people worldwide acquire new digital skills.

global-initiative

Our goal is to ignite the passion to solve important problems relevant to their lives, families and communities.

Microsoft

Last week, they partnered with Netflix to release a new learning experience featuring a young female hero Fei Fei, who has a passion for science and explores space.

Newly launched

Microsoft has launched three new modules under Explore Space with “Over the Moon” learning path. These modules will help learn basic concepts of data science, artificial intelligence and machine learning:

  1. Plan a Moon Mission using the Python Pandas Library
  2. Predict Meteor Showers using Python and VC Code
  3. Use AI to Recognize Objects in Images using Azure Custom Vision
fei-fei-explore

The movie’s story takes place in a beautifully animated universe and tackles problems real-life space engineers face.

How is it?

They cover the basic workflow of a machine learning problem similar to what I shared in my previous article here.

Exercises also provide a professional experience as they are built on Visual Studio Code and use Azure Cognitive Services.

Looking at it, seems a fun way to learn and explore the data world. Microsoft is really trying to make things simple and available to all. An effort worth to try out. Would recommend and ask to give it a shot.


Keep learning!

samples GitHub Profile Readme
Learn Python – Beginners step by step – Basics and Examples
Sandeep Mewara Github
Sandeep Mewara Learn By Insight
Matplotlib plot samples
Sandeep Mewara Github Repositories
Learn Microsoft Tech via Videos LiveTV Streams
Machine Learning workflow

AWS re:Invent – Amazon Virtual Event 2020

Amazon is planning for AWS re:Invent 2020, a cloud learning virtual event that would be open for all for free. It is a conference for the global cloud computing community, hosted by AWS.

Full details of the events are here. Registrations are open.

Event is spread across 3 weeks: Nov 30 – Dec 18, 2020

amazon-reinvent

Get inspired to build
Enjoy unlimited access to hundreds of sessions led by AWS experts. Hear from cloud leaders and be the first to learn what’s new.

Event highlight shared by AWS

There would be multiple interactive ways to learn. Like, Sessions with over 50 content tracks, Training & Certification to advance your professional skills, all mixed with some fun activities in between.

The world is moving towards cloud. Thus, it seems a good opportunity to see how various organizations are using the cloud to solve problems and the skills needed for it.


Happy connecting!

samples GitHub Profile Readme
Learn Python – Beginners step by step – Basics and Examples
Sandeep Mewara Github
Sandeep Mewara Learn By Insight
Matplotlib plot samples
Sandeep Mewara Github Repositories
Learn Microsoft Tech via Videos LiveTV Streams

How to solve Word Ladder Problem?

Sometime back, a colleague of mine asked me about the word ladder problem. She was looking for a change. So, I believe she stumbled across this while preparing for data structures and algorithms.

graph-header

Problem Statement

Typically, the puzzle shared is a flavor of below:

Find the smallest number of transformations needed to change an initial word to a target word of same length. In every transformation, change only one character and make sure word exists in the given dictionary.

Explanation

Assuming all these 4 letter words are there in the dictionary provided, it takes minimum 4 transitions to convert word from SAIL to RUIN, i.e.
SAIL -> MAIL -> MAIN -> RAIN -> RUIN

Intent here is to know about Graph algorithm. So, what are graphs in context of algorithms and how do we apply them to solve such problems?

Graph Data Structure

Graphs are flow structure that represents entities connection with each other. Visually, they are represented with help of a Node (Vertex) & an Edge (Connector).

graph-general

A tree is an undirected graph in which any two nodes are connected by only one path. In it, each node (except the root node) comprises exactly one parent node.

Most common way to represent a graph is using an Adjacency matrix. In it, Element A[i][j] is 1 if there is an edge from node i to node j or else it is 0. For example, adjacency matrix of above unidirected graph is:

  | 1 2 3 4
------------
1 | 0 1 0 1
2 | 1 0 1 0
3 | 0 1 0 1
4 | 1 0 1 0

Another common way is via Adjacency list. (List format of the data instead of a matrix.)

Related Algorithms

Graphs are applied in search algorithms. Traversing the nodes and edges in a defined order helps in optimizing search. There are two specific approaches to traverse graph:

Breadth First Search (BFS)

Given a graph G and a starting node s, search proceeds by exploring edges in the graph to find all the nodes in G for which there is a path from s. With this approach, it finds all the nodes that are at a distance k from s before it finds any nodes that are at a distance k+1.

For easy visualization, think of it as, in a tree, finding all the child nodes for a parent node as first step. Post it, find all the grandchildren and hence forth.

Depth First Search (DFS)

Given a graph G and a starting node s, search proceeds by exploring edges in the graph to find all the nodes in G traversed from s through it’s edges. With this approach, we go deep in graph connecting as many nodes in the graph as possible and branch where necessary.

For easy visualization, think of it as, in a tree, finding all the family nodes for a parent node. With this, for a given node, we connect its children, grand children, grand grand children and so on before moving to next node of same level.

Thus, with DFS approach, we can have multiple deduced trees.

Knight’s tour is a classic example that leverages Depth First Search algorithm.

Shortest Path First OR Dijkstra’s Algorithm (SPF)

Given a graph G and a starting node s, search the shortest path to reach node d. It uses a concept of weights. It’s an iterative algorithm similar to results of BFS.

Many real world example fits in here, e.g. what would be shortest path from home to office.

With BFS (a simple queue), we visit one node at a time whereas in SPF (a priority queue), we visit a node at any level with lowest cost. In a sense, BFS follows Dijkstra's algorithm, a step at a time with all edge weights equal to 1. The process for exploring the graph is structurally the same in both cases. at times, BFS is preferred with equal weight graphs. This is because, operations on a priority queue are O(log n) compared to operations on a regular queue which is O(1).

Code

I will be using a breadth first graph algorithm here based on the problem need:

import collections
from collections import deque 

class Solution(object):
    # method that will help find the path
    def ladderLength(self, beginWord, 
                        endWord, wordList):
        """
        :type beginWord: str
        :type endWord: str
        :type wordList: Set[str]
        :returntype: int
        """

        # Queue for BFS
        queue = deque()

        # start by adding begin word
        queue.append((beginWord, [beginWord]))

        while queue:
            # let's keep a watch at active queue
            print('Current queue:',queue)

            # get the current node and 
            # path how it came
            node, path = queue.popleft()

            # let's keep track of path length 
            # traversed so far
            print('Current transformation count:',
                                        len(path))

            # find possible next set of 
            # child nodes, 1 diff
            for next in self.next_nodes(node, 
                            wordList) - set(path):
                # traversing through all child nodes
                # if any of the child matches, 
                # we are good               
                if next == endWord:
                    print('found endword at path:',
                                            path)
                    return len(path)
                else:
                    # keep record of next 
                    # possible paths
                    queue.append((next, 
                                path + [next]))
        return 0

    def next_nodes(self, word, word_list):
        # start with empty collection
        possiblenodes = set()

        # all the words are of fixed length
        wl_word_length = len(word)

        # loop through all the words in 
        # the word list
        for wl_word in word_list:
            mismatch_count = 0

            # find all the words that are 
            # only a letter different from 
            # current word those are the 
            # possible next child nodes
            for i in range(wl_word_length):
                if wl_word[i] != word[i]:
                    mismatch_count += 1
            if mismatch_count == 1:
                # only one alphabet different-yes
                possiblenodes.add(wl_word)
        
        # lets see the set of next possible nodes 
        print('possible next nodes:',possiblenodes)
        return possiblenodes

# Setup
beginWord = "SAIL"
endWord = "RUIN"
wordList = ["SAIL","RAIN","REST","BAIL","MAIL",
                                    "MAIN","RUIN"]

# Call
print('Transformations needed: ',
    Solution().ladderLength(beginWord, 
                            endWord, wordList))

# Transformation expected == 4
# One possible shortes path with 4 transformation:
# SAIL -> MAIL -> MAIN -> RAIN -> RUIN

Used deque (doubly ended queue) of Python

deque helps with quicker append and pop operations from both the ends. It has O(1) time complexity for append and pop operations. In comparison, list provides it in O(n) time complexity.

A quick look at the code workflow to validate if all nodes at a particular distance was traversed first and then moved to next level:

Current queue: deque([('SAIL', ['SAIL'])])

Current transformation count: 1
possible next nodes: {'BAIL', 'MAIL'}
Current queue: deque([('BAIL', ['SAIL', 'BAIL']), 
                      ('MAIL', ['SAIL', 'MAIL'])])

Current transformation count: 2
possible next nodes: {'SAIL', 'MAIL'}
Current queue: deque([('MAIL', ['SAIL', 'MAIL']), 
                      ('MAIL', ['SAIL', 'BAIL', 
                       'MAIL'])])

Current transformation count: 2
possible next nodes: {'BAIL', 'MAIN', 'SAIL'}
Current queue: deque([('MAIL', ['SAIL', 'BAIL', 
                                'MAIL']), 
                      ('BAIL', ['SAIL', 'MAIL', 
                                'BAIL']), 
                      ('MAIN', ['SAIL', 'MAIL', 
                                'MAIN'])])

Current transformation count: 3
possible next nodes: {'BAIL', 'MAIN', 'SAIL'}
Current queue: deque([('BAIL', ['SAIL', 'MAIL', 
                                'BAIL']), 
                      ('MAIN', ['SAIL', 'MAIL', 
                                'MAIN']), 
                      ('MAIN', ['SAIL', 'BAIL', 
                                'MAIL', 'MAIN'])])

Current transformation count: 3
possible next nodes: {'SAIL', 'MAIL'}
Current queue: deque([('MAIN', ['SAIL', 'MAIL', 
                                'MAIN']), 
                      ('MAIN', ['SAIL', 'BAIL', 
                                'MAIL', 'MAIN'])])

Current transformation count: 3
possible next nodes: {'RAIN', 'MAIL'}
Current queue: deque([('MAIN', ['SAIL', 'BAIL', 
                                'MAIL', 'MAIN']), 
                      ('RAIN', ['SAIL', 'MAIL', 
                                'MAIN', 'RAIN'])])

Current transformation count: 4
possible next nodes: {'RAIN', 'MAIL'}
Current queue: deque([('RAIN', ['SAIL', 'MAIL', 
                                'MAIN', 'RAIN']), 
                      ('RAIN', ['SAIL', 'BAIL', 
                        'MAIL', 'MAIN', 'RAIN'])])

Current transformation count: 4
possible next nodes: {'MAIN', 'RUIN'}
found endword at path: ['SAIL', 'MAIL', 'MAIN', 
                                        'RAIN']

Transformations needed:  4
Overall path: ['SAIL', 'MAIL', 'MAIN', 
                               'RAIN', 'RUIN']

Complexity

For above code that I used to find the shortest path for transformation:

Time

In next_nodes, for each word in the word list, we iterated over its length to find all the intermediate words corresponding to it. Thus we did M×N iterations, where M is the length of each word and N is the total number of words in the input word list. Further, to form an intermediate word, it takes O(M) time. This adds up to O(M2×N).

In ladderLength, BFS can go to each of the N words and for each word, we need to examine M possible intermediate words. This adds up to O(M2×N).

Overall, it adds up to O2(M2×N) which would be called O(M2×N).

Space

In next_nodes, each word in the word list would have M intermediate combinations. For every word we need a space of M2 to save all the transformations corresponding to it. Thus, it would need a total space of O(M2×N).

In ladderLength, BFS queue would need a space of O(M×N)

Overall, it adds up to O(M2×N) + O(M×N) which would be called O(M2×N)

Wrap Up

It could be little tricky and thus would need some practice to visualize the graph as well to write code for it.

Great, so now we know how to solve problems like word ladder problem. It also touch based other related common graph algorithms that we can refer to.

I had a read of the following reference and it has much more details if needed.


Keep problem solving!

samples GitHub Profile Readme
Learn Python – Beginners step by step – Basics and Examples
Sandeep Mewara Github
Sandeep Mewara Learn By Insight
Matplotlib plot samples
Sandeep Mewara Github Repositories

Learn Microsoft Tech via Videos & Live Streams

Recently, Microsoft has invested and made extra efforts into putting up the resources to learn.

microsoft-learn

Recordings …

This September, Microsoft launched Video Hub, a new resource home for Tech Community Videos and Interactive Guides to help learn everything about major Microsoft products.

Access: Microsoft Tech Community Video Hub

Live …

Yesterday (Mid October), Microsoft launched .NET Live TV, a one stop shop for all .NET and Visual Studio Live Streams across Twitch and YouTube.

To view, visit: .NET Live TV

Sometime back, Microsoft launched Learn TV. It is a place to find the latest digital content to be updated on the latest announcements, features, and products from Microsoft.

To view, visit: Learn TV

Discover your path …

As shared on the Microsoft’s Learning site, irrespective of which stage you are in your carrier – a fresher or an experience professional, material can help learn hands on and gain confidence faster.

You can choose topics, learn at your own schedule and even do Microsoft based certifications. It even has suggestions and ratings for popular topics to guide further.

Explore: Microsoft Learn

Well, seems knowledge is all there and pretty organized for the taking.


Keep learning!

samples GitHub Profile Readme
Learn Python – Beginners step by step – Basics and Examples
Sandeep Mewara Github
Sandeep Mewara Learn By Insight
Matplotlib plot samples
Sandeep Mewara Github Repositories

Just reverse alphabets in a string?

Last week it was a simple problem that we discussed to tangle our brain.

string-reverse

Reverse only alphabets in a provided string in a most efficient way. (Special characters, numbers, etc should continue to stay at their original place)

First thought …

Okay, so first thought was to make use of an extra space and then we can get our desired result with two traversals of the string. Yeah, but let’s optimize.

Updated thought …

We can make the swaps in place in a single traversal. A good stopping criteria seems to be when index while moving from front crosses the index moving backwards from end.

Let’s write code:

static void Main(string[] args)
{
    Console.WriteLine($"Please enter a string:");

    // Ignore casing
    var inputString = Console.ReadLine().ToLower();
    char[] inputArray = inputString.ToCharArray();
    ReverseAlphabetsOnly(inputArray);        
    Console.WriteLine(
            $"Reversed: {new String(inputArray)}");
}

static void ReverseAlphabetsOnly(char[] inputArray)
{
    int frontIndex = 0;
    int endIndex = inputArray.Length-1;
    char temp;

    while(frontIndex < endIndex)
    {
        if(!IsAlphabet(inputArray[frontIndex]))
            frontIndex++;
        else if(!IsAlphabet(inputArray[endIndex]))
            endIndex--;    
        else
        {
            temp = inputArray[frontIndex];
            inputArray[frontIndex] 
                 = inputArray[endIndex];
            inputArray[endIndex] = temp;

            frontIndex++;
            endIndex--;
        }
    }
}

static bool IsAlphabet(char x) 
{ 
    return ( (x >= 'a' &amp;&amp; x <= 'z') 
            || (x >= 'A' &amp;&amp; x <= 'Z') ); 
}

// Input:  [email protected] By In$ig#t...
// Output: [email protected] Iy Bn$re#L...

Closure …

Approach looks good, as it would be at maximum a single traversal with no extra space used. Thus we are able to solve it with an overall Order of Time complexity O(n) & Space complexity O(1).


Happy solving …

samples GitHub Profile Readme
Learn Python – Beginners step by step – Basics and Examples
Sandeep Mewara Github
Sandeep Mewara Learn By Insight
Matplotlib plot samples
Sandeep Mewara Github Repositories