43

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


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


12

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

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

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

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

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

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

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

Asking whether an occurrence of monad is natural is similar to asking whether a group (in the sense of group theory) is natural. Once you formalise something, in this case as an endofunctor, either it satisfies the axioms of being a monad or not. If it does satisfy the axioms, then one gets a lot of technical machinery for free. Moggi's paper Notions of ...


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


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