Algorithms that run our Universe

Largest palindrome made from product of two 3-digit numbers

We will find the largest palindrome that is a product of two three-digit numbers. In brute force, there are 810000 comparisons which we have reduced to 362 computations based on three deep insights.

Algorithms

Largest prime factor of a number (Project Euler Problem 3)

We need to find the largest prime factor of a given number N. We will bring in some insights and solve this in O(√N log log N) time complexity.

Algorithms

Largest subset with divisible pairs

We explored the method to get the longest subset within any given array, such that for each pair, the smaller number divides the larger number using Dynamic Programming.

Algorithms

Sum of Even Fibonacci Numbers (Project Euler Problem 2)

The problem is find the sum of even fibonacci numbers that is fibonacci numbers that are even and is less than a given number N. We will present 3 insightful ideas to solve this efficiently.

Algorithms

Sum of multiples of 3 and 5 (Project Euler Problem 1)

The problem at hand is to find the sum of all numbers less than a given number N which are divisible by 3 and/ or 5 using a constant time algorithm.

Algorithms

Calculate Binomial Coefficient using Dynamic Programming

Using a recursive relation, we will calculate the N binomial coefficient in linear time O(N * K) using Dynamic Programming

Algorithms

Find the largest number with given number of digits and sum of digits

In this problem, we need to find the largest number with a given number of digits N and given sum of digits say M. We will use a greedy algorithm to solve this is O(N) time complexity.

Algorithms

Maximum Sum Rectangle in a Matrix

Given a 2D array, we need to find the subarray with the maximum sum of its elements. We solve this using Dynamic Programming in O(N^3) where brute force takes O(N^5)

Algorithms

Find the smallest number with given number of digits and sum of digits

We are given two positive integers M and N. The task is to find the smallest number that has length M (number of digits) and sum of digits as N. We will solve this using a greedy approach in O(M)

Algorithms

Calculate Newman Conway Sequence

Newman Conway Sequence is the sequence which follows a given recursive relation (p(n) = p(p(n-1)) + p(n-p(n-1))). We solve it using Dynamic Programming in O(N) time

Algorithms

Find number of subsets with sum divisible by given number M

Find the number of subsets with sum divisible by given number M. We solved this using a Dynamic Programming approach with time complexity O(N * M).

Software Engineering

Types of CPU Scheduling algorithms

We explored different types of CPU Scheduling algorithms such as FCFS, SJF, SRTF, Round Robin, priority, multilevel queue and feedback queue scheduling.

Algorithms

Implement Least Recently Used (LRU) Cache

In this article, we have implemented Least Recently Used cache using 2 data structures: Doubly Linked Lists and Hash Map and compared LRU with FIFO cache.

Algorithms

Split N into maximum composite numbers

Given a number N, the problem is to count the maximum number of composite numbers that sum up to N. We solve this using a greedy algorithm in constant time

Algorithms

Find point of 2D Line Intersection

The point of intersection of two 2D lines can be calculated using two algorithms namely Elimination method and Determinant method which takes constant time O(1)

Algorithms

Finding the number of sub matrices having sum divisible by K

This article is about counting the number of sub-matrices such that the sum of the elements is divisible by k and using Dynamic Programming, we solve it in O(N^3)

Algorithms

Number of ordered pairs such that (A[i] & A[j])=0

Given array A[] of n integers, find out the number of ordered pairs such that (A[i]&A[j])=0. This can be done using dynamic programming in O(N*(2^N)) time

Algorithms

8 Queens Problem using Branch and Bound

In the backtracking approach of solving 8 queens problem, we maintain an 8x8 binary matrix for keeping track of safe cells and update it each time we place a new queen.

Algorithms

Largest rectangular sub matrix having sum divisible by k

This article is about finding the size of the largest area of the rectangular sub-matrix such that the sum of the elements is divisible by k.

Algorithms

Calculating Permutation Coefficient

Given n and k, we will calculate permutation coefficient using dynamic programming in O(N * K) time complexity.

Algorithms

Maximize the sum of array[i]*i

Given an array of N integer, we have to maximize the sum of arr[i] * i. Brute force approach will take O(N*N!) time while greedy algorithm will take O(N log N) time

Algorithms

8 Queens Problem using Backtracking

In this article, we will solve the 8 queens problem using backtracking which will take O(N!) time complexity. We demonstrate it with code.

Algorithms

Count all subsequences in an array with product less than K

Finding subsequences in an array with product less than a given number is another area of application of dynamic programming.

Algorithms

Secant Method to find root of any function

Secant Method is a numerical method for solving an equation in one unknown. It avoids this issue of Newton’s method by using a finite difference to approximate the derivative.

Algorithms

Newton Raphson Method to find root of any function

Newton's Method, also known as Newton-Raphson method, named after Isaac Newton and Joseph Raphson, is a popular iterative method to find a good approximation for the root of a real-valued function f(x) = 0.