COVID-19 End Date Predictions - A Machine Learning Experiment

I am writing this post to address the gigantic elephant in the room about which the entire world is wondering — When really is the COVID-19 crisis going to end? When will all of our lives, the world economy, healthcare, infrastructure, travel, tourism — when are all these things going to go back to normal? Seeing that these questions are popping up from every corner of the world, one of my friends did and experiment to find out the answers.
We computer science majors have a problem — we try to answer every question in the world with machine learning. Why do we do so? It’s because machine learning does have the ability to answer every question in the world (although the answer to every question in the world is 42, but that’s a different discussion :P). So naturally, my friend, being a computer science major, starts putting his machine learning mind to work. He pulls out a popular model — the SIR model. The SIR model is a differential equation model for a set of dependant variables — Susceptible, Infected and Recovered, a model perfect for a pandemic outbreak such as the COVID-19 (you can Google it!). He pulls the daily cases reports coming in from different countries and trains his model to learn the pattern in which the COVID-19 has played out in these countries to date. Once trained, he applies this model on another set of countries and voila! This is the result:

He created a website on which he updates his predictions daily for the public to look at. Obviously, the website has more data than I’ve put up in the above image, because he wants you all to visit his website and give your suggestions and feedback :P. However, let me describe the image a bit for your benefit:
What does “Predicted Max Cases” mean?
It is a prediction of the total number of confirmed cases a region will see in the current COVID-19 lifecycle.
What does “Ends Completely” mean?
It is a prediction of the date when the region is likely to report the very last case.
What does the increase and decrease in the table mean?
The increment and decrement of the values in the cells is in comparison to the previous day’s predicted values.
For the nerds out there, if you’re really curious and interested about how he arrived at the final results, just click on any of the regions and something interesting will pop-up:

Yes, that’s what the machine learning algorithm has spit out for him. He just transformed the results into a readable tabular format for you all to perceive the predictions easily.
Predictions can be a sensitive issue, so my friend is really concerned about how people would react after looking at them. So, he thought it apt to put up a disclaimer for you all:
Disclaimer: Content from this website is STRICTLY ONLY for showing purpose and may contain errors. The model and data are inaccurate to the complex, evolving, and heterogeneous realities of different regions over time. Predictions are uncertain by nature. Users must take any predictions with caution. Over-optimism based on some predictions is dangerous because it may loosen our disciplines and controls and cause the turnaround of the virus and infection, and must be avoided. Earlier predictions are no longer valid because the real-world scenarios have changed rapidly.
Thanks for reading! Don’t forget to check out the website. And if you liked what you read, do share this answer with your close ones to let them know when they can expect to be free from the chains of COVID-19! :)

NextShow: Personalised Movie Recommendations with Friends’ Reviews

