All mathematical questions about computer science, including theoretical computer science, formal methods, verification, and artificial intelligence. For questions about Turing computability, please use the (computability) tag instead. For numerical analysis, use the (numerical-methods) tag. For ...

learn more… | top users | synonyms

11
votes
0answers
348 views

How does a Lehmer Sieve work?

http://en.wikipedia.org/wiki/Lehmer_sieve Apparently a Lehmer Sieve was a mechanical device that used chains and pulleys to factor numbers and solve diophantine equations. It once was able to factor ...
11
votes
0answers
189 views

Reference on standard types

This question is about what I presume is a basic construction in type theory. The finite types are defined as follows: 0 is a finite type; if $\sigma, \tau$ are finite types, then so is ...
8
votes
0answers
171 views

How to maximize the number of operations in process

In my research project I have encountered the following problem, concerning a tuple of words in the formal language $L=\{0,1\}^*$, with $\epsilon$ denoting the empty word. If we are given an ordered ...
7
votes
0answers
218 views

Homomorphic Compression

Can there be an algorithm such that, given plaintext data P,Q, and compression function e, Such that if we treat P and Q as a number (a series of bits): $$\begin{eqnarray*}e(P + Q)& =& e(P) ...
6
votes
0answers
156 views

Calculating $\sum_{y=0}^x \Pr[Y= y] \Pr[Z\leq k-y]^2$ when Y,Z are binomially distributed?

Remark: I recently rewrote this post, hoping to get answers! I am analyzing the following experiment: Pick an $x \in \{0,\ldots,2k\}$ uniformly at random Pick $(2k+1)$-bit bitstring $b_1=(u,v_1)$ ...
5
votes
0answers
55 views

Where can I learn more about the “else” operation / “else monoid”?

(The set of natural numbers $\mathbb{N}$ starts at $0$ for me.) Let $X$ denote a set, and define $X_\bot = X \uplus \{\bot\}.$ Let $\mathbf{else}$ denote the binary operation on $X_\bot$ defined as ...
5
votes
0answers
54 views

Elementary proof of compact space = exhaustible space?

(This is a repost of a question I asked last year on cs.stackexchange.) The work of Martín Escardó has demonstrated close parallels between classical topology on one hand and computability on the ...
5
votes
0answers
158 views

How to list the prime factorised natural numbers?

Today I set out to invent a two character numeral system designed to make factorization trivial. Indeed, it lets one factor non-trivial numbers with over thousand digits within 30 seconds per hand - ...
5
votes
0answers
108 views

Are points on the complex plane sufficient to solve every solvable equation composed of the hyperoperators, their inverses, and complex numbers?

Some background: I'm programming a maths environment. I'm computer science, so please excuse any probable ignorance and lack of precision in my question. It seems $i$ and complex numbers were ...
4
votes
0answers
108 views

A problem on 0-1 matrices.

Given a 0-1 matrix $A$, is there an efficient way to find all 0-1 vectors $x$ such that $Ax = v$ where the entries of $v$ belong to a set $\{a,b\} \subseteq \mathbb{Z}$ of size $2$? Note that $v$ is ...
4
votes
0answers
81 views

This proof in my textbook involving the pumping lemma appears incorrect - is it?

It states Let $B$ be the language $\{0^n1^n2^n | n \geq 0\}$. We use the pumping lemma to prove that $B$ is not regular. The proof is by contradiction. Assume to the contrary that $B$ is regular. ...
4
votes
0answers
118 views

Computational hard math problem

Given a square filled randomly with the numbers $1$ to $N$, for instance $$\begin{array}{cccc} 16 &12 & 9 & 1\\ 11 & 3 & 4 & 7\\ 2& 8 & 5&14\\ 6& 10& ...
4
votes
0answers
475 views

How to reverse this bitwise AND-XOR encoding algorithm?

I have been given an "encoding" algorithm that does bitwise XOR and bitwise AND. Originally it's a C code that operates on integers with bit-shifts, but I have translated it into a simpler pseudocode ...
4
votes
0answers
384 views

algorithm for solving diagonal quadratic equations over real or complex numbers

I found the following statement in the paper http://www.math.uni-bonn.de/~saxena/papers/cubic-forms.pdf (page 22, in the middle): For $\mathbb F\in\{\mathbb R, \mathbb C\}$ and $b, a_i\in\mathbb ...
4
votes
0answers
133 views

Hardness of perimeter minimization?

Given $xy=C$ where $x, y$ are integer variables and $C$ is integer constant. What is the most efficient algorithm that finds $x,y$ such that $x+y$ is minimum? Providing references is highly ...
3
votes
0answers
49 views

Complexity of finding set of sets with maximum cardinality and constrained coverage.

