liveType is a web application used for real-time typing competition between two players. Users can join room from any corner of the globe and compete as well as chat in real-time.
Why liveType?
Many people use to test their typing speed on various wonderful platforms like monkeytype.com, typerush.com etc. But what they miss is real-time rivalry between their friends. Many studies have already proven that motivation to do a task comes when there is a win-reward system, so is the case with liveType, you feel overwhelmed beating your friend in a close compitition.
Project Inception
The idea to build the project came to my mind when I was quite bored with binged typing on monkeytype.com. The first commit was made on 27 th of November 2022 and it took three days to build the first substantial model.
Vulnerabilities to be probed
Although socket.io uses long polling for maintaining constant communication between server and the client, it has been observed that connection may broke on delayed inactivity from client's end. Thus it is advised to refresh the window when this happens.
I am extremely happy to share with you that I have made my own social media called "beSocial". It is a full stack project which is completely built with Nodejs, Expressjs, Mongodb and some node libraries. It took me almost four days to complete it. Since Heroku has already withdraw its free tier services, I have moved to Render.
I have tried to make development environment as comprehensive as possible. The file structure looks like this:
toastKing.js is a light-weight JavaScript library for creating non-blocking, beautiful notification messages.
I am very fond of beautiful notification or toast messages. They are often used in web applications. I searched the internet for such libraries and found some, but the problem was that they are very mediocre in looks or a kind of boring. Then I decided to make a library for notification cum toast messages that will be very beautiful in terms of graphics and will have some interactive features. Before developing the library, I made a layout of it, which looks like this:
After completing the design, I started the coding part. All the CSS and HTML is dynamic. User need not to including any additional CSS or HTML in his program.
In Computer Science and Operations Research, Genetic Algorithms are often used for find the optimal solution of a optimization problem, more formally, GAs are heuristic algorithms.
GAs are based on Darwin's theory of natural selection. i.e. survival of the fittest.
Heuristic Algorithms: In mathematical optimization and computer science, heuristic is a technique designed for solving a problem more quickly when classic methods are too slow or for finding an approximate solution when classic methods fail to find any exact solution.
Steps followed in designing a genetic algorithm
What I have made?
I have made a simulation of GA in which the algorithm goes on computing until it founds the optimal string.
Flood fill algorithm helps in visiting each and every point in a given area. It determines the area connected to a given cell in a multi-dimensional array. Following are some famous implementations of flood fill algorithm:
Bucket Fill in Paint: Clicking in an area with this tool selected fills that area with the selected color.
Solving a Maze: Given a matrix with some starting point, and some destination with some obstacles in between, this algorithm helps to find out the path from source to destination
Minesweeper: When a blank cell is discovered, this algorithm helps in revealing neighboring cells. This step is done recursively till cells having numbers are discovered.
Flood fill algorithm can be simply modeled as graph traversal problem, representing the given area as a matrix and considering every cell of that matrix as a vertex that is connected to points above it, below it, to right of it, and to left of it and in case of 8-connections, to the points at both diagonals also. For example, consider the image given below.
It clearly shows how the cell in the middle is connected to cells around it. For instance, there are 8-connections like there are in Minesweeper (clicking on any cell that turns out to be blank reveals 8 cells around it which contains a number or are blank). The cell (1,1) is connected in (2,1), (1,2), (1,0), (0,0), (0,2), (2,0), (2,2) and (0,1).
ie Each (x,y) cell is connected to (x-1,y), (x+1,y), (x,y+1), (x,y-1), (x+1,y+1), (x+1,y-1), (x-1,y+1) and (x-1,y-1).
Algorithm
function DFS(x, y, visited, n, m)if(x ≥ n OR y ≥ m)returnif(x <0 OR y <0)returnif(visisted[x][y]==True)return
visited[x][y]=True
DFS(x-1, y-1, visited, n, m)
DFS(x-1, y, visited, n, m)
DFS(x-1, y+1, visited, n, m)
DFS(x, y-1, visited, n, m)
DFS(x, y+1, visited, n, m)
DFS(x+1, y-1, visited, n, m)
DFS(x+1, y, visited, n, m)
DFS(x+1, y+1, visited, n, m)
The above code visits each and every cell of a matrix of size starting with some source cell. Time Complexity of above algorithm is O(m*n).
We have seen the Binary Search Algorithm which searches for an element in a sorted array in logarithmic time. Time complexity associated with it is .
Recurrence relation of Binary Search:
Using the same principle of Divide, Conquer, and Combine, we can also utilize this algorithm to find an element in an unsorted array, though the time complexity will be linear .
Sum of an array using Divide and Conquer algorithm (DAC)
Finding sum of an array is a very easy task, just add all the elements in a single pass! Time and space complexity associated with this approach is linear and constant respectively.
In this post, I will show how we can find the sum of an array using Divide and Conquer algorithm.
First of all I would like you to have a glance at What a Divide and Conquer algorithm is?
Divide and Conquer is an algorithmic strategy used to find solution of a particular problem by recursively breaking down the problem into sub-problems of same type, and when the base condition of the recursion is hit, assemble the results of those sub-problems to form the solution of the original problem.
This strategy often brings considerable optimizations in some while solving some problems. Some popular algorithms that implements Divide and Conquer are:
1. Quicksort
2. Mergesort
3. Binary Exponentiation
4. Quickselect
5. Straseen's algorithm (Matrix Multiplication)
6. Binary Search
The Divide and Conquer strategy can be divided into three parts:
1. Divide: Divide the larger problem into smaller sub-problems of same type.
2. Conquer: Solve the sub-problems by recursively calling until solved.
3. Combine:Combine the sub-problems to get the final solution of the whole problem.
It becomes very easy to find the time complexity of DAC algorithms using Master Theorem.
Image given below shows how to solve recurrence relations using Master Method.
Now, coming back to the question. We have to find the sum of an array using DAC.
Let's formulate the solution:
Sum of an array can be found using breaking the array into two halves, add them and return the sum. Recursively break down the problem into two halves, we the array size becomes 1, return the value of that single element. So simple!
intsum(intarr[],intstart,intend)
{
if(start==end)
returnarr[start];
intmid=start+(end-start)/2;
intleft=sum(arr,start,mid);
intright=sum(arr,mid+1,end);
returnleft+right;
}
intarr[]={1,2,3,-1,4,5,6,7};
cout<<sum(arr,0,sizeof(arr)/sizeof(int)-1);
output: 27
I have traced the algorithm:
Now, let's find the time complexity of this algorithm.
Suppose I give you an array of numbers and ask you to give me the smallest number. How will you come out with solution?
One simple solution is to sort the array and return the element at index, or ARR[K-1].
C++ code
intkthSmallest(int*arr,intn,intk)
{
sort(arr,arr+n);
returnarr[k-1];
}
The time complexity of this approach will be depending upon the sorting algorithm we use. Let us suppose we use the very popular comparison based sorting algorithm known as quicksort.
Since time complexity of quicksort is . Therefore our naive solution will also have the same complexity of .
Is it a good approach?
Surely no because by sorting the whole array, we will be in the position to answer each element from k=1 to k=N ( N is the length of the array). What I want to say is we are doing extra efforts, which we can skip.
Before heading towards our goal, first let us know about the partitioning algorithm.
Partitioning Algorithm
Partitioning algorithm is a subroutine of quicksort algorithm which creates a pivot in the array and returns its index. Elements in the left hand side of the array are less than the pivot and that of right side are greater than the pivot.
for example, if the array is 3,2,1,5,6,4.Then after partitioning it will look like 1,2,3,5,6,4.
It takes the first element and places it at some index such that all elements before it are lesser than it and all element to its right are greater than it.
Here 3 is selected as pivot and placed at index 2.
C++ code
intpartition(int*arr,intlb,intub)
{
intstart=lb,end=ub;
intpivot=arr[start];
while(start<end )
{
while(arr[start]<=pivot)
++start;
while(arr[end]>pivot)
--end;
if(start<end)
swap(arr[start],arr[end]);
}
swap(arr[lb],arr[end]);
returnend;
}
Time complexity of this partitioning algorithm is .
QuickSelect Algorithm:
Similar to quicksort algorithm, quickselect calls partition function as it subroutine. The partition function partitions the array into two parts and returns the index of the pivot element.
Now, if the index of the pivot element is equal to k, then the quickselect functions returns the pivot, else if k is greater than the pivot index, then the quickselect is called for the right side of the array or if k is less than the pivot index, then the quickseleck is called for the left side of the array.
Look at the code for better understanding.
intquickSelect(int*arr,intstart,intend,intk)
{
if(start>end)
return0;
intpInd=partition(arr,start,end);
if(pInd==k)
returnarr[pInd];
if(k>pInd)
{
quickSelect(arr,pInd+1,end,k);
}
else
{
quickSelect(arr,start,pInd-1,k);
}
}
Now let's do the analysis of QuickSelect algorithm:
Primality test is an algorithm used to determine if a number is prime or not.
One of the basic algorithm used is given below:
Its time complexity is O(√n), and space complexity is O(1).
Suppose n is greater than 10^20 ie out of range of the long long int , the largest container of c++ in terms of size(8 bytes).
In this case the mentioned algo will indeed perform poorly. Therefore we must have some techinque/algorithm to counter bigger numbers.
One of the best algorithm to check if a number is prime or not is given below:
The time complexity of this algorithm is O(√n), here 'n' is the number under consideration. Suppose we have a total of 'Q' numbers , Q and n can be as large as a million. Now we have to check each number whether it is prime or not.
Since, n and Q are the order of 10^6, therefore in worst case, our machine would have to do O(Q√n) computations ie ~10^6*10^3=10^9 computations, which will take more than the expected time!
Here comes this Sieve algorithm. It is a preprocessing technique which generates all the prime numbers between 0 and a given limit. It is very efficient in cases we have to find all the prime numbers between a range.
Time Complexity O(nlog(n)log(n))
Auxiliary Space O(n)
