42

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 ...


19

The context-sensitive languages are exactly the languages that can be recognized by a Turing machine using linear space and non-determinism. You can simulate such a Turing machine using exponential time, so you can recognize any such language in exponential time. Do note that the problem of recognizing some context-sensitive languages is $PSPACE$-complete, ...


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

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. ...


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

Rotations: that arise in Computer Graphics and Robotics , through rotation matrices, Quaternions, etc. Cordics for computing these functions on a Microprocessor / FPGA Transforms in Image Compression and elsewhere , e.g. FFT computation in $O(n \log n)$ time Anything to do with the interface between CS and Signal Processing Pretty much anywhere in ...


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, ...


12

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-...


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

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 ...


10

Generally speaking, you usually want to know the smaller class to which a given language $L$ belongs. This is because smaller classes can be recognized/accepted/generated by simpler mechanisms (automata, grammars, regular expressions, etc.), which is desirable. For example, the class of regular languages has good closure properties, and given a DFA $\...


10

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

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 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

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

In context-free languages, at any point of the input parsing, the automaton is in a state defined by its stack. Each production has the same behaviour in consuming the input regardless of where it is used. This leads to the interesting property that each production generates a sub-language of the one generated by the ones that are deeper in the stack and ...


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

Closure Properties Of all language classes from the Chomsky hierarchy, only regular and context-sensitive languages are closed under complementation. Hence this is a sort of unique feature of context-sensitive languages. In contrast to context-free languages, CS are also closed under intersection and shuffle product.


7

Finite fields come up in many places. Here are just a few examples: The Razborov-Smolensky polynomial method. Fourier analysis, as used for example in the proof of the PCP theorem, or fast integer multiplication. List decoding - codes like Reed-Muller are algebraic codes. Algebraization, the method used to prove IP=PSPACE. Elliptic curves over finite fields ...


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 ...


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