Algorithm tutorial

Smallest number with all numbers from 1 to N as multiples

We will find the smallest number that is perfectly divisible by all numbers from 1 to N and used 3 approaches: Brute force O(N^3 * log N), using prime factorization O(N * log N * log N) and using insights into the problem O(N * log log N).

algorithm

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.

algorithm

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.

algorithm

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.

algorithm

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.

algorithm

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.

algorithm

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

algorithm

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.

algorithm

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)

algorithm

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)

algorithm

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

algorithm

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.

software engineering

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.

algorithm

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

algorithm

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)

algorithm

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)

algorithm

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

algorithm

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.

algorithm

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.

algorithm

Calculating Permutation Coefficient

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

algorithm

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

algorithm

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.

algorithm

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.

algorithm

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.