Algorithms *

• we find all the image defects: fractures, scuffs, holes;
  
• we inpaint the discovered defects, based on the pixel values around them;
  
• we colorize the image.
  

Introduction

Our project implements a real-time edge detection system based on capturing image frames from an OV7670 camera and streaming them to a VGA monitor after applying a grayscale filter and Sobel operator. Our design is built on a Cyclone IV FPGA board which enables us to optimize the performance using the powerful features of the low-level hardware and parallel computations which is important to meet the requirements of the real-time system.

We used ZEOWAA FPGA development board which is based on Cyclone IV (EP4CE6E22C8N). Also, we used Quartus Prime Lite Edition as a development environment and Verilog HDL as a programming language. In addition, we used the built-in VGA interface to drive the VGA monitor, and GPIO (General Pins for Input and Output) to connect the external hardware with our board.

(Elliptic Curve) Diffie-Hellman (Ephemeral)

In this article I will explain a texture splatting algorithm which allows you to create more natural terrain. This algorithm may be used in shaders of 3D games as well as in 2D games.

The original post has been updated based on community input in order to remove confusion.

Final version of the whitepaper is available here:

https://github.com/cybercongress/cyber/releases

The Art of Designing Road Networks

Transport problems of a city through the eyes of a Computer Scientist

On implementing streaming algorithms, counting of events often occurs, where an event means something like a packet arrival or a connection establishment. Since the number of events is large, the available memory can become a bottleneck: an ordinary -bit counter allows to take into account no more than events.
One way to handle a larger range of values using the same amount of memory would be approximate counting. This article provides an overview of the well-known Morris algorithm and some generalizations of it.

Another way to reduce the number of bits required for counting mass events is to use decay. We discuss such an approach here [3], and we are going to publish another blog post on this particular topic shortly.

In the beginning of this article, we analyse one straightforward probabilistic calculation algorithm and highlight its shortcomings (Section 2). Then (Section 3), we describe the algorithm proposed by Robert Morris in 1978 and indicate its most essential properties and advantages. For most non-trivial formulas and statements, the text contains our proofs, the demanding reader can find them in the inserts. In the following three sections, we outline valuable extensions of the classic algorithm: you can learn what Morris's counters and exponential decay have in common, how to improve the accuracy by sacrificing the maximum value, and how to handle weighted events efficiently.

Manual lung segmentation takes about 10 minutes and it requires a certain skill to get the same high-quality result as with automatic segmentation. Automatic segmentation takes about 15 seconds.

I assumed that without a neural network it would be possible to get an accuracy of no more than 70%. I also assumed, that morphological operations are only the preparation of an image for more complex algorithms. But as a result of processing of those, although few, 40 samples of tomographic data on hand, the algorithm segmented the lungs without errors. Moreover, after testing in the first five cases, the algorithm didn’t change significantly and correctly worked on the other 35 studies without changing the settings.

Also, neural networks have a disadvantage — for their training we need hundreds of training samples of lungs, which need to be marked up manually.

The life of Langton's Ant seems sad and lonely, but, as we'll soon discover, he is not ready to put up with such an outrageous situation and is trying his best to escape. American scientist Christopher Langton invented his ant back in 1986. Since then, no one has been able to explain the strange behavior of this mysterious model...

The flag of the Netherlands consists of three colors: red, white and blue. Given balls of these three colors arranged randomly in a line (it does not matter how many balls there are), the task is to arrange them such that all balls of the same color are together and their collective color groups are in the correct order.

For simplicity instead of colors red, white, and blue we will be dealing with ones, twos and zeroes.

Let's start with our intuition. We have an array of zeroth, ones, and twos. How would we sort it? Well, we could put aside all zeroes into some bucket, all ones into another bucket, and all twos into the third. Then we can fetch all items from the first bucket, then from the second, and from the last bucket, and restore all the items. This approach is perfectly fine and has a great performance. We touch all the elements when we iterate through the array, and then we iterate through all the elements once more when we "reassamble" the array. So, the overall time complexity is O(n) + O(n) ~= O(n). The space complexity is also O(n) as we need to store all items in the buckets.

Can we do better than that? There is no way to improve our time complexity. However, we can think of a more efficient algorithm in regard to space complexity. How would we solve the problem without the additional buckets?

Let's make a leap of faith and pretend that somehow we were able to process a part of the array. We iterate through part of the array and put encountered zeroes and ones at the beginning of the array, and twos at the end of the array. Now, we switched to the next index i with some unprocessed value x. What should we do there?

After 210 days, 600 commits, tens of debugging nights, and thousands of messages in the project chat, I finally released AngouriMath 1.2.

This is an open-source symbolic algebra library for C# and F#, maybe it is interesting for someone?

The traditional definition for the operation of exponentiation to a natural power (or a positive integer) had introduced approximately as follows:

Exponentiation is an arithmetic operation originally defined as the result of multiple multiplications a number by itself.

But the more precise formulation is still different:

Raising a number X to an integer power N is an arithmetic operation defined as the result of multiple [N by mod times] multiplications or divisions one by number X.

1. About this series of articles

1.1 Central result

Most solutions to algorithmic problems can be grouped into a rather small number of patterns. When we start to solve some problem, we need to think about how we would classify them. For example, can we apply fast and slow аlgorithmic pattern or do we need to use cyclic sortpattern? Some of the problems have several solutions based on different patterns. In this series, we discuss the most popular algorithmic patterns that cover more than 90% of the usual problems.

It is different from High-School Algorithms 101 Course, as it is not intended to cover things like Karatsuba algorithm (fast multiplication algorithm) or prove different methods of sorting. Instead, Algorithmic Patterns focused on practical skills needed for the solution of common problems. For example, when we set up a Prometheus alert for high request latency we are dealing with Sliding Window Pattern. Or let say, we organize a team event and need to find an available time slot for every participant. At the first glance, it is not obvious that in this case, we are actually solving an algorithmic problem. Actually, during our day we usually solve a bunch of algorithmic problems without realizing that we dealing with algorithms.

The knowledge about Algorithmic Patterns helps one to classify a problem and then apply the appropriate method.

But probably most importantly learning algorithmic patterns boost general programming skills. It is especially helpful when you are debugging some production code, as it trains you to understand the execution flow.

Patterns covered so far:

Sliding Window I

Sliding Window II

Merge Intervals

Dutch National Flag

Matrix Spiral

Iterative Postorder Traversal

Bit Manipulation

Stay tuned :)

<Promo> If you interested to work as a backend engineer, there is an open position in my squad. Prior knowledge of Golang is not required. I am NOT an HR and DO NOT represent the company in any capacity. However, I can share my personal experience as a backend engineer working in the company. </Promo>