Questions requesting papers in the literature on specific, narrow issues.

learn more… | top users | synonyms

0
votes
0answers
17 views

Diving right into computer science for the first time. Seeking advice [on hold]

I have a desire to start studying computer science. Actually, my initial desire is to get a taste of what it's like, but I feel that the proper way to do so is through actual learning it. However, ...
5
votes
3answers
189 views

Relationship of algorithm complexity and automata class

I have been unable to find a graph depicting or text answering the following question: Is there a direct relationship between the complexity of an algorithm (such as best / worst case of quick sort), ...
2
votes
0answers
16 views

Where does the term “Amechanicity” for type-error generation come from

I've been looking at these slides about improving type error messages for programming languages. One of the things they describe, starting at Slide 8, is the concept of amechanicity. Anytime the ...
3
votes
1answer
101 views

Where can I find an original reference for this integer square root algorithm

As an exercise, I converted an old method I learned for calculating square roots on a rotary decimal hand calculator to binary. I'm sure this is not original; can anyone provide a reference? ...
0
votes
0answers
16 views

How do I build a Tower of Hanoi simulator? [closed]

I'm a CS student in my fourth semester. I've been thinking of undertaking a minor personal project to increase things and learn on my own. And, I thought it would be great to build a simulator of a ...
-2
votes
0answers
16 views

Python to retrieve some sport [closed]

I am looking for an example on how can I retrieve data for football for current day in bet fair. Looked on the interent but not found specific programmtic examples.
5
votes
0answers
30 views

Can we simulate any dependent datatype with `Eq`?

Consider the canonical homogeneous equality type: Eq : (A : Set) -> A -> A -> Set, with constructor ...
1
vote
1answer
55 views

Can anybody suggest some algorithms for computing the edit distance other than ‎Wagner–Fischer algorithm? [closed]

I'm currently working with finding edit distance between two string of unequal length. But I'm sorry to say that I've got only one algorithm using Dynamic programming to find out edit distance. But ...
3
votes
0answers
30 views

What kind of formal language is generated by Parsing Expression Grammars?

I've been unable to find what language is recognized by PEGs. The original paper[1] only conjectures that there are some Context-Free Grammars that are unrecognizable by PEGs. It also demonstrates how ...
0
votes
1answer
19 views

In terms of the multiplicative constant, what comparison algorithm is fastest in average complexity? [closed]

It is well-known that there is an asymptotic lower bound of $nlogn$ for comparison sorting. However, I am wondering what is the fastest known algorithm for comparison sorting, in terms of the ...
1
vote
2answers
30 views

Random sampling of tuples

When I talked with students about pseudo-random number generation, I mentioned that you should not blindly use subsequent outputs of a pseudo-random number generator (PRNG) to form tuples as they may ...
8
votes
0answers
58 views

Using logic to prove non-regularity of a language

