Theoretical results and techniques applied in practical settings.

learn more… | top users | synonyms

4
votes
2answers
76 views

Real world applications for Steiner Tree Problem?

Are there real-world applications of the Steiner Tree Problem (STP)? I understand that VSLI chip design is a good application of the STP. Are there any other examples of real world problems that ...
11
votes
1answer
579 views

What is the use of finding minimum number of straight lines to cover a set of points?

There is that popular problem [1] [2] in the computer science that is finding minimum number of straight lines that covers a given set of points in 2D. Even though I have scanned many papers, none of ...
13
votes
1answer
230 views

Why are Red-Black trees so popular?

It seems that everywhere I look, data structures are being implemented using red-black trees (std::set in C++, SortedDictionary ...
3
votes
1answer
35 views

What are some interesting applications of the skyline problem?

You are given a set of $n$ rectangles in no particular order. They have varying widths and heights, but their bottom edges are collinear, so that they look like buildings on a skyline. For each ...
5
votes
2answers
83 views

Application of set theory subjects as ordinals, forcing, generic filters in software engineering

I am going to teach a course in set theory for software engineering students. I am going to talk in this course about: ordinal numbers, partial orders, well ordering, generic filters and maybe some ...
1
vote
0answers
29 views

Applications of Linked Lists [closed]

I tried looking in the internet but couldn't get any applications of linked list used in day-to-do life.Could anyone list any applications of linked list?
-4
votes
2answers
89 views

How long would it take a computer with twice the processing power to solve a polynomial time problem?

Say I have some problem of $O\left(n^k\right)$ complexity. If I were to solve the problem on a computer $x$, it would take time $t$. Now I have a new computer $x'$, which has double the computing ...
2
votes
2answers
62 views

Are device drivers state machines?

I know that device drivers are attached to device controllers, which have their own registers and some local buffer storage. I'm wondering if I can think of device drivers as little state machines -- ...
0
votes
0answers
19 views

Can Ontologies be used for defining tactics and technical features?

The generic use of ontologies is defining terms and relations between them in a specific domain. And in some cases they are used with the cognitive architectures to make intelligent agents for ...
4
votes
4answers
235 views

What are the practical uses of ontologies?

I have read many papers and books about ontologies and I am trying to figure out that how they are used in a real project? For example how the ontology for a soccer player robot can be defined and ...
23
votes
8answers
6k views

Is it a problem to be a programmer with no knowledge about computational complexity?

I've been assigned an exercise in my university. I took it home and tried to program an algorithm to solve it, it was something related to graphs, finding connected components, I guess. Then I made ...
2
votes
1answer
21 views

Prefix computation used for lexical analysis?

I'm preparing a presentation on prefix computation (aka scan, the generalization of prefix summation to any associative operator) for a class I'm taking on parallel algorithms. Several lists of ...
5
votes
1answer
180 views

Travelling with the most efficient path

A friend of mine actually asked me a very interesting computer science related question, and I have been stuck on it for a long time. The problem is: you have to travel $1000$ km. The only gas ...
1
vote
1answer
75 views

Are there some real-world optimization problems with very cheap objective functions?

Many real world optimization tasks (especially black box optimization) have objective functions, which are quite expensive to evaluate. For example to find the optimal shape of an airplane wing, a ...
5
votes
2answers
217 views

Is Dijkstras algorithm used in modern route-finding systems?

Is Dijkstra's algorithm used in modern route-finding systems such as Google maps or the satnav in your car? If not, then what is?
6
votes
1answer
46 views

Applications of model counting

I have been reading about model counting, a.k.a. the #SAT problem. What are the practical applications, if any, of this problem, and how exactly do they reduce to it? I have been unable to find any, ...
2
votes
1answer
130 views

A real-world example for a kind of real-time applications

I submitted a paper regarding hard real-time systems to an engineering journal. But the referees generally agreed my task model is too limited. My task model is a frame-based real-time application ...
7
votes
3answers
1k views

When are binary trees better than hashtables in real world applications?

I am currently bushing up on my data structures and basic algorithms, part of that is the Binary Tree. I do understand the algorithms, and how to implement a binary search tree and such. I do so how ...
3
votes
0answers
178 views

Applications of min spanning trees

What are the significant applications of minimum spanning trees? After doing some research online and in several textbooks, I have found three real-world applications: Building a connected network. ...
5
votes
2answers
128 views

Choosing error rates for probabilistic algorithms

Probabilistic algorithms often have a parameter that allows one to tune the error rate, typically by running the algorithm repeatedly. This often gives an error rate of something like $2^{-k}$ for $k$ ...
1
vote
1answer
120 views

What are practical applications of AI Planning? [closed]

note: any tips toward making this more constructive will be highly appreciated. I've dealt with ai-related problems, from searching algorithms, to computer vision, to machine learning. However none ...
8
votes
3answers
987 views

Gödels (first) incompleteness Theorem and the Halting Problem - How limiting is it?

When I first heard of these things I was very fascinated as I thought it sets really a limit to mathematics and science in general. But how practically relevant are these things? For the Halting ...
1
vote
1answer
67 views

Logic applications and security protocols references request

I'm a student of logic and I'm interested in looking at logic applications, of which I am told there are many, in computer science and allied areas. I've seen some applications. More specifically, I ...
15
votes
10answers
1k views

Why is non-determinism useful concept?

An automaton is an abstract model of a digital computer. Digital computers are completely deterministic; their state at any time is uniquely predictable from the input and the initial state. When we ...
1
vote
2answers
152 views

Applications for boolean logic operations in zero-one integer linear programming (ILP) [closed]

It is nice to know that every boolean formula can be expressed by zero-one integer programming by this answered question. But are there any applications? To be more precise: Are there papers which ...
5
votes
2answers
434 views

The Absolute Minimum Every Software Developer Absolutely, Positively Must Know about Computer Science (No Excuses!) [closed]

Yes, I borrowed the title form a famous joelonsoftware post for my question because I didn't exactly know how to ask this. I'm a professional programmer for a few years now and although I followed ...
9
votes
1answer
207 views

Universal Hashing in Practice

A family $H$ of hash functions $h: U \rightarrow \{0,\ldots,M-1\}$ is universal if $$\forall x,y \in U, x \neq y \Rightarrow \Pr_{h \in H}[h(x) = h(y)] \leq \frac{1}{M}$$ You can find more about ...
-1
votes
1answer
41 views

Is a non-perfect improvement and optimisation?

In real word problems, the influence of multiple not perfectly known factors results in using heuristics instead of mathemacial solutions that calculates a perfect value from only precisly defined ...
5
votes
2answers
105 views

Where are M-Trees applied in practice?

My similarity search seminar topic are M-trees. I would like to give some examples about where they are practically applied, but I can't find anything googling. Does someone know if M-trees are ...
10
votes
1answer
593 views

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

I'm using a SAT solver to encode a problem, and as part of the SAT instance, I have boolean variables $x_1,x_2,\dots,x_n$ where it is intended that exactly one of these should be true and the rest ...
10
votes
3answers
2k views

Practical Applications of Radix Sort

Radix sort is theoretically very fast when you know that the keys are in a certain limited range, say $n$ values in the range $[0\dots n^k -1]$ for example. If $k<\lg n$ you just convert the ...
23
votes
6answers
3k views

What use are groups, monoids, and rings in database computations?

Why would a company like Twitter be interest in algebraic concepts like groups, monoids and rings. https://github.com/twitter/algebird All I could find is: Implementations of Monoids for ...
5
votes
4answers
2k views

Trigonometry in computer science

What's the use of studying trigonometry in computer science? I mean, is it essential? Does it have a specific application in computer science? Because I can't seem to muster enough motivation for ...
5
votes
2answers
139 views

What are some applications of binary finite fields in CS?

I was looking at details on finite fields. Finite binary fields, e.g. $\mathbb{F_2}$, are used in CS in some places such as circuit theory [1]. What are some key applications of finite fields in ...
10
votes
1answer
157 views

Natural occurrences of monads that make use of the category-theoretical framework

Today, a talk by Henning Kerstan ("Trace Semantics for Probabilistic Transition Systems") confronted me with category theory for the first time. He has built a theoretical framework for describing ...
25
votes
9answers
2k views

What is the significance of context-sensitive (Type 1) languages?

Seeing that in the Chomsky Hierarchy Type 3 languages can be recognised by a state machine with no external memory (i.e., a finite automaton), Type 2 by a state machine with a single stack (i.e. a ...