OpenGenus Tech Review Team - OpenGenus IQ: Learn Algorithms, DL, System Design (Page 139)

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 Structures

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 Structures

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 (ML)

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 (ML)

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 Structures

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 Structures

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 (ML)

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 (ML)

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 (ML)

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

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

automaton

Von Neumann Cellular Automaton

Von Neumann Cellular Automaton model is the original expression of cellular automaton. It has 29 states which are the minimum for a self-replicating machine and all of which can be grouped into four categories: blank, transmission, confluent and transition states. It simulates real systems