Given a set of sets $S = \{S_1, S_2, \dots, S_n$}, let $S^{'} \subset S$ be the largest subset of S that obeys $\left| \bigcup_{S_i \in S^{'}}{S_i} \right| \leq k$. What is the complexity of finding ...
3
votes
0answers
49 views

Why is this not a poset after adding zero?

The problem    Consider the following set for divisibility. {1, 2, 3, 4, 6, 8, 12, 16, 24, 32, 96}. If 0 is added, the divisibility relation set will no longer be a poset. Please ...
3
votes
0answers
161 views

Execution time of function

At the algorithm SELECT, there is the following step: ...
3
votes
0answers
95 views

Converting a pushdown automaton (that accepts by final state) to a context-free grammar

Given the following PDA: $$ P = (\{q, p\}, \{0, 1\}, \{Z_0, X\}, \delta, q, Z_0, \{p\}) $$ where the transition function $\delta$ is given by: $$ \delta(q, 0, Z_0) = \{(q, XZ_0)\} \\ \delta(q, 0, ...
3
votes
0answers
77 views

A Tricky Quetiones on Creative Algorithm in Graph

an agent is works between n producer and m consumers. i'th producer, generate $s_i$ candy and j'th consumer, consumes $b_j$ candy, in this year. for each candy that sales, agent get 1 dollar payoff. ...
3
votes
0answers
68 views

Computability and continuous real functions

I have found somewhere the following statement: "Every computable real function has to be continuous," but I'm not able to prove it and the "proofs" that I found in some blog posts don't seem ...
3
votes
0answers
67 views

What is the desirable function identification when setting up arrows in the category of types?

My question is which functions can not be allowed in a statically typed programming language, so that the "canonical" category is less coarse than what you get if you define it's arrows to be ...
3
votes
0answers
100 views

Related paradigms in Computer Science and Mathematics

I've read in a number of places discussions on whether Mathematics is a branch of Computer Science and vice-versa (see here for example) Having a background in both, I know that the Computer Sciences ...
3
votes
0answers
78 views

Minimizing set intersection/block design

I asked this question on the CS theory stack exchange, but didn't get an answer. Was wondering whether anyone here might have some insight. Thanks in advance for any help. Given 3 parameters $s, r$ ...
3
votes
0answers
92 views

Which takes more energy: Shuffling a sorted deck or sorting a shuffled one?

You have an array of length $n$ containing $n$ distinct elements. You have access to a comparator on the elements (a black-box function that takes $a$ and $b$ and returns true if $a < b$, false ...
3
votes
0answers
80 views

Boltzmann machines - motivation for the energy function

I've been studying Boltzmann machines lately and was wondering if anyone could give me a "high-level" explanation or motivation for the energy function used: $$E = -\sum_{i<j} w_{ij} \, s_i \, s_j ...
3
votes
0answers
165 views

Binomial Coefficients optimization

Given n and R, I have to find the minimum value of k such that: $${(2^n)-1 \choose k}\bmod(2^n)==R$$ Where $k = \{0, 1, 2, \dots, 2^n-1\}$ Here ${n \choose k}$ is the binomial coefficient ...
3
votes
0answers
50 views

Covering $n$ points with fewest disks with fixed radius $\epsilon$

The title says it all. I have a set of $n$ points in $\mathbb{R^{2}}$ and I am looking for an algorithm that tells me the fewest numbers of disks of radius $\epsilon$ that cover the set of $n$ ...
3
votes
0answers
193 views

Amortized Analysis for (2,5)-Tree

I need some help with the following problem Definition: A (2,5)-tree is an external search tree, where all leaves have the same depth. Each inner node in a (2,5)-tree has at least 2, and at most 5 ...
3
votes
0answers
331 views

Constructor And\Or-graph on function transition of the alternating automata

In a And\Or-graph induced by the transition function, each node of G corresponds to a state q belonging to set Q of the state of the Automaton, for q with $\delta(q,a)=q1*q2$, the node is a $*-node$ ...
2
votes
0answers
72 views

Tree decomposition by hand for understanding

I am implementing "algorithm 2" from the paper "Treewidth computations I. Upper bounds" by Bodlander and Koster[1,page5] and I am not sure if I understand it or not. As I understand, the algoritm ...
2
votes
0answers
14 views

Determining the sequence that yields a balanced search tree in the form of a recurrence / sequence

Let's say I have a sequence of (distinct) monotonically increasing numbers S. I'll want to add them sequentially to a Binary Search Tree (BST) but as the numbers ...
2
votes
0answers
18 views

Optimality of lower bounds for Max-cut on specific graphs

The Max-Cut problem asks to find a subset $S$ of the vertices of a graph (with $m$ edges) such that the number of edges from $S$ to it's complement is as large as possible. The size $|M|$ of a max cut ...
2
votes
0answers
63 views

Trouble with induction on the length of a word

In the accepted solution of the question If L is regular, prove that $\sqrt{L}=\{w:ww\in L\}$ is regular the answerer made the claim that "What's left is to show that $δ ′ (q_{0}' ,w)=h$ , which can ...
2
votes
0answers
32 views

Hashing Probability

I have just started to learn about the topic of hashing. I understand how it works and the difference between closed address and open address, but do not know how to calculate the probability of a ...
2
votes
0answers
18 views

Compute the coefficients of a Runge-Kutta method

Let $f$ be a Lipschitz continuous function, $(a_{ij})_{1\le i,j\le s}$ and $(b_i)_{1\le i \le s}$ some real numbers, $x_0 \in \mathbb{R}$ and $h$ an arbitrary small positive number. Under some ...
2
votes
0answers
63 views

Graph Algorithm and Cycle Detection

In $O(|V|+|E|)$, we can detect whether a Directed Graph has a cycle or not. ---> True In depth-first seach on DAG, there is no Back Edge. ---> True With known Number of Edges, in $O(|V|)$ and not ...
2
votes
0answers
47 views

(Concrete) mathematical aspects of programming

It is often said that progamming is mathematics as it "makes use" of "discrete mathematics". However, I would like to ask a more concrete question: what are the concepts of a programming ...
2
votes
0answers
36 views

Decidability of given languages

Given are the following languages: $L_1 = \{0\}\\ L_2 = \{w \in \{0,1\}^{*} | L(M_w) = \{0\}\}\\ L_3 = \{w \in \{0,1\}^{*} | M_w \text{ stops at all entries }\} \\ L_4 = \{w \in \{0,1\}^{*} | ...
2
votes
0answers
65 views

What computations would advance math knowledge a lot?

Suppose we where given a super computer that would be capable of computing anything, but only for one day. We could for instance compute many of the Ramsey numbers. What would be some computations ...
2
votes
0answers
43 views

Delete nodes that satisfy a property

I want to write a function that takes as argument a pointer A to the root of a binary tree that simulates a (not necessarily binary) ordered tree. We consider that each node of the tree saves apart ...
2
votes
0answers
91 views

Traveling salesman neighborhood

I am solving some TSP problems and i got this one and i am not pretty sure about my answer. By seeing TSP as a formal combinatorial problem, i have that the Feasible solutions $F$ is the set defined ...
2
votes
0answers
96 views

How can we find the elements?

I want to describe an algorithm with time complexity $O(m)$ that, given a set $M$ with $m$ numbers and a positive integer $p \leq m$, returns the $p$ closest numbers to the median element of the set ...
2
votes
0answers
37 views

Size of increments in commutative ring to reach given number

I have the ring $\Bbb Z_q = \{0,1,\ldots,q-1\}$, where $q$ is a prime. Starting from $0$, I want to make exactly $n$ equally sized increments and reach $a\in \Bbb Z_q$, with $n<q-1$. For example if ...
2
votes
0answers
26 views

Deriving a recurrence equation and apply Master's Thrm to it

So for a function such as: function Hi(n) if n > 1 then for j ← 1 to n do print(”Hi”) Hi(n/2) Hi(n/2) Hi(n/2) It's very easy to eyeball this and get a ...
2
votes
0answers
67 views

Recursive definition of a language

Define recursively the language L of all finite strings over the alphabet Σ={a b} satisfying both criteria: All words in L contain the substring aa an odd number of times. All words in L are such ...
2
votes
0answers
85 views

Humankind knows the prime factorization of the first how many consecutive integers?

I am only looking for an approximation. I'm guessing the answer must be somewhere between $10^{20}$ and $10^{50}$. . Edit: Okay so my first initial estimation was pretty poor... I should have ...
2
votes
0answers
61 views

How to find the shortest path of a graph in a turing machine

I'm reading about Turing machine and I saw some examples as: Let $M_{1}$ a Turing Machine and the language $B = \{w\#w \vert w \in \{0,1\}^{*}\}$, We want $M_{1}$ to accept if its input is a member of ...
2
votes
0answers
83 views

Algorithm to reduce expressions to canonical form

I'm writing a small computer algebra system that only knows rational numbers and all expressions that you can get from them by using basic arithmetic operations and powers. So the expressions are ...
2
votes
0answers
43 views

Prove the big theta

I need to find a $n_0$ and $k$ for Big Oh and an $n_0$ and $k$ for Big Omega, to find a big theta bound for: $5n^2 - 9n = \theta(n^2)$ Can anyone help me and show me how to find these for this ...