# Questions tagged [reference-request]

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

960 questions
Filter by
Sorted by
Tagged with
16 views

### Control Flow Graph - How to represent returns in code

Consider the following program int someCode1(int x){ if (x < 0) return 0; else return x; Last Statement;} Last statement could be either "printf(...
11 views

### Are there any references for this theorem of Lercher?

Let $\Delta = \lambda x.(x)x$ and consider $\Omega = (\Delta)\Delta$. Then $\Omega$ is exactly the only $\lambda$-term of the form $(\lambda x.t)v$ such that $(\lambda x.t)v=t\{v\ /\ x\}$. Does ...
19 views

### Modern standard texts on distributed systems

I'm starting a job soon that involves a large number of disciplines interacting at once. I'm knowledgeable in most of these areas; at least enough that when I don't know something I know how to look ...
32 views

### Online Taylor series calculator

When I compute the the eigenvalues of the matrix $$\begin{bmatrix}x^3& 2 + x^3& 3 - 2 x^3\\ 2 + x^3& 4 - 5 x^3& 5 + 3 x^3\\ 3 - 2 x^3& 5 + 3 x^3& x^3\end{bmatrix}$$ using ...
99 views

### Multivariate piecewise linear interpolation

I am looking for a reference to a solution of the multivariate piecewise linear interpolation. I am not quite sure how to generalize a well-known dynamic programming Segmented Least Squares algorithm. ...
36 views

### What is the anayslsis that a heap's optimal branching factor is 2 <= factor <=5?

I'm reading the book Advanced Algorithms and Data Structures and it makes the claim that the optimal branching factor for a heap is 2 <= D <= 5 and that it is ...
90 views

### Do modern computers prevent instructions being executed by audio? If so, how?

Most know that early phones and modems, and still, fax machines, sent information through the use of tones. This got me thinking - could audio be a viable vector for executing instructions by a bad ...
30 views

### Arithmetic hierarchy via oracles

My professor gave an introduction to the arithmetic hierarchy via Turing reductions, stating that, for instance, $\Sigma_2 = \text{r.e.}^\text{r.e.}$ (namely an $\text{r.e.}$ pseudocode with access to ...
25 views

### Heuristics for a variant of the traveling salesman problem

I am looking at a variant of TSP in which rather than visiting every node, there is a given collection of (possibly overlapping) subset, and the salesman must pass through one node from each subset. ...
14 views

### Intro to basic automated proof search for theorems in equational theories

I have heard about this topic, and I'm merely looking for a reference that I can read through: I know about formal logic as a proof-checking system, but I haven't yet learned about actual algorithms ...
40 views

### List of algorithms that depend on sorting / ranking / argsorting

I am looking for a list of algorithms that depends on sorting / relative ranking / argsorting, not for a list of sorting algorithms. I want to study and illustrate the importance of fast sorting in ...
97 views

### Mathematical models of computation that capture more advanced OS and CPU design features

The universal Turing machine is the standard theoretical model of a stored-program computer. While in one sense as general as possible (Turing completeness), it doesn't explicitly contain many of the ...
72 views

### Is there a book with 100 reductions?

In a lecture I'm taking about complexity theory a professor said, there are infinite many NP-complete problems. Question: I was wondering if there exists something like a database or a book with some ...
30 views

### Periodic 4D Triangulations

I am looking for references and/or algorithms for generating 4-dimensional periodic triangulations on unit 4 lattices. That is, generating a space filling triangulation of the 4D integer lattice (Z^4) ...
178 views

### Produce a Dynkin system from a finite set of finite sets

[Updated question] A Dynkin System is, provided all sets are finite, a collection of subsets of a universal set closed under complements with the universal set and closed under union of disjoint sets. ...
58 views

### what precisely do linear types prevent?

"A theory of type polymorphism in programming" introduced the Hindly-Milner type system whose punchline can be summarized "well-typed terms don’t get stuck". They do this by ...
31 views

### Using B+Tree to implement index, when the index-key size and the data-block size are of the same order

I want to implement an Index using a B+Tree as the underlying data structure. The index will have to support key sizes which are of order of my block size, what means I cannot save all the key as a ...
34 views

### Kolmogorov complexity of probability distributions, with and without time bound

Kolmogorov complexity of a string is the length of the shortest algorithm that generates it. Here I'm focusing instead on randomly distributed strings $x$, with length $n$, with a probability ...
28 views

### Counter automata with a bound on the counters?

It is widely known that emptiness of counter automata is undecidable since two counters are enough to simulate a Turing machine (see the classic book from Hopcroft and Ullman, for example). However, ...
44 views

### What is this linear optimization problem?

Given a $d$-dimensional vector $v = (v_1,\dots,v_d) \in \Bbb{R}^d$, we define $f(v) = \min_{i\in [d]} \{v_i\}$ to be the smallest coordinate of $v$. Let $v^1,\dots,v^n \in \Bbb{R}^d_{\ge 0}$ be non-...
47 views

### Filling in the image by the brain

The Cones and rods are not evenly or precisely sensitized on the retina by incoming light. Because of this, the image is formed with distortions. But the brain corrects these deformations through a ...
37 views

### Definition of static property of object in OOP

Grady Booch in Object-Oriented Analysis and Design with Applications says: The state of an object encompasses all of the (usually static) properties of the object plus the current (usually dynamic) ...
141 views

### Proving FPT is strictly contained in XP

In their book Fundamentals of Parameterized Complexity, Downey and Fellows claim (in chapter 27.1) that $\mathrm{FPT}\subsetneq \mathrm{XP}$, and that this is a "basic result" that follows ...
134 views

### A beginner book on algorithms

I am a tenth grader. I currently learnt about sorting algorithms in java in school. I started with the book "Algorithmic Mathematics" so as learn about algorithms mathematically. I know very ...