# Tag Info

44

Yes, I would say knowing something about computational complexity is a must for any serious programmer. So long as you are not dealing with huge data sets you will be fine not knowing complexity, but if you want to write a program that tackles serious problems you need it. In your specific case, your example of finding connected components might have worked ...

27

The main answer is that by exploiting semi-group structure, we can build systems that parallelize correctly without knowing the underlying operation (the user is promising associativity). By using Monoids, we can take advantage of sparsity (we deal with a lot of sparse matrices, where almost all values are a zero in some Monoid). By using Rings, we can do ...

26

This is a rebuttal of Tom van der Zanden's answer, which states that this is a must. The thing is, most times, 50.000 times slower is not relevant (unless you work at Google of course). If the operation you do takes a microsecond or if your N is never above a certain threshold (A high portion of the coding done nowadays) it will NEVER matter. In those ...

17

Radix sorts are often, in practice, the fastest and most useful sorts on parallel machines. Zagha and Blelloch: Radix sort for vector multiprocessors. Supercomputing, 1991: 712-721. Blelloch, Leiserson, Maggs, Plaxton, Smith, and Zagha: A Comparison of Sorting Algorithms for the Connection Machine CM-2. Symp Parallel Algorithms and Arch (SPAA-3):3-16, 1991. ...

16

Yes, you are correct computers are deterministic automate. Non-deterministic models are more useful for theoretical purpose, sometime the deterministic solution is not as obvious to the definition(or say problem statement) and so little hard to find solution. Then one approach is that first design a non-deterministic model that may be comparatively easy to ...

15

Although many papers in theoretical computer science claims practical applications for their work, this is unfortunately often simply not the case. Usually, either the problems are too far away from being something useful (too simplified), or the algorithms are too far away from being practical (e.g. hiding big constants in the O-notation). However, you ...

14

Hash tables can only tell you if an element is present or not. Here are somethings you can do with a binary tree that you can't do wiht a hash table. sorted traversal of the tree find the next closest element find all elements less than or greater than a certain value See this wikipedia article on K-d trees for an example of a real world data structure ...

14

I've been developing software for about thirty years, working both as a contractor and employee, and I've been pretty successful at it. My first language was BASIC, but I quickly taught myself machine language to get decent speed out of my underpowered box. I have spent a lot of time in profilers over the years and have learned a lot about producing fast, ...

13

For the special case of k out of n variables true where k = 1, there is commander variable encoding as described in Efficient CNF Encoding for Selecting 1 to N Objects by Klieber and Kwon. Simplified: Divide the variables into small groups and add clauses that cause a commander variable's state to imply that a group of variables is either all false or all-...

13

To quote from the answer to “Traversals from the root in AVL trees and Red Black Trees” question For some kinds of binary search trees, including red-black trees but not AVL trees, the "fixes" to the tree can fairly easily be predicted on the way down and performed during a single top-down pass, making the second pass unnecessary. Such insertion ...

11

Monoids are ubiquitous in programming, just that most programmers don't know about them. Number operations like addition and multiplication. Matrix multiplication. Basically all collection-like data structures form monoids, where the monoidal operation is concatenation or union. This includes lists, sets, maps of keys to values, various kinds of trees etc. ...

11

