Software Engineering

malloc vs calloc vs realloc

We take a deep look into the 3 dynamic memory allocation techniques in C/ C++ namely malloc, calloc and realloc and explore the difference. malloc stand for memory allocations, calloc for contiguous allocation and realloc for re-allocation.

Machine Learning (ML)

Principal Component Regression (PCR)

Principal Component Regression (PCR) is an algorithm for reducing the multi-collinearity of a dataset. PCR is basically using PCA, and then performing Linear Regression on these new PCs. The key idea of how PCR aims to do this, is to use PCA on the dataset before regression.

Algorithms

Topological Sorting using Depth First Search (DFS)

We will implement Topological sorting using Depth First Search in linear time O(V+E). Topological Sorting for Directed Acyclic Graph (DAG) is a linear ordering of vertices such that for every directed edge uv, vertex u comes before v in the ordering. It is useful in instruction scheduling and other

Machine Learning (ML)

Ridge Regression

Ridge regression is an efficient regression technique that is used when we have multicollinearity or when the number of predictor variables in a set exceed the number of observations. It uses L2 regularization and solves the problem of overfitting. Concepts of overfitting and regularization is basis

Machine Learning (ML)

Model Evaluation: a crucial step in solving a machine learning problem

Models like Googlenet is used across various problems and MobileNet are designed for computational limited resources. It is a challenge to find the best technique or model for a given problem. We evaluate a model based on Test Harness, Performance Measure, Cross validation and Testing Algorithms.

Machine Learning (ML)

Summary of Regression Techniques

Regression is a technique based on statistics to model the relationship between a set of variables to make predictions on unseen data. We explored are Linear, Logistic, Polynomial, Ridge, Lasso, Elastic Net, Stepwise regression.

Machine Learning (ML)

Data augmentation Techniques

Data augmentation is the technique of increasing the size of data used for training a model. Some of position augmentation includes scaling, cropping, flipping, padding, rotation, translation, affine transformation. Color augmentation includes brightness, contrast, saturation and hue.

Software Engineering

List in Java

There is a List interface in Java which is a child interface of Collection. The List interface supports access, insertion, deletion of the elements. Each element in List has its own index, starting at 0, then 1 and so on. To create List objects we have ArrayList() LinkedList() Vector() and Stack()

Algorithms

String hashing

Hashing is an important technique which converts any object into an integer of a given range. Hashing is the key idea behind Hash Maps which provides searching in any dataset in O(1) time complexity. An efficient algorithm to hash a string is used to compare strings in O(1) time complexity

Algorithms

Fermat's little theorem, a Probabilistic test for Primality

One of the most popular probabilistic algorithm for determining if a number is prime or not is based on Fermat's little theorem. The complexity of the algorithm is O(K log N) and fails only for Carmichael numbers which are composite numbers satisfying fermat little theorem starting with 561

Software Engineering

HashMap in Java

In Java, HashMap is a Map based collection class that is used for storing Key and value pairs which is denoted as HashMap. It does not maintain order of elements, allows one null key, multiple null values, is not thread safe, default size is 16, default load factor is 0.75 JDK1.7, JDK1.8

Data Structures

Circular Queue / Ring Buffer / Circular Buffer

Circular Queue (Ring Buffer) is also a linear data structure, which follows the principle of FIFO(First In First Out), but instead of ending the queue at the last position, it again starts from the first position after the last, hence making the queue behave like a circular data structure.

Data Structures

Implementing Queue using Stack in two ways

Queue is an abstract data structure similar to Stacks. Queue is open at both its ends. One end is always used to insert data (enqueue) and the other is used to remove data (dequeue). For implementing queue using stack, one method is to make dequeue costly and other is to make enqueue costly

Data Structures

Skip List

A skip list is a data structure that is used for storing a sorted list of items with a help of hierarchy of linked lists that connect increasingly sparse subsequences of the items. A skip list allows the process of item look up in efficient manner. The time complexity of operations are O(log N)

Software Engineering

Ivan Edward Sutherland: Father of computer graphics

Ivan Edward Sutherland is a computer scientist, entrepreneur and Turing Award Winner and is regarded as the Father of Computer Graphics. He is associated with Harvard University, Massachusetts Institute of Technology and Sun Microsystems, Evans and Sutherland and Sutherland Sproull and Associates

Data Structures

Octree data structure

Octree is a tree data structure where each internal node has 8 children. An octree is generally used to represent relation between objects in a 3-dimensional space. It is used in 3D computer graphics. Octrees are also used for nearest neighbor search which can be done easily in logarithmic time.

Data Structures

Palindromic Tree (Eertree)

Palindromic tree (Eertree) is a tree based data structure that is specifically used to tackle problems involving palindromes of a string like 'longest palindrome in a string', 'count of plaindromic substrings'. It keeps track of all palindromic substrings of a string in linear time and space

Algorithms

Expectation Maximization Clustering Algorithm

Expectation Maximization Clustering algorithm is much more robust than K-Means, as it uses two parameters, Mean and Standard Deviation to define a particular cluster. This simple addition of calculating the Standard Deviation, helps the EM algorithm do well in a lot of fail cases of K-Means

Algorithms

Mean Shift Clustering Algorithm

Mean Shift clustering is an unsupervised clustering algorithm that groups data directly without being trained on labelled data. It is hierarchical in nature. It starts off with a kernel, which is basically a circular sliding window. The bandwidth the radius of this sliding window is pre-decided

Algorithms

Cartesian tree sorting

Cartesian tree sorting, also called Levcopoulos Petersson algorithm is an adaptive sorting algorithm, i.e. it performs much better on a partially sorted data. It needs two data structures a Cartesian tree and a priority queue. The algorithm here uses min-heap Cartesian tree to give a sorted sequence

Data Structures

Fusion Tree

Fusion tree is a tree data structure that implements associative array in a known universe size. Fusion trees are used to solve predecessor and successor problem. We have covered sketch, parallel comparison, predecessor and successor and insert operations in O(log N) time and O(N) space complexity

Software Engineering

Install Git on any operating system

We have covered the commands to install git for the following operating systems: Ubuntu, RHEL, OpenSUSE/ SLES/ SLED, Windows, MacOS and Fedora. Following the installation, you need to configure git to add your username and email id to get started.

Machine Learning (ML)

Autoencoder

An autoencoder is a neural network that learns data representations in an unsupervised manner. Its structure consists of Encoder, which learn the compact representation of input data, and Decoder, which decompresses it to reconstruct the input data.

Data Structures

Doubly Linked List

Doubly Linked List has the flexibility of traversing the list in both the ways i.e., forward and backward unlike singly linked list where movement is restricted in forward direction only. Doubly Linked List contains an extra pointer to link the previous node which enables the backward traversing.

Algorithms

Activity Selection Problem using Greedy algorithm

For activity selection, Dynamic Programming Approach takes O(n^3) time while Greedy Approach takes O(N) time when unsorted and O(n log n) when sorted. It follows Greedy approach as at every step, we make a choice that looks best at the moment to get the optimal solution of the complete problem