A language $L$ is regular if and only if it is definiable by a sentence in monadic second order logic (MSO) over strings (J.R. Buchi, Weak second-order arithmetic and Finite automata; Z. Math. Logik ...
1
vote
1answer
68 views

Maximize ratio of sums

I have a $2 \times n$ matrix of positive integers, where the elements are denoted by $a_{ij}$ for all $i$ in the set $\{1,2\}$ and for all $j$ in the set $\{1,\ldots,n\}$. I would like to select a ...
3
votes
2answers
32 views

Could PRNGs make use of more internal state?

In the context of our class on combinatorial algorithms we have been discussion randomness. One student said (paraphrasing): Pseudo-random number generators (PRNGs) must have a period since they ...
2
votes
0answers
25 views

Constraint solving for scheduling code with complex unspillable register classes?

I'm currently working on a compiler backend for a custom architecture which has some unusual constraints. The architecture has several super-registers with aliasing between the sub-registers, and none ...
0
votes
0answers
28 views

Pointers to schema evolution and semi-automated instance migration

QUESTION EDITED Since this question wasn't clear, I'll rephrase. See question-history for original. I'm looking for academic papers that describe schema evolution on documents (1) in a generic way. ...
1
vote
1answer
53 views

What is the Haskell-style type signature called (i.e., who is it named after)?

A type signature in Haskell is written in the following format: functionName :: (arg1Type, arg2Type) -> returnType There's a (hyphenated, after a person or ...
12
votes
3answers
254 views

Deterministic linear time algorithm to check if one array is a sorted version of the other

Consider the following problem: Input: two arrays $A$ and $B$ of length $n$, where $B$ is in sorted order. Query: do $A$ and $B$ contain the same items (with their multiplicity)? What is the ...
3
votes
0answers
314 views

What can I do with this algorithm?

Problem Statement The problem is to calculate the coefficients $A_{j_1\cdots j_n}$, of a square matrix A with size $N$ by $N$ of complex double elements, whose weighted sum with $N^2$ irreducible ...
0
votes
0answers
22 views

Who said: you need to send few messages over the network and they need to be as small as possible so that a distributed application scales up?

I wonder if there is a well known law or scientific article to cite for this. I am writing a manuscript and I am looking for the right reference. Is there something like the Amdahl's law saying that? ...
7
votes
1answer
212 views

Problems whose decidability status is unknown but known to be less hard than the halting problem

Are there problems the decidability of which is unknown but it is known for certain that the problems are less hard than the halting problem.
10
votes
5answers
1k views

What is the earliest use of “trees” in computer science?

I have a little history question, namely, as the title says, I am looking for early uses of trees (as a data structure, search tree, whatever) in computer science.
4
votes
1answer
27 views

How can I calculate optimal batch sizes for calls to an external server?

So I have a large number of commands, say 500,000, that I want to send and run on a server somewhere else, and get the answers back. All of these commands together takes a long time to execute - ...
1
vote
0answers
31 views

What are resources that I can use to learn about formal langauges?

What are some good resources for practice problems on formal languages? Every textbook I've seen contains few practice problems with even fewer answers. I would like a resource that has questions with ...
4
votes
1answer
91 views

Has connect 4 in 3D been studied in CS?

Connect 4 is a classical game in computer science. Recently I found a web game where one could play the game on a 3d board. One version can be found here ...
5
votes
0answers
45 views

Is there any recent study about percentage that computer spend on sorting?

I came across this on Art of Computer Programming long time ago Computer manufacturers of the 1960s estimated that more than 25 percent of the running time on their computers was spent on ...
0
votes
1answer
22 views

Cyber Security - recommended reading [closed]

I'm applying for a doctoral training in Cyber Security, although I come from a maths background. I've been told that my background meets the entry criteria, although for my application I would like to ...
0
votes
0answers
28 views

Looking for name of siblings-first-depth-second traversal order

I've had to come up with a traversal order/algorithm for a project, and I am wondering if it has a name. The requirements of the algorithm are: it visits the parent before the children. it visits ...
4
votes
1answer
53 views

space complexity of DFA intersection problem

the DFA-intersection computation problem, given two DFAs specified on the input, compute the intersection DFA, or the decision problem to determine its emptiness, turns out to have wider/ deeper ...
4
votes
2answers
97 views

Practical exponential time algorithms for polynomial-time solvable problems

Inspired by this quote attributed to Alan Perlis: For every polynomial-time algorithm you have, there is an exponential algorithm that I would rather run. How I interpret this statement is that ...
2
votes
0answers
20 views

What are the recent research directions in the topic of circuit lower bounds from derandomization?

I am thinking of the classical paper, https://www.cs.sfu.ca/~kabanets/Research/poly.html Can someome link to some papers/reviews that give a sampling of what are the recent thoughts in this ...
4
votes
1answer
152 views

How rule 110 would be proven to be universal if the tag system did not exist?

I was reading about Cellular Automata and I read in this question that Matthew Cook proved that rule 110 is universal, and that his proof relied upon showing how rule 110 can simulate a tag system. ...
2
votes
1answer
45 views

Maximising a particular colour in a vertex colouring

I'm looking for a paper that discusses the maximising of one colour in a vertex colouring. Suppose that for an unweighted, undirected graph $G=(V,E)$ we define a vertex colouring as a function $c : ...
1
vote
0answers
16 views

Sources on dictionary learning and related algorithms

In the context of signal processing and sparse representation of signals, there is a topic called dictionary learning which is basically about how to's of the selection of basis functions used for ...
0
votes
1answer
69 views

Is this a new compression approach?

I've come up with an idea on how to compress data. But I'm not sure if the approach already exists. I would like to know if it does already, and if so, what its name is. The approach is to: Convert ...
2
votes
0answers
46 views

Recommendation book to learn how computers work at a transistor level [closed]

I would like to know your book recommendations / popular books to learn how computers perform operations, store memory, process your mouse input to open a program for example (maybe not that ...
3
votes
1answer
71 views

NP-hardness of a scheduling problem

Problem: Given an undirected, weighted, complete graph $G = (V, E, w, c)$. $w$ is the time weight function on edges, $w:E \to \mathbb{N}^{+}$; $w(e)$ represents the time it takes to travel along edge ...
3
votes
1answer
56 views

ZK proof that I possess a ZK proof for membership in $L$?

A zero-knowledge proof system for a language $L$ is an interactive proof system where a prover $P$ (a Turing machine) tries to convince a verifier $V$ (a polynomially bounded Turing machine) in a ...
0
votes
0answers
22 views

Is there open source model of multi-agent system of consumer behavior?

I am trying to build models of consumer behavior (especially investigating the impact of advertising on purchase decisions) using multi agent systems but I wonder are there already available some open ...
3
votes
0answers
33 views

Original proof that orders eliminate deadlocks?

A well-known approach to eliminate the possibility of a deadlock when accessing exclusive ressources is enforcing a partial (or total) order in which the ressources may be requested. Which ...
4
votes
1answer
52 views

Sequence of total languages whose limit is turing complete

First let me clarify what I mean by a number of things. A language is a decidable set of natural numbers which encode functions from natural numbers to natural numbers $ \mathbb{N} \to \mathbb{N}$. A ...
1
vote
0answers
37 views

Self-learning computer science and coding [closed]

I want to learn more computer science in theory and practice. However, I really don't know where to find more practical exercises in languages like Java or Python. I feel like the best way I could ...
1
vote
1answer
76 views

Origin of the terms “safety” and “liveness” for concurrent algorithm properties?

Properties of concurrent algorithms are usually divided into two categories: Safety - something must not happen. Properties in this category are for example partial correctness and sometimes ...
5
votes
1answer
192 views

Computational complexity of finding the roots of a polyomial

I'm currently dealing with a problem for which I could show that an exact algorithm would imply a general algorithm for finding the real (but not complex) roots of an arbitrary univariate polynomial ...
2
votes
0answers
18 views

State of the art in multi-modal command recognition

I'm currently researching various fusion methods in a multi-modal (video, audio, identity, user position and gesture) human-computer interaction environment (think in terms of a smart-home system). ...
3
votes
1answer
33 views

Search problem when the effects of actions are not deterministic

The standard search problem studied in AI contains: An initial state $A$; A final (goal) state $Z$; A set of actions that can change the state; each action takes as input a certain state and returns ...
1
vote
1answer
28 views

Combining Production Rules using Reinforcement Learning

Production systems have been used to solve puzzles such as the Tower of Hanoi for years with hard-coded production rules. However, has there been any research in using reinforcement learning to ...
1
vote
0answers
22 views

Inherent complexity of testing line segment intersections with aligned and oriented bounding boxes?

It is well known that in practice, a substantial difference in run-time between algorithms for testing intersection of a line segment with aligned or oriented bounding boxes (in computer graphics ...
3
votes
1answer
40 views

Understanding the fundamentals of building an in-Memory Distributed Graph

I am working on a project where I have to build an in-memory distributed graph capturing the relation between similar files(based on some similarity metric) stored in shared file system over multiple ...
1
vote
1answer
26 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 ...