Piyush Rajendra Chaudhari - OpenGenus IQ: Learn Algorithms, DL, System Design

Classification of CPU Scheduling Algorithms

There are two types of CPU scheduling algorithms namely Preemptive Scheduling Algorithm and Non-preemptive Scheduling Algorithm.

Algorithms

Carmichael Number

Carmichael Number is an odd composite number which follows the following condition applicable in Fermat's Little Theorem.

Software Engineering

Non-Preemptive Priority CPU Scheduling Algorithm

In Non-preemptive Priority CPU Scheduling Algorithm, processes are scheduled as per the priorities assigned to respective task and next process is not schedule until and unless current execution of process is not completely finished.

Software Engineering

First Come First Serve CPU Scheduling Algorithm

First Come First Serve (FCFS) is also known as First In First Out (FIFO) scheduling algorithm is the easiest and simplest CPU scheduling algorithm where the process which arrives first in the ready queue is executed first by the CPU.

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

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 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 Lexicographical Next Permutation in O(N) time complexity

In Lexicographical Permutation Algorithm we will find the immediate next smallest Integer number or sequence permutation. Finding all permutations take O(N!) time complexity but we present an efficient algorithm which can solve this in O(N) time complexity

Algorithms

Heap’s algorithm for generating permutations

Heap's Algorithm is used to generate all the possible permutation of n-decimals of a number. It generates each permutation from the previous one by interchanging a single pair of elements; the other n−2 elements are not disturbed. For N numbers, it takes O(N!) time complexity

C++

Stack in C++ STL

Stack in the STL of C++ is a dynamically resizing container. Stack class is an container adapter. Containers or container classes store objects and data. There are in total seven standard "first-class" container classes and three container adaptor classes and only seven header files

Algorithms

Distance between two points in 2D space

Distance between two points is calculated by creating a right-angled triangle using the two points.The line between the two points is the hypotenuse (the longest side, opposite to the 90° angle). We used the Distance formula derived from Pythagorean theorem with a time complexity of O((log N)^2)

Algorithms

Area of Polygon: Shoelace formula

Given coordinates of vertices of polygon, Area of Polygon is calculated using Shoelace formula described by Mathematician and Physicist Carl Friedrich Gauss where polygon vertices are described by their Cartesian coordinates in the Cartesian plane. The time complexity is O(N) with O(1) space

Algorithms

Area of Triangle: Heron's formula

We take a look at Heron's formula which will enable us to calculate the area of any triangle given the length of the three sides of that triangle. The advantage is that the area is calculated using arithmetic operations and hence, the time taken can be assumed to be constant,

Algorithms

Conversion of Infix to Postfix Expression using Stack

To convert Infix expression to Postfix expression, we will use the stack data structure. By scanning the infix expression from left to right,if we get any operand, simply add it to the postfix form, and for the operator and parenthesis, add them in the stack maintaining the precedence of them.

Algorithms

Bresenham Line Drawing Algorithm

Bresenham line drawing Algorithm is a Line Drawing Algorithm which calculates all intermediate points over the interval between start and end points, implemented with integer numbers and integer arithmetic such as addition, subtraction and avoids heavy operations like multiplication and division

Algorithms

DDA (Digital Differential Analyzer) Line Drawing Algorithm

Digital differential analyzer is a line drawing algorithm that is based on incremental method which calculates all intermediate points over the interval between start and end points. It uses the concept that rate of change in a straight line in constant and is a linear time complexity O(N) algorithm

Algorithms

Bresenham’s Circle Drawing Algorithm

Bresenham’s Circle Drawing Algorithm is a circle drawing algorithm that selects the nearest pixel position to complete the arc. The unique part of this algorithm is that is does only integer arithmetic which makes it faster than other algorithms using floating point arithmetic

Algorithms

Cohen Sutherland Line Clipping Algorithm

Cohen Sutherland Algorithm is a linear time complexity line clipping algorithm that cuts lines to portions which are within a rectangular area. It eliminates the lines from a given set of lines which belongs outside the area of interest and clip those lines which are partially inside