One application domain where binary trees are better, or more easily adjustable than certain alternatives, are persistent data structures (which are often used in (purely) functional programming). A persistent data structure is a data structure that preserves the previous version of itself when it is modified. (Data structures that do not have this property ...

11

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 prominent case is std::map from C++ STL. The standard requires that insert does not invalidate existing iterators No iterators or references are invalidated....

10

You may be interested in the work on Ceptre, a result of the PhD research of Chris Martens, which uses type theory for interactive storytelling. Quoted below is the thesis abstract: Interactive storytelling weaves together deep computational ideas with humanity's rich history of story and play, providing an important context for tools and languages to be ...

10

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, and Solaris uses AVL trees. They do this because the operating system needs to store the virtual memory map in order (by virtual address), to allow for fast ...

9

The halting problem being undecidable has lots of practical relevance, here is a quick example: Writing anti-virus software is hard: We can't decide whether a given piece of code is malicious because if we could we could decide the halting problem. To see this take a piece of code which takes as input a Turing machine $M$ and an input word $w$ and does ...

9

It is more the other way around: automata arose first, as mathematical models. And nondeterminism is quite natural, you often have several paths open before you. Instead of some messy way of specifying that all paths must be followed to the end in some order, and perhaps getting bogged down by infinite branches, and... just use nondeterminism. And while ...

9

The question is quite subjective, so I think the answer is it depends. It doesn't matter that much if you work with small amounts of data. In these cases, it is usually fine to use whatever e.g. the standard library of your language offers. However, when you deal with large amounts of data, or for some other reason you insist that your program is fast, ...

9

Because of the Curry-Howard correspondence, types can be interpreted as propositions, and propositions as types. As a result of this, type theory is applicable to literally any field that uses formal logic for its proofs. This can be circuit verification, real analysis, symbolic logic, geometry, etc. For instance, some automated proof checking tools work ...

9

There has been interesting uses of type theory in linguistics. See for example the linguistic works of Chung-chieh Shan or Christian Rétoré. Quoted below is the description of Rétoré's book on categorial grammars: This book is a contemporary and comprehensive introduction to categorial grammars in the logical tradition initiated by the work of Lambek. It ...

8

Google Maps in 2009 used Contraction Hierarchies - see this tech talk. Since then, some mind-blowing methods have been discovered, capable of doing cross-country routing in fractional milliseconds - the so-called "two-hop labeling distance oracles". See here, or search for "Hub labeling" or "Shortest paths for the masses". I think I heard Bing uses this one....

7

One important problem in distributed file systems (DFS) is to generate files from distributed blocks. The area of Erasure code from information theory and Algebra (groups, rings, linear algebra,...) is used extensively in distributed fault tolerant file systems for example in HDFS RAID (Hadoop Based File System). Social network and Cloud companies are ...

7

NFAs might be used in practice, check out this answer on stackexchange. The reason is that the powerset construction can be simulated on-the-fly, so to speak. In order to simulate an NFA on a deterministic computer, we just keep track of the possible states that the NFA could be in. Typically, this number would be small, and so the simulation would be fast. ...

7

This is the arithmetic for Juho's answer. (Run it for the length of time it takes to make the algorithm failure probability equal the hardware failure probability). Suppose it takes time $t$ seconds to perform one computation, and thus time $kt$ to get the algorithm error probability down to $2^{-k}$. Suppose that the hardware probability of failure per ...

7

An interesting article that explain applications of dependent types, is the The Power of Pi, that shows how Agda can be used to solve interesting problems. Another good example is the use of dependent types to resource control. A good example is the file management API of Effects of Idris. For instance, the function for reading a line from a file has the ...

6

For the Halting Problem: Are there more than some artificially constructed cases, where one can't decide whether the algorithm will terminate or not? there are quite a few "roughly practical/applied" contexts with active research where the halting problem plays a role: automated theorem proving. proving theorems by computers runs into the same ...

6

If your question is What are examples of groups, monoids, and rings in computation? then one example I can think of off-hand is for path-finding algorithms in graph-theory. If we define a semiring with $+$ as $\min$ and $\cdot$ as $+$, then we can use matrix multiplication with the adjacency matrix to find all-pairs-shortest-path. This method is ...

6

I don't know about robotics, but ontologies are part of the standard toolkit for modern expert systems, especially those with a natural language processing component. For example, consider the process of performing literature searches for systematic reviews in medicine. Of the millions of medical studies out there, reviewers need to find the 20 or so high-...

5

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 encoding, and $y_1,\dots,y_b$ as a binary encoding, where $b = \lg n$. We can encode the "at least one" constraint easily, in a single clause: \$(x_1 \lor \...

5

I am answering one of your two questions, regarding the halting problem. First, the undecidability of the halting problem does not state that you cannot decide whether a given TM does not halt. It states that there is no general algorithm that can decide that for all TM. This is a statement about our models of what constitute computation. But, according to ...

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