Planning to watch a movie, but not able to decide which one? I came across this awesome website: NextShow (https://www.nextshow.co/), which not only recommends you movies based on your personal taste, but also tells you how your friends have reacted to those movies. Interesting, isn’t it?

Let me tell you about some key features of NextShow:

- Powerful, personalised movie recommendations based on your taste.

- Movies your friends have watched and liked/disliked.

- Helps you keep yourself updated on the latest movies, so that you’ll never miss a great one again.

NextShow has a vast collection of movies spread over 26 categories and 19 languages, so that no one feels inadequate whenever they are in the mood for a movie.

- Categories include “Now Playing”, “Upcoming”, “Popular” and “Top Rated” Movies, as well as movies from the 2000s, 90s, 80s and the Classics. Categories also include movies over various genres such as Romance, Comedy, Horror, Thriller, Adventure, Action, Music, Documentary, Fantasy, Drama, Science Fiction, Mystery, Crime, War, Family, History, Animation and TV Movies.

- Languages include world languages such as English, Hindi, French, Italian, Japanese, German, Spanish, Russian, Korean, Chinese and Portuguese. Languages also include Indian regional languages such as Tamil, Telugu, Kannada, Marathi, Malayalam, Bengali, Punjabi and Gujarati.

If you are indeed confused as to what to watch next, NextShow is the perfect place for you to go.

Solution to "House of Cards"

View Problem: House of Cards

Let us assume that instead of spending the night in the last house he visits, Underwood returns to his house the same day. Clearly, in such a case, the distance he travels will be 2 x (Number of Edges in the Tree) = 2(N-1). Now, if he does stay back in the last house he visits, it will be best if the distance between his own house and this last house (say D) is as large as possible. This is because the distance traveled by him in this case will be 2(N-1) - D. Hence, the minimum distance traveled by Underwood will be 2(N-1) - (Length of the longest path between the root to a leaf).

House of Cards

Frank Underwood is running for the post of "President of the United States of America". He is now in his home state South Carolina for campaigning. Today, he is visiting the city he grew up in, Gaffney.

Houses in Gaffney are arranged in the form of a tree with N nodes. Houses are denoted by the nodes, and roads (each of length 1 unit) are denoted by the edges of the tree. At present, Frank is at his house, which also happens to be the root of the tree. He plans on visiting each and every house in the city. It will be very late by the time Frank finishes visiting all the houses and he will have to spend the night in the last house he visits.

Given the map of Gaffney, can you state the minimum distance he has to travel today to visit each and every house in the city? Let us look at an example:

If Frank travels as shown in Fig 1, the distance traveled by him will be 3 + 3 + 2 = 8 units. However, if he travels as shown in Fig 2, the distance traveled by him will be 2 + 2 + 3 = 7 units. Clearly, Fig 2 depicts a better way of visiting the houses.

View Solution: Solution to "House of Cards"

Solution to "Squary Numbers"

View Problem: Squary Numbers

We will solve this problem by using a Dynamic Programming (DP) approach. Let us assume the number N is given to us in a string format s[1..L] where L is the number of digits in N. s[i..j] denotes the sub-string starting at index i (inclusive) and ending at index j (again inclusive).

s[i..j] is Squary if and only if for at least one k in [i..j-1], both s[i..k] and s[k+1..j] are Squary. This is our sub-problem for the Dynamic Programming approach:

dp[1..L][1..L] = 0;

for(i=1; i<=L; i++)
{
    for(j=i; j<=L; j++)
    {
        if(isPerfectSquare(s[i..j]))
        {
            dp[i][j] = 1;
        }
    }
}

for(l=1; l<=L; l++)
{
    for(i=1; i<=L-l+1; i++)
    {
        j = i+l-1;

        for(k=i; k<=j-1; k++)
        {
            if(dp[i][k] == 1 && dp[k+1][j] == 1)
            {
                dp[i][j] = 1;
            }
        }
    }
}

dp[i][j] = 1 only if s[i..j] is Squary, otherwise dp[i][j]=0. So, if dp[1][L] = 1, then N is Squary, otherwise it isn't.

To find a valid partitioning for a Squary number, we use the following simple recursive algorithm:

partitions(i, j, s, dp)
{
    if(isPerfectSquare(s[i..j]))
    {
       return(pair(i,j)); 
    }
    else
    {
        for(k=i; k<=j-1; k++)
        {
            if(dp[i][k] == 1 && dp[k+1][j] == 1)
            {
                return(partitions(i, k, s, dp) + partitions(k+1, j, s, dp));
            }
        }
    }
}

Calling partitions(1, L, s, dp) will return a set of pairs of indices denoting the starting and ending indices of all the partitions.

Solution to "Multiplying Nines"

View Problem: Multiplying Nines

The trick lies in writing a number with K 9's (i.e. 999...9 occurring K times) as 10^K-1. So, the numbers A and B can be written as A = 10^N-1 and B = 10^M-1.

A x B = (10^N-1) x (10^M-1) = 10^N+M - 10^N - 10^M + 1

Without loss of generality, let N >= M. Let us now try to compute the above result:

   10000...0000     // N+M 0's
-     1000..000     // N 0's
-       100..00     // M 0's
+             1
-------------------------------------------------------------
[(M-1) 9's]  [1 8]  [(N-M-1) 9's]  [1 9]  [(M-1) 0's]  [1 1]
-------------------------------------------------------------

The answer can obtained by making simple observations while performing the subtractions and addition as shown above.

Solution to "Divided Tree Processing"

View Problem: Divided Tree Processing

Initially, let us assume that the task can be completed in 0 time. This would mean that each parent assigns sub-tasks to its children at the same time which is T = 0. We will now delay the sub-task distribution only where it will be required, thus minimizing the time to complete the task.

Let time_received[i] denote the time at which node i received its task. Let time_completed[i] denote the time at which node i completed its task. If node i has children, let child[i][0] and child[i][1] denote the indices of its children.

Let us say that both the children complete their tasks at the same time. This case has to be avoided, so we simply delay the giving away of sub-task for one of the children by 1 time unit. This will work due to our initial assumption that all parents distribute the sub-tasks to their children at the same time. We then apply this condition recursively (assume initially for all i, time_received[i] = time_completed[i] = 0):

calculate(i)
{
    if(!hasChildren(i))
    {
        time_received[i] = 0;
        time_completed[i] = 0;
    }
    else
    {
        calculate(child[i][0]);
        calculate(child[i][1]);

        if(time_completed[child[i][0]] == time_completed[child[i][1]])
        {
            /*
             Increment by 1 the time_received[i] and time_completed[i] for all i 
             such that node i belongs to the sub-tree rooted at node child[i][1].
            */

            time_completed[i] = time_completed[child[i][0]] + 1;
        }
        else
        {
            time_completed[i] = max(time_completed[child[i][0]], time_completed[child[i][1]]); 
        }
    }
}

calculate(1) fills time_received[i] and time_completed[i] for all i. time_completed[1] gives us the minimum time taken by the system to complete the entire task.

The above algorithm can be optimized. Instead of incrementing the values of time_completed[i] and time_received[i] for all i which belong to the sub-tree rooted at node child[i][1], we can store separately for which sub-tree the increment has to be performed. In the end, these stored values can be added in a cumulative fashion by following a top-down approach.