# Tagged Questions

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

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, ...
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), ...
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 ...
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? ...
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 ...
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.
30 views

### Can we simulate any dependent datatype with Eq?

Consider the canonical homogeneous equality type: Eq : (A : Set) -> A -> A -> Set, with constructor ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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. ...
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 ...
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 ...
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 ...
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? ...
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.
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.
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 - ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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. ...
45 views

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