39 votes

Why can't we mimic a dog's ability to smell COVID?

Addressing the hardware side of your question: A dog's sense of smell was developed through millions of years of evolution. The dog's nose is powered by hundreds of millions of organic nanomachines (...
user45623's user avatar
  • 511
39 votes
Accepted

Why can't we mimic a dog's ability to smell COVID?

We can actually detect some diseases via smell, and the term to search for is olfaction. The general problem is known as breath analysis. However, the research into olfaction and machine learning is ...
Pål GD's user avatar
  • 15.8k
15 votes

Why are Red-Black trees so popular?

I've been researching this topic recently as well, so here are my findings, but keep in mind that I am not an expert in data structures! There are some cases where you can't use B-trees at all. One ...
matklad's user avatar
  • 151
14 votes

Usefulness of binary extension field GF(2^n)

$GF(2^n)$ is used in error correcting codes, in some elements of cryptography (e.g., message authentication with 2-universal hashing), and in the AES block cipher, which is very widely used.
D.W.'s user avatar
  • 158k
10 votes
Accepted

Where can I find information on Data Structures used in common software?

Off the top of my head: Every modern operating system uses balanced binary search trees to implement the virtual memory map of a process. Windows uses splay trees, Linux and OS X use red-black trees, ...
Pseudonym's user avatar
  • 22k
7 votes

Encoding 1-out-of-n constraint for SAT solvers

A paper by Magnus Björk describes two techniques that could be worth trying. For 1-out-of-$n$, one can use both one-hot and binary encoding simultaneously. Thus, we have $x_1,\dots,x_n$ as a one-hot ...
D.W.'s user avatar
  • 158k
6 votes

Why are Red-Black trees so popular?

Well, this is not an authoritative answer, but whenever I have to code a balanced binary search tree, it's a red-black tree. There are a few reasons for this: 1) Average insertion cost is constant ...
Matt Timmermans's user avatar
5 votes
Accepted

What is the closest theory to "The theory of code refactoring"?

Basic code refactoring is not about symmetries but rather about equivalences. When code $C$ is transformed by refactoring to become code $C'$, we expect $C$ and $C'$ to "do the same thing". (...
Andrej Bauer's user avatar
  • 30.3k
5 votes
Accepted

Practical applications of the palindromic substring problem?

Lots of string-related algorithms have applications in the field of bioinformatics. Motivations for finding palindromic substrings in bioinformatics include Finding secondary structures in RNA ...
Throckmorton's user avatar
4 votes

Usefulness of binary extension field GF(2^n)

There indeed aren't a lot of situations where any binary extension field would work but no other finite field would. In fact, I can't think of any off the top of my head. Usually, you either need a ...
Ilmari Karonen's user avatar
4 votes

Is Bresenham's Line Drawing algorithm still used today?

Google Scholar reports hundreds of mentions since 2012. Specifically, the patents System and method of optical reading employing virtual scan lines (US 20100308114 A1, 2010), System and method for ...
Raphael's user avatar
  • 72.3k
3 votes
Accepted

Encoding a "not-k-out-of-n" constraint for SAT solvers

Assuming you work in CNF, construct "at least $k+1$-out-of-$n$" and add "or $p$" to each disjunction. Do the same for "at most $k-1$-out-of-$n$" and add "or $q$" to each disjunction. Then add one ...
orlp's user avatar
  • 12.9k
2 votes

Encoding 1-out-of-n constraint for SAT solvers

Here is my implementation of Kyle's answer: ...
Thomas Ahle's user avatar
1 vote

Is Bresenham's Line Drawing algorithm still used today?

This ia a bit like comparing apples and oranges. Good written Bresenham algorithm works like Wu algorithm without antialiasing. It can be used to draw lines, ellipses and circles with very high speed ...
Evil's user avatar
  • 9,445
1 vote

Examples of random deployment in wireless sensors networks

One scenario that I've heard discussed is the idea that an airplane flies over a remote area and drops wireless sensors. They fall somewhat randomly, and then need to establish a network amongst ...
D.W.'s user avatar
  • 158k
1 vote
Accepted

Maximize area of light with 4 light sources on a diagram of a room

This is an optimization problem, where a function $f: \Bbb R^8 \rightarrow \Bbb R$ is defined as an area of the visibility polygon, corresponding to four points, situated inside a polygon with holes. ...
HEKTO's user avatar
  • 3,078
1 vote

Relation/use of irrational or transcedental numbers in computer science?

On the surface that does not strike me as a high-quality paper. I wouldn't recommend it. I don't think irrational/transcendental numbers are a good approach to building PRNGs. Building PRNGs is ...
D.W.'s user avatar
  • 158k
1 vote

What are some practical problems which require the use of Kadane's algorithm?

See the Wikipedia article on the maximum subarray problem for applications to genomic sequence analysis, computer vision, and data mining.
mo2019's user avatar
  • 379
1 vote

Are Petri Nets actually used in the industry

Petri-nets are e.g. used for Businees Process Modeling with BPMN. Of course Petri Nets are an abstract idea that lends itself to modelling a wide variety of dynamic and/or distributed systems - but ...
thertweck's user avatar
  • 171
1 vote

Google's Deep Dreamer

Simply put, you: Pick a layer Forward propagate to that layer Set the gradient at that layer to the activation at that layer. Backpropagate to update the image The general idea is that you want that ...
Christabella Irwanto's user avatar
1 vote

Google's Deep Dreamer

So far nothing's been said about technical details of DeepDream. I'll fill the blank. The procedure is the following: pick some layer from the network (usually a convolutional layer), pass the ...
Maxim's user avatar
  • 640

Only top scored, non community-wiki answers of a minimum length are eligible