OpenGenus Foundation - OpenGenus IQ

Longest Palindromic Subsequence: Reducing complexity from O(2^N) to O(N^2)

The longest palindrome subsequence problem (LPS) is the problem to find longest subsequences of a string that is also a palindrome. We will see two solutions one which is a naive solution and the other is a dynamic programming approach where we will reduce the time complexity from O(2^N) to O(N^2)

sorting algorithm

Comb Sort

Comb sort is a comparison based sorting algorithm and is an improvement to Bubble Sort by using the idea of killing the turtles. In Bubble Sort algorithm, the gap between the elements that are compared is always 1. Comb sort works on the same principles as Bubble Sort but uses a larger gap.

dynamic programming

Longest Bitonic Sequence

The problem we will solve is given a sequence an array of positive integers and have to find the length of longest bitonic subsequence. Using dynamic programming ideas, we will solve this on O(N^2) time complexity

sorting algorithm

Heap Sort

Heapsort is an efficient in-place comparison based sorting algorithm with O(N log N) time complexity and uses a data structure to achieve it. It uses a complete Binary Heap data structure to sort the elements depending on whether the heap is Min Heap (ascending) or Max heap (descending).

sorting algorithm

Radix Sort

Radix Sort is an efficient non-comparison based sorting algorithm which can sort a dataset in linear O(N) time complexity and hence, can be better than Quick Sort. It uses Counting Sort as a subroutine. It uses the fact that number of digits in an Integer is very less compared to the data

automaton

John Conway's Game of Life

The Game of Life is a cellular automaton created in 1970 by the British mathematician John Horton Conway. The game is a zero-player game, where you include an initial input and watch how the board evolve through the generations and if the life will prosper or will be extinct over time.

data structure

Van Emde Boas tree

Van Emde Boas tree is a tree data structure which implements an associative array with m-bit integer keys. It performs all operations (insert, delete, lookup, maximum, minimum, successor and predecessor) in O(log log M) time, where M is the maximum number of elements that can be stored in the tree.

sorting algorithm

Counting Sort

Counting sort is an algorithm for sorting integers in linear time. It can perform better than other efficient algorithms like Quick Sort, if the range of the input data is very small compared to the number of input data. It is a stable, non-comparison and non-recursive based sorting

algorithm

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

sorting algorithm

Bucket Sort Algorithm

Bucket sort is a comparison sort algorithm that works by distributing the elements of an array into a number of buckets and then each bucket is sorted individually using a separate sorting algorithm. It is useful when the input is uniformly distributed over a range in linear time complexity

data structure

Queue

Queue is a linear data structure that can be used to store data in order by imposing rules on data insertion and deletion. It has found immense use and can be implemented using arrays and linked lists. The operations include enqueue and dequeue which are of O(1) time complexity with space of O(N)

algorithm

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

data structure

Y fast trie

Y-fast trie is a data structure used to store integers from a bounded domain. It has two data structures X fast trie and balanced binary search tree with the change being we operate on representative values r in X-fast tries, and the leaf nodes point to balanced binary search trees instead of values

data structure

X-fast trie

X-fast trie is a data structure used to store integers from a bounded domain. It is a bitwise trie, i.e. a binary tree where each subtree stores values having binary representations with common prefix. It is a trie of hash tables and supports successor and predecessor operations in log log U time

cyber security

SamSam Ransomware: made $850K by attacking government organizations

SamSam Ransomware uses a custom infection in targeted attacks and the ransomware have been made by SamSam group. The ransomware has been publically available since 2015 and has been known for targeting government entities in USA. The ransomware is developed privately and modernized regularly

cyber security

Jigsaw Ransomware: Pay $150 in bitcoin with live support or get files deleted

Jigsaw Ransomware (BitcoinBlackmailer) targets Microsoft Windows first appeared in 2016. The ransomware is desgined to spread through malicious attachments in spam emails. It not only encrypts the user's files but also deletes them if the user takes too long to make the ransom payment of $150

machine learning

Fully Connected Layer: The brute force layer of a Machine Learning model

Fully Connected layers in a neural networks are those layers where all the inputs from one layer are connected to every activation unit of the next layer. In most popular machine learning models, the last few layers are full connected layers which compiles the data extracted by previous layers

machine learning

Convolution Layer: The layer that takes over 70% of time in a Machine Learning model

Convolutional Layer is the most important layer in a Machine Learning model where the important features from the input are extracted and where most of the computational time (>=70% of the total inference time) is spent. Concepts involved are kernel size, padding, feature map and strides

data structure

AVL Tree: A tree that can stay balanced by rotating

An AVL Tree (Adelson-Velsky and Landis tree) is a self balancing binary search tree such that for every internal node of the tree the heights of the children of node can differ by at most 1. It uses four types of rotations to keep itself balanced and delete, insert and search take O(log N) time

computer architecture

Graphics Processing Unit (GPU) vs Tensor Processing Unit (TPU) vs Field Programmable Gate Arrays (FPGA)

Graphics Processing Unit (GPU), Tensor Processing Unit (TPU) and Field Programmable Gate Array (FPGA) are processors with a specialized purpose and architecture. We have compared these in respect to Memory Subsystem Architecture, Compute Primitive, Performance, Purpose, Usage and Manufacturers.

data structure

Treap / Randomized cartesian tree

A treap is a height balanced binary tree with heap properties. It is used to store a sequence in a tree, which allows for various applications like searching. It takes O(log N) time complexity for search, insert and delete operations and takes O(N) space complexity

clustering algorithm

K+ Means Clustering algorithm

K+ Means algorithm is a clustering algorithm and an improvement to K means clustering algorithm and solves the problem of choosing K (number of clusters). It is great at detecting outliers and forming new clusters. The complexity is O(t*(k^2)*n) which is slightly more than K means algorithm

machine learning

Types of Data Formats in Machine Learning

Each data format represents how the input data is represented in memory. This is important as each machine learning application performs well for a particular data format and worse for others. Various data formats are NHWC, NCHW, NCDHW and NDHWC

machine learning

Types of Loss Functions in Machine Learning

The various types of loss functions are mean_squared_error, mean_absolute_error, mean_absolute_percentage_error, mean_squared_logarithmic_error, squared_hinge, hinge, categorical_hinge, logcosh, categorical_crossentropy, sparse categorical / binary crossentropy, kullback_leibler_divergence and other

machine learning

Bayesian model

A Bayesian model is a statistical model where we use probability to represent both the uncertainty regarding the output and input to the model. The basic idea is that we start by assuming something which is adjusted based upon input data. We look into Bayesian Linear Regression as well