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

3
votes
1answer
104 views

Balls on Stairs

Recently I realized that lost all computing skill in probability. Please take a look at the following problem. There are $b$ balls that are thrown one by one and bounce from top to bottom on the $n$ ...
0
votes
1answer
102 views

Is it properly applied the Quine McCluskey algorithm by this?

I'm writing some code for implementing the Quine McCluskey algorithm and I simply need to clear out if my logic for implementation is ok. I get some number of minterms and combine each of them so ...
0
votes
1answer
59 views

problem understanding a solution of Talbot's book (complexity and cryptography)

There's a question which is answered at the end of the book, but I have problem understanding the answer, my own understanding is that its lower bound would be $n^2$ as well. A palindrome is a a ...
4
votes
1answer
80 views

Any work on Automated theorem proving by Pattern Recognition?

Are there some mathematicians or papers about Advanced ATP by Pattern recognition? Pattern recognition: recognize the patter from mathematic sentence, proof sequence.
3
votes
1answer
53 views

the time required to decide $L$

Suppose that a language $L$ is decided in space $S(n)$ by a DTM with alphabet  $\Sigma$ and set of states $\Gamma$. What upper bound can you give for the time required to decide $L$?
1
vote
1answer
56 views

what is the meaning of “vector” in the context of algorithms?

I'm familiar with the concept of vectors in math and physics, but this wording in a computer science textbook is unfamiliar to me. A configuration in the shared memory model is a vector ...
1
vote
0answers
200 views

How to Diagonalize an Extremely Large Sparse Matrix in SLEPc/PETSc

Dear Friends, Recently I have started with learning SLEPc/PETSc, but I didn't find a way to solve my problem. I have to solve a big sparse matrix which is a two dimensional quantum ...
0
votes
1answer
84 views

Postfix notation in MAPLE

I usually use MATHEMATICA as a computer algebra system and there I heavily employ the postfix notation (achieved by "//" at the end of some command), e.g. ...
1
vote
1answer
602 views

Prim's algorithm

Given a connected, directed and weighted graph, Prim's algorithm may not necessarily generate the minimal spanning tree. Suppose we have such a graph $G$ with the special condition that for every pair ...
1
vote
2answers
91 views

What's the term for a value x that satisfies the constraint $f(x) = f$ for a function f?

I know that $x$ is called the fixed point of a function $f$ if it satisfies the constraint $f(x) = x$. However, for a function $f$ if there exists some value $x$ such that $f(x) = f$ then what is the ...
0
votes
1answer
373 views

Integer Linear Programming (ILP): NP-hard vs. NP-complete?

I was thinking about examples where a problem is NP-hard but was not NP-complete and ILP came to mind. It is obviously NP-hard but is it NP-complete? I.e., is it in NP? Given a certificate (the ...
11
votes
0answers
195 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 ...
4
votes
1answer
237 views

Water Systems: When can I use buckets of water to simulate an ODE.

It is quite common to use physical systems to perform calculations (see here and here). This is for a number of reasons: sometimes the physical system is efficient, sometimes it helps us understand ...
1
vote
1answer
77 views

Making a logarithmic equation that starts at $(0,0)$ and passes through $(x, y)$?

I'm writing a computer program and for fading sound, it's best to do it in a logarithmic equation. What I need it to find a graph of the "volume" that starts at (0, 0) [x is the time, y is the volume] ...
4
votes
2answers
93 views

Prove that $\{1, 11, 1001,\dots\}$ is an irregular language

Let $L:=\{1, 11, 1001,\dots\}$ be the language with alphabet $\{0,1\}$ which is formed by all powers $3^n, n=0,1,\dots$ written in binary notation. How to prove that $L$ is not regular?
15
votes
1answer
339 views

How to prove there are no more positive integers that are products of 2 and 3 consecutive numbers?

$6$ and $210$ share the property that both are the products of both two and three consecutive numbers. $6$ is $2\times3$ and $1\times2\times3$ and $210$ is $14\times15$ and $5\times6\times7$. It was ...
1
vote
1answer
115 views

Give a regular grammar for L

Give a regular grammar for L= {a^n b^n : n<=100} I would do something like this : S---> A | empty string A---> aB| empty String B---> Ab but How do we keep count of the number in the grammar? ...
0
votes
1answer
216 views

A an nxn matrix. P a permutation matrix that permutes columns of A. How many operations does P*A involve?

Essentially, I am supposed to count how many operations a particular computational algorithm involves, and I've gotten stuck on this one part. My understanding is that for two nxn matrices, matrix ...
28
votes
4answers
1k views

Why do we believe the Church-Turing Thesis?

The Church-Turing Thesis, which says that the Turing Machine model is at least as powerful as any computer that can be built in practice, seems to be pretty unquestioningly accepted in my exposure to ...
0
votes
1answer
56 views

can you determine the distinct variable bit packets from within this bitstream?

11001101111011000011000111001011010011010111011011100011100111101011 the above bit stream should break up into these variable bit packets 11 0011 0111 1011 000011 000111 001011 010011 010111 011011 ...
1
vote
1answer
243 views

Is there a function that grows asymptotically faster than the Busy Beaver numbers?

Is there a function that grows asymptotically faster than the Busy Beaver numbers? That is, I know that BB(n)^n grows faster than ...
3
votes
1answer
188 views

Books on computational complexity

Can anyone recommend a good book on the subjects of computability and computational complexity? What are the de facto standard texts (say, for graduate students) in this area? I've heard a thing or ...
1
vote
1answer
204 views

2-colorable belongs to $\mathsf P$

To show that 2-colorable belongs to $\mathsf P$, I have a straightforward mental description in mind that I don't think will be considered as a formal proof. Hence I am interested to know how this ...
19
votes
1answer
392 views

Mathematics of Torrenting

It is more or less common knowledge that a bittorrent network has the potential to be much faster than direct downloads, but I have never seen any real math describing why, or any theoretical bounds ...
-1
votes
2answers
75 views

How to find the amount to added every month or year to get the required amount after certain years?

I want to do a Java application for which after giving the current savings, and the rate of interest and and required amount after specified no of years, it has to show how much a person has to earn ...
2
votes
2answers
139 views

Books for Geometry processing

Please suggest some basic books on geometry processing. I want to learn this subject for learning algorithms in 3d mesh generation and graphics. Please suggest me subjects or areas of mathematics i ...
7
votes
4answers
410 views

What is the relationship between “recursive” or “recursively enumerable” sets and the concept of recursion?

I understand that "recursive" sets are those that can be completely decided by an algorithm, while "recursively enumerable" sets can be listed by an algorithm (but not necessarily decided). I am ...
3
votes
2answers
2k views

MATLAB code to find distance and eccentricity in graphs

I was trying to find the distances between vertices in graphs. But as the number of vertices are increasing up to 25 vertices or more, its becoming a tedious job for me to calculate $distance$ and ...
1
vote
1answer
87 views

Why is it okay to do this?

I am studying asymptotic recurrences for algorithms, and the book says: $$T(n) = 2T(n/2) + \Theta (n)$$ is technically $$T(n) = T(\lfloor n/2 \rfloor) + T(\lceil n/2 \rceil) + \Theta (n)$$ for an ...
3
votes
1answer
105 views

Is this language decidable?

Is this language decidable? $$\{x\mid \text{$x$ is the code of a Turing machine that always halts on $y$ in less than $y^3$ steps}\}$$ I think it is, because it halts in a finite number of ...
0
votes
1answer
51 views

Is $\{(x, y) \mid y \in \text{Range}(\phi_x)\}$ decidable?

Is the following language decidable? A decidable language must be recursive, right? How should I show that the following is or is not recursive? $$\{(x, y) \mid y \in \text{Range}(\phi_x)\}$$
1
vote
2answers
76 views

decidability of $\{x|W_x \text{is different from K in only finitely many elements}\}$

Is the following language decidable? Please explain your argument as I want to learn how such problems must be solved to do the rest on my own. $$\{x \mid W_x \text{ is different from K in only ...
1
vote
3answers
107 views

Is it possible to prove from the definition of big $O$ that $5n^3+7n+1$ is $O(n^3)$?

Is it possible to prove from the definition of big O that $5n^3+7n+1$ is $O(n^3)$? Can this be generalised to any case where you have to (and what is the procedure for working it out?) I guess the ...
0
votes
1answer
143 views

Why is it necessary to use sin or cos to determine heading? (dead reckoning)

Here's the problem: (see pic for problem): https://fbcdn-sphotos-c-a.akamaihd.net/hphotos-ak-ash3/21281_10152793202590262_1804321932_n.jpg You have a robot that is moving forward at a variable rate ...
1
vote
0answers
122 views

Pebble game on graph

Consider the problem whose instance is a directed graph with the selected vertex V and k of 'pebbles'. We can in any order, perform the following elemental steps: on top of x we can put a pebble, if ...
2
votes
2answers
158 views

Is the difference of two recursively enumerable sets, reducible to $K$?

Is the difference of two recursively enumerable sets, reducible to $K$? $W_x/W_y=\{z|z \in W_x \& z \notin W_y\}$ $K=\{x|\Phi_x(x) \downarrow\}$ $W_x= \text{dom}(\Phi_x)$
1
vote
2answers
203 views

Decidability and undecidability of a set or language

I want to find out whether the following sets are decidable or not. Generally speaking, what exactly should be done about it? Doing some research, I think a language or set is decidable if a Turing ...
2
votes
1answer
118 views

An interesting version of the problem “balls into bins”

Consider n people, each has k identical balls. Each people choose k different bins from m bins, constrained by the condition that there are no two people choose exactly the same k bins. For instance, ...
0
votes
1answer
131 views

Rice’s theorem and recursion theorem

Prove Rice’s theorem using recursion theorem. I need some hints as to what must be done about it. Please use Davis' book notation: Computability, Complexity, and Languages, Second Edition: ...
1
vote
2answers
128 views

non-recursive function

Give a direct proof that the set $\{x|\Phi_x(1) \downarrow\}$ (which is a set of program numbers that halt on input $1$) is not recursive. I've got an idea that indirect proof must work. Assuming ...
1
vote
1answer
292 views

Logical Conjunction of Binary Decision Diagrams

Compute a Binary Decision Diagram for $B1∧B2$. Furthermore, for an arbitrary BDD B you can use the equations $B∧F=F$, $F∧B=F$, $B∧T=B$ and $T∧B=B$. To construct the BDD i start from the leaves ...
2
votes
2answers
56 views

If $\{w^k|w\in L\}$ regular implies L regular?

If L is a language and the language $$\tilde{L}:=\{x^k,x\in L, k\in\mathbb{N}\}$$ is regular, does that imply that L is regular? ($|L|<\infty$ gives equivalence) We came across this question when ...
1
vote
1answer
67 views

Are these two context free grammars equivalent?

Let Σ = {a,b}. A CFG for the language {a^nb^m | n > 2m} can be written as: S-->aaSb S-->A A-->aA A-->a Would it be equivalent to write this CFG as: ...
1
vote
1answer
96 views

to find disconnected graphs

We know that if in a graph $G$, $e$ < $(n -1)$, then the graph is disconnected, where $e$ and $n$ are number of edges and number of vertices resp. Is there any other criteria to find out the ...
1
vote
1answer
127 views

Multivariable asymptotic analysis?

Show that $k \ln k = \Theta (n)$ implies $k = \Theta (n /\ln n)$. Thanks for the help.
0
votes
1answer
724 views

Is the function $\lceil\lg \lg n\rceil!$ polynomially bounded?

I'm totally lost so please be really explicit in your answers. Thanks for the help. Polynomially Bounded: $f(x)$ is polynomially bounded if for some constants $c$, $a$ and $x_0$, $$f(x) \le cx^a$$, ...
1
vote
0answers
37 views

is the $d$-dimensional arrangement of Trees still $NP$-hard?

The $d$ dimensional Arrangement Problem for general graphs is known to be $NP$-hard since the special case $d=1$ (OLA) already is (Garey et al, [1976]). For Trees however, the one dimensional case can ...
1
vote
2answers
116 views

Decimal Floating Point to Shortest Binary

Might be more of a Comp Sci question so apologies if it's not appropriate. Basically I have a range bounded by two floating-point decimals <1. I need to find a short binary number lying between ...
1
vote
1answer
140 views

Binary Decision Diagram of $(A\Rightarrow C)\wedge (B\Rightarrow C)$?

I made a Binary Decision Diagram for $(A\vee B)\Rightarrow C$, which i think is correct. Know i want o make a Binary Decision Diagram for $(A\Rightarrow C) \wedge (B\Rightarrow C)$ but i can't. I ...
0
votes
1answer
46 views

Given a DFA $\mathcal{M} = (S, \Sigma, q_0, \delta, F)$, is there an algorithm that finds the pumping length of $L(\mathcal{M}$)?

This question has been bugging me for a while, and I'm curious what such an algorithm would look like, if it exists. My guess is that it does exist, but I'm not sure how it would look.