Skip to main content
Share Your Experience: Take the 2024 Developer Survey

Questions tagged [applied-theory]

Theoretical results and techniques applied in practical settings.

Filter by
Sorted by
Tagged with
0 votes
0 answers
21 views

Is super-exponential complexity useful in practice?

Exponential time-complexity has a useful application in "practical" CS: NP-problems, NP-complete problems. Knowledge about this obviously helps in everyday programming. Can you give an ...
porton's user avatar
  • 493
9 votes
2 answers
812 views

Usefulness of binary extension field GF(2^n)

The binary extension field, usually denoted as $\textsf{GF}(2^n)$ or $\mathbb{F}_{2^n}$, is a finite field of characteristic 2. Are there any applications of $\textsf{GF}(2^n)$ (or more broadly, $\...
Tianren Liu's user avatar
2 votes
1 answer
105 views

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

We refactor code lots of times as developers. Metaphorically, our program space is an infinite-dimensional Rubik's cube. Things can be rearranged, preserving the code's action, so a "symmetry ...
HighAsAKiteOnMath's user avatar
0 votes
0 answers
24 views

Solving the constraint portion of the input-encoding problem

The "input-encoding problem" is where the binary representations of symbolic input variables to a Boolean function are chosen to minimize the decode logic complexity. The "Espresso-MV&...
MattyZ's user avatar
  • 101
1 vote
0 answers
43 views

Is there a known FPRAS for this simple partition function?

I Let $G$ be the set of simple graphs on $n$ nodes. Given a $g \in G$, we denote the number of triangles in $g$ with $n(g)$. Given some positive real-valued parameter $w$, we define the the function $...
SagarM's user avatar
  • 173
1 vote
1 answer
119 views

How to model an inverse "token relationship" in Petri nets?

Suppose I have the following Petri net: I wonder whether it is possible to model an inverse relationship between $p2$ and $p3$. Basically what I want to achieve is to make either $t1$ or $t2$ ...
user3475602's user avatar
29 votes
4 answers
9k views

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

As far as I can tell, we have invented tools and algorithm to: Detect a wider range of colors at a larger range than humans or any other animals on the planet Detect sound with wavelengths ...
jonjbar's user avatar
  • 408
1 vote
1 answer
36 views

Examples of random deployment in wireless sensors networks

I have been doing some research and have found a lot of papers on the subject of random deployment in wireless sensor networks, but I haven't found a single example of its usage. Has it been used ...
Florentin Labelle's user avatar
5 votes
1 answer
90 views

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

Given a diagram of a room with obstacles in it (like walls or furniture), find the 4 best places to put omnidirectional light sources in it so the area that is lighted is maximized. Here is a simple ...
loot's user avatar
  • 53
1 vote
2 answers
36 views

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

I'm wodering about the relationship between the theory that studies irrational/transcendental numbers and computer science. For example, I found this paper (but was unable to get the full text) Pseudo-...
Pinteco's user avatar
  • 151
2 votes
0 answers
73 views

Sample applications based on First Order Logic

I often hear about benefits of FOL, but I wonder what are some of its real world applications? Could someone please provide samples/case studies of applications of FOL that address real world ...
User 19826's user avatar
1 vote
1 answer
619 views

Practical applications of the palindromic substring problem?

The longest palindromic substring problem is certainly an interesting intellectual exercise, and seems to be popular in coding interviews in industry. As an interesting puzzle, its popularity for ...
Logan R. Kearsley's user avatar
1 vote
1 answer
128 views

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

I'm finding myself needing to encode a "not-k-out-of-n" constraint in a SAT solver. The "at-most-k-out-of-n" constraint for SAT solvers is something I can find research about -- this paper by Frisch ...
onigame's user avatar
  • 203
2 votes
1 answer
151 views

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

I've worked through Kadane's and love its elegance. I am worried though, unless asked specifically about arrays and it's obvious that's what's for dinner, I won't know to use it. What are some real-...
dsp_099's user avatar
  • 121
1 vote
0 answers
80 views

Law as a computer science problem?

For a long time, computer scientists and logicians have noticed that law (statutes, contracts, adjudication, etc), has some similarity with formal logic and programming languages, and have approached ...
user83014's user avatar
2 votes
1 answer
2k views

Are Petri Nets actually used in the industry

I'm having a hard time finding any prominent applications of Petri nets in the industry. Can you name some, or are Petri nets still just an academic curiosity?
jnalanko's user avatar
  • 577
0 votes
1 answer
50 views

Need introductory guide to cellular automata for geographic automata systems

I would like to work on urbanisation and I've read that cellular automata has potential use on model urban sprawl. However I need some kind of introductory to cellular automata in order to tackle an ...
Joachim's user avatar
6 votes
1 answer
216 views

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

As part of a course I am teaching on Data Structures, I want students to research and present the use of Data Structures in popular software/services. However, basic googling shows me that this ...
wsaleem's user avatar
  • 581
3 votes
0 answers
3k views

What are some applications of 2 stack pushdown automata?

What are some real world application for 2 stack pushdown automata, as i can only find pushdown automata applications in the internet
Angeline J. Tan's user avatar
2 votes
1 answer
367 views

Assumptions when selecting an algorithm or data structure [closed]

As I understand it the nature of data access (sequential or random) will determine the optimal algorithm/data structure to use when manipulating data. What other assumptions need to be checked before ...
52d6c6af's user avatar
  • 320
14 votes
5 answers
3k views

Daily Applications of Type Theory

I want to understand type theory but I have to know first how I can apply it. Could there be more non-obvious applications of type theory aside from in type systems in programming? Could there be ...
damat-perdigannat's user avatar
3 votes
2 answers
2k views

Is Bresenham's Line Drawing algorithm still used today?

If so, I cannot find any examples of this. Edit: By "used", I mean are they still used in rendering in games or whatever. I haven't seen it used anywhere except in MS Paint because Wu's algorithm ...
Dylanthepiguy's user avatar
2 votes
1 answer
53 views

Have block edit distances been computed on large code bases?

There is an enormous mass of source code in this world, and I think it's safe to say that most of this source code was once copied from elsewhere, then modified. There is a decent chance of the (small,...
reinierpost's user avatar
  • 5,694
1 vote
5 answers
664 views

Google's Deep Dreamer

I was just wondering on a more technical side, if anyone could explain what Google does to create these amazing images from it's deep dream system. Could anyone explain to me in a step by step way, ...
George's user avatar
  • 67
0 votes
0 answers
104 views

Rules language / DSL expressivity measure

Languages to express domain rules are quite diverse from very simple and inexpressive to Turing-complete programming languages. If we consider developing some DSL (domain-specific language), is there ...
Roman Susi's user avatar
9 votes
3 answers
3k 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 ...
guskenny83's user avatar
12 votes
1 answer
1k 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 ...
padawan's user avatar
  • 1,435
63 votes
4 answers
20k 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 ...
Jakub Arnold's user avatar
6 votes
1 answer
874 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 ...
jsguy's user avatar
  • 629
5 votes
2 answers
824 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 ...
user135172's user avatar
-3 votes
2 answers
1k 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 ...
JibbyJames's user avatar
2 votes
2 answers
770 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 -- ...
Eli Rose's user avatar
  • 440
8 votes
5 answers
4k 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 ...
Freelancer's user avatar
2 votes
0 answers
195 views

Practical implications of strongly polynomial time algorithm for linear programming

Why do people care about whether a strongly polynomial time algorithm for linear programming exists or not? Does this have any practical improvement?
testy's user avatar
  • 199
30 votes
8 answers
8k 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 ...
Red Banana's user avatar
2 votes
1 answer
107 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 ...
ShadSterling's user avatar
7 votes
1 answer
379 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 ...
HenryHey's user avatar
  • 140
1 vote
1 answer
599 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 ...
Martin Drozdik's user avatar
10 votes
2 answers
8k 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?
chopper draw lion4's user avatar
8 votes
1 answer
173 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, ...
Elliot Gorokhovsky's user avatar
2 votes
1 answer
2k 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 ...
Code's user avatar
  • 37
7 votes
3 answers
7k 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 ...
Androme's user avatar
  • 207
3 votes
0 answers
4k 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. ...
D.W.'s user avatar
  • 161k
3 votes
2 answers
538 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$ ...
David Richerby's user avatar
2 votes
1 answer
982 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 ...
Iancovici's user avatar
  • 665
8 votes
3 answers
1k 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 ...
Nocta's user avatar
  • 121
1 vote
1 answer
84 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 ...
لويس العرب's user avatar
28 votes
10 answers
13k views

Why is non-determinism a 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 ...
Tanmoy Banerjee's user avatar
1 vote
2 answers
675 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 ...
user avatar
5 votes
2 answers
717 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 ...
John's user avatar
  • 59