OpenGenus Tech Review Team

git

Git is a Map and SHA1 hash

Git is exactly a map data structure or more precisely a persistent map which maps blobs to hashes. We have demonstrated how Git is simply a hash map and with this view, its working is simplified.

git

Git is an Onion

Git version control is like an onion and has 4 layers namely a Distributed Revision Control System, a Revision Control System, a Simple Content Tracker and a Persistent Map. We have demonstrated its working based on the layers

bitwise operation

Algorithm to detect whether two numbers have opposite signs using bitwise operators

We present a bitwise algorithm to detect whether two numbers have opposite signs. This is important as using comparision based operations is slow and nearly all hardware support optimizations for bitwise operations

Algorithms

Maximize sum of consecutive differences in a circular array

Given an array A with values a1, a2, a3, a4, an Now, arrange all elements of array A such that sum of absolute differences of consecutive elements is maximum, i.e consider after an arrangement the array is b1, b2, b3, b4,..., bn then maximize |b1-b2| + |b2-b3| + |b3-b4| + .. + |bn-1-bn| + |bn-b1|

control statement

switch case control statement

A switch statement allows a variable to be tested for equality against a list of values. Each value is called a case, and the variable being switched on is checked for each case.if variable and case value are matched, then matched case will be executed.

control statement

for loop control statement

A for loop allows us to write a loop that is executed a specific number of times. The loop enables us to perform n number of steps together in one line. We have provided the flow diagram, syntax and example to demonstrate for loop.

control statement

do while loop control statement

A do-while loop is similar to a while loop, except the fact that it is guaranteed to execute at least one time. The do-while loop checks its condition at the bottom of the loop after one time execution of do.

control statement

While loop control statement

A while loop is a control flow statement that allows code to be executed repeatedly based on a given condition. We have provided a flow chart, syntax and programming example to demonstrate while loop

control statement

if-else control statement

if else is a programming construct/ concept for controlling the flow of program execution. The basic idea is to execute different code depending upon the outcome of an expression.

git

How Git uses Tree data structure concepts?

We have explored how Git version control system rely on Tree data structure concepts for its internal working. We have given an overview of the various important concepts in Git such as object store, index, blobs, tree, commit, tags and others.

bitwise operation

Bitwise Algorithm to Find the Number Occurring with Odd Frequency

We have explored the bitwise algorithm to find the only number occuring odd number of times in a given set of numbers. We have used the XOR operator to solve this problem in O(N) time complexity in contrast to the native algorithm which takes O(N^2) time complexity. The space complexity is constant.

Graph Algorithms

Graph Representation: Adjacency Matrix and Adjacency List

A Graph is represented in two major data structures namely Adjacency Matrix and Adjacency List. This forms the basis of every graph algorithm. In this article, we have explored the two graph data structures in depth and explain when to use one of them

bitwise operation

Maximise XOR of a given integer with a number from the given range

Given q queries each of specifies three integers x, l, r. We have to find an integer from given range [l, r] inclusive, such that it gives maximum XOR with x. All values are assumed to be positive. We will show two ways to solve this interesting problem.

Machine Learning (ML)

Artificial Neural Networks

An Artificial Neural Network is a form of computing system that vaguely resembles the biological nervous system. It is composed of very many neurons that are centres of computation and learn by a sort of hit and trial method over the course of many epochs. ANN can be seen as a network of perceptrons

Machine Learning (ML)

Restricted Boltzmann Machines

Boltzmann Machines are bidirectionally connected networks of stochastic processing units. It can be used to learn important aspects of an unknown probability distribution based on samples from the distribution. We explore Gibbs Sampling and Contrastive Divergence.

Machine Learning (ML)

Perceptron, the building block of modern AI

A perceptron is an artificial neuron that essentially receives input from an input layer, processes the input with the help of an activation function (the Heaviside step function) and gives out the output in the form of either a 0 or 1. The perceptron was invented in 1957 by Frank Rosenblatt

C Programming

Multithreading and pthread in C

In this article, we have explored how the pthread library in C can be used to implement concepts of multithreading. A thread is a single sequence stream within in a process.

C Programming

Semaphore in C

Semaphore is a data handling technique which is very useful in process synchronization and multithreading. We used the POSIX semaphore library and use the functions sem_wait, sem_post, sem_open and sem_init for implementing semaphore in C.

multiplication

Toom Cook method for multiplication

Multiplication of two n-digits integers has time complexity at worst O(n^2).Toom-Cook algorithm is an algorithm for multiplying two n digit numbers in Θ(c(k)n^e) time complexity. The idea is based on divide-and-conquer technique

matrix multiplication

Cannon’s algorithm for distributed matrix multiplication

Cannon's algorithm is a distributed algorithm for matrix multiplication for two-dimensional meshes. It is especially suitable for computers laid out in an N × N mesh. The main advantage of the algorithm is that its storage requirements remain constant and are independent of the number of processors.

matrix multiplication

Freivalds’ algorithm for verifying Matrix Multiplication

Freivalds' algorithm is a probabilistic randomized algorithm used to verify matrix multiplication. Given three n x n matrices, Freivalds' algorithm determines in O(kn^2) whether the matrices are equal for a chosen k value with a probability of failure less than 2^-k.

matrix multiplication

Russian peasant multiplication algorithm

Russian peasant multiplication is an interesting way to multiply numbers that uses a process of halving and doubling without using multiplication operator. The idea is to double the first number and halve the second number repeatedly till the second number doesn’t become 1

matrix multiplication

Strassen’s Matrix Multiplication algorithm

Strassen’s Matrix Multiplication algorithm is the first algorithm to prove that matrix multiplication can be done at a time faster than O(N^3). It utilizes the strategy of divide and conquer to reduce the number of recursive multiplication calls from 8 to 7 and hence, the improvement.

C++

Most commonly used utilities in Standard Template Library in C++

This is an overview of the most commonly used utilities in Standard Template Library in C++. We have covered Iterator, Vector, Stack, Queue, Priority Queue, Map, Set and Pair utilities.

C++

Standard Template Library in C++

Standard Template Library in C++ is a pre-defined generic implementation of most widely used data structures and algorithms. By generic implementation it means that there is a single implementation of various Classes and Functions which works with multiple datatypes by the use of templates.