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
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
3answers
692 views

Understanding recursive definitions of a language.

I am having difficulty understanding the recursive definition of a language. The problem asked how to write this non recursively. But I want to understand just how a recursive definition of a ...
1
vote
2answers
264 views

Determining function for recursive Fibonacci algorithm

I'm given a function: int fib(int n) { if (n == 0 || n == 1) return n; return fib(n - 1) + fib(n - 2); } from which I am supposed to determine a ...
1
vote
1answer
72 views

How to compute the complexity

1) If $a(n)=O(n^2)$ and $b(n)=O(n^3)$. Can someone tell me how to compute the computational complexity of $$ c(n)=\sum_{k=1}^{n}a(k)b(k) $$ What rules apply? I think it might be $O(n^6)$, but this ...
1
vote
2answers
44 views

Solving for x. Do I require iterations?

I have the following expression (used in a computer program): $$f(x)=b^{{k}^{ax}}$$ where $k$ is a constant and $a$ and $b$ are given. I need to calculate the distance from this curve to a point $P: ...
0
votes
1answer
44 views

Difficulty understanding some algebra done in a problem

The main problem is about computer science, trying to show that $f(x)=e^{x^Tx'}$ is of the form $\exp{\Big( \frac{||x - x'||^2}{2\sigma^2} \Big) }$, so it could be a kernel function. (see here for ...
1
vote
1answer
25 views

If I am checking for $s$ divides $n$ on the interval $S = [3, n-x]$, how large can I make $x$ to ensure I have verified $n$ is prime?

$\forall x \in \mathbb{Z}^+$, $x > 1 \longrightarrow x-2$ does not divide $x$ I have not yet proven this, which might be a good aside for my discrete math. One of my current assignments in ...
1
vote
1answer
84 views

Combinatorics question. Bit stuck.

Why can't there exist 5 5-digit binary numbers such that each pair has 1 or 2 digits in common? Another way to state the condition is that any pair has either 3 or 4 digits that are different.
0
votes
1answer
157 views

Cyclomatic complexity - understanding the paths issue

Also I know that cyclomatic complexity determines the number of linearly independent paths through the source code. An independent path=a path that executes at least one statement that the other paths ...
2
votes
1answer
91 views

A way to codify (pre-calculatate) if a one Tree Node is a descendant of another

I have a simple, 1-directional tree representing the veins in a human body. It looks somewhat like this (red dots are nodes, blood flow is always downwards, sorry for my drawing): What I need is a ...
8
votes
2answers
771 views

Common Lisp for mathematicians?

I am interested in learning Common Lisp. There seems to be a lot of material either for (experienced) programmers, or for people with no background, in programming or in mathematics. I was wondering ...
0
votes
1answer
112 views

Help with simplifying boolean functions algebraically

I have 2 boolean functions that I am having some difficulty solving algebraically. NOTE: ~ means NOT, & means AND, + means OR 1) $(\sim b~\&~\sim d)+(b~\&~\sim ...
1
vote
1answer
262 views

How to use a graph cut

I have to use a graph cut to create a binary image from a grayscale image. I can easily compute both energy functions $E_{data}$ and $E_{smooth}$. But after that, I don't know what is the next step. ...
1
vote
1answer
100 views

Difference between language is decidable and function calculable by turing machine

I'm trying to understand the difference between saying a language is decidable and a function is calculable by a turing machine. I must have understood something wrong, because for me it doesn't make ...
1
vote
1answer
159 views

Euclidean Division to avoid need for floating point arithmetic

In simple terms (that Google has been unable to provide the answer), is there an approach to dividing a whole integer by a quotient & remainder? As a specific example, ...
-1
votes
1answer
82 views

Limiting search space for efficient line matching [closed]

I have 2D line segments extracted from an image. So i know end point coordinates of them. also, i have some reference 2d line segments. Both line segments are now in vector form. comparing to ...
1
vote
1answer
188 views

Ackermann function in terms of higher order recursion

Wikipedia provides a higher-order definition of Ackermann function. First it gives the normal recursive definition \begin{equation*} A(m,n)=\left\{ \begin{array}{ll} n+1 & \text{if $m=0$} \\ ...
1
vote
1answer
641 views

How do I find the number of bit strings with 3 consecutive 0s in a bit string of length n?

Say n is 8. How would I ever solve this problem? I've Googled around and searched this site but I haven't come up with much. I'm not even looking for the answer necessarily, just the process by ...
0
votes
3answers
695 views

Are these languages context free or not?

$L_1=\{a^nb^mc^nd^m \mid m,n >0\}$ $L_2=\{a^nb^mc^md^n \mid m,n >0 \}$ $L_3=\{a^mb^n \mid m+n\text{ is a prime number}\}$ $L_4=\{a^mb^n \mid n=m^2\}$ $L_5=\big\{ww^R\#ww^R \mid w \in \{a,b\}^* ...
1
vote
1answer
311 views

Minimum number of moves to create a new permutation

Edit: Before you begin, please note that a move refers to swapping a pair of letters (thanks to ferfer93) Ok, so I understand the title is a bit ambiguous, so I'll clarify it further below: Let us ...
1
vote
0answers
102 views

Question regarding implicant chart of Quine-McCluskey algorithm

In https://en.wikipedia.org/wiki/Quine-McCluskey#Example, at the end of Step 1, there is a table that shows the number of 1's, minterms, 0-cube and size-2 implicants and size-4 implicants. But I am ...
2
votes
1answer
128 views

The existing bound on Edmonds-Karp doesn't seem to be tight

(I have posted the following in theoretical CS stackexchange, but realized that it's the wrong place, so I'm reposting it here) I'm reading CLRS's (Cormen et.a al) Introduction to Algorithm, and ...
1
vote
3answers
2k views

Way of simplifying binary multiplication

Is there a way to simplify multiplication of binary numbers regardless of digits? Or do we always have to resort to 10-base multiplication? As computers do multiplication, there should be ways to ...
1
vote
1answer
113 views

Space : Kolmogorov complexity :: time and space : ___?

It's well-known that the Kolmogorov complexity is uncomputable, essentially because of the halting problem: you can list all programs of length less than one known to generate a given string, but you ...
3
votes
1answer
316 views

Why is $ab+bc+ac = 0$ in some situation?

This is originally a Computer Science question, but I ran a equation that is too hard to solve. Here goes. So the problem is quite simple, given positive integers $a$, $b$, $c$, and calculate ...
4
votes
1answer
154 views

Prove that all combinators must fulfill A x = x for some x, given that M x = x x and composability of any two combinators

I'm working through Raymond Smullyan's "To Mock a Mockingbird" and I'm stuck on the first problem in the combinatory logic section. I'd appreciate hints, but no spoilers please. The problem is ...
3
votes
2answers
131 views

For a simple XML doc, how to find number of possible arrangements of elements (i.e open and close tags) when given maximum number of tags?

For a simple XML doc, how to find number of possible arrangements of elements (i.e open and close tags) when given maximum number of tags ? Let me rephrase the question by example, we have a set ...
1
vote
2answers
194 views

Is there a limit to how exact $\pi$ can be calculated? [duplicate]

Possible Duplicate: Do We Need the Digits of $\pi$? Working out digits of Pi. What are the limitations? Faster computers More accurate measuring devices
0
votes
1answer
139 views

Regular grammar and context grammar problems

If $G$ is not a regular grammar, then $L(G)$ is infinte. If $L^*$ is context free then $L$ is definitely context free. If $G$ is a context free grammar that is language is $L$ (meaning $L(G) = L$), ...
1
vote
1answer
223 views

Programming related calculus & math symbols and questions

I am reading a textbook for my next semester just for fun. I didn't study so hard during the high school so I have missed out many vital information. Questions: 1) What is λ -calculus and λ (in ...
1
vote
1answer
91 views

Proving uncomputability — Rice's theorem

I am trying to prove the uncomputability of the following function: Let $\varphi$ be a Gödel-numbering of the computable functions. Consider the following function: \begin{align*} f(x) = \left\{ ...
1
vote
0answers
61 views

Regression with multiple line types from set of points

Given a set of points, I'm looking to find the best possible line (within reason) to fit to these points. These points won't be from real data, so they could form any sort of curve or line. So, I ...
3
votes
2answers
215 views

Primitive recursive select from parameters

I'm looking forward function, that works like that $\mathbb{N}^{n+1} \rightarrow \mathbb N$: $f(y, x_1, x_2, \dots ,x_n)=x_y$ We use projection $\Pi^n_k$, but I need something with "dynamic" size ...
3
votes
1answer
274 views

Steps in the Simplex Method

I'm trying to look at how the Simplex method in standard form works. I understand the basics of how ti works, but I can't understand what happens between two steps. I'm using the example from chapter ...
1
vote
0answers
96 views

Asymptotic analysis for multiple variables?

How is asymptotic analysis (big o, little o, big theta, big theta etc.) defined for functions with multiple variables? I know that the Wikipedia article has a section on it, but it uses a lot of ...
0
votes
2answers
66 views

Asymptotic constants for a quadratic?

Note than $n$ is a parameter for the functions. For some constants $c_1, c_2$ and $n_0,$$$c_1n^2\le an^2 + bn + c \le c_2n^2$$ for all n > $n_0$. Consider any quadratic function $f(n) =an^2 ...
1
vote
0answers
180 views

PDA state diagram with an inifinite languge but with no looping states

For class I'm supposed to create a PDA state diagram that is capable of generating an infinite language with no state q such that q is reachable from the start state, there is no cycle within the ...
0
votes
1answer
870 views

How to prove perm-power is in P?

Let $\mathit{PERM\text{-}POWER} = \{ \langle p, q, t\rangle \mid p = q^t \}$ where $p$ and $q$ are permutations on $\{1, \ldots, k\}$ and $t$ is a binary integer. How do I prove that ...
0
votes
2answers
102 views

Is the halting of a program that checks for duplicates in an infinite multiset decidable?

A program $P(\Sigma)$ takes input $\Sigma$, which is an nonempty multiset. Let $\Phi$ be an empty multiset. Take any element $\sigma$ from $\Sigma$. If $\sigma \in \Phi$, return true. Otherwise, ...
1
vote
4answers
86 views

Procedures to find solution to $a_1x_1+\cdots+a_nx_n = 0$

Suppose that $x_1, \dots,x_n$ are given as an input. Then we want to find $a_1,\ldots,a_n$ that satisfy $a_1x_1 + a_2x_2+a_3x_3 + a_4x_4+\cdots +a_nx_n =0$. (including the case where such $a$ set does ...
-1
votes
1answer
207 views

How to show if a function is partial recursive?

I have seen and understood the most definitions but i just could not understand how to show if a function is mu-partial recursive or not. I used search engines, but all I find are just more lectures ...
0
votes
1answer
397 views

machine numbers in IEEE single precision

Is the following numbers machines numbers on the IEEE single precision system? $10^{304}$ $2^4+2^{27}.$ What do I have to do to know whether they are machine numbers on IEEE single precision?
1
vote
1answer
165 views

The set of Turing machines that recognize $\{00, 01\}$ is undecidable

$L =\big\{\langle T\rangle \mid T\text{ is a Turing machine that recognizes }\{00, 01\}\big\}$. Prove $L$ is undecidable. I am really having difficulties even understanding the reduction to use ...
5
votes
1answer
915 views

Why can't reachability be expressed in first order logic?

I'm wondering why we can't express graph reachability in first order logic in pretty much exactly the same way we express it in second order existential logic. For SOL, one definition is : 1 . L is ...
0
votes
1answer
102 views

Why do we need tactics, reflection and other techniques when we have Curry-Howard for theorem proving?

First of all, I apologize if this question is slightly misplaced, but this seemed the best place to ask it given the mathematical/theoretical nature of the discussion. Given that the Curry-Howard ...
1
vote
1answer
172 views

Depth first search on graph

I have a homework problem I think I know the answer to, but want to double check Consider the graph with three nodes, $a$, $b$, and $c$, and the two arcs $a \rightarrow b$ and $b \rightarrow c$. ...
1
vote
1answer
340 views

Reduction to prove that the function is not computable

Use reduction to show that the following function is not computable, where P is any python program that takes a single input x: sotrue(P) = true, if P(x) returns true for every value of x, ...
2
votes
1answer
194 views

Connected Components Graph proof

I am trying to do this one problem for a homework set, and am not entirely sure how I would even start this proof. Here is the question Prove, by induction on k, that a connected component of k nodes ...
0
votes
1answer
50 views

Parallel computing : scheduling processors for large sums

does anyone know if there exists in the literature an algorithm that solves the following problem? I have M different and indipendent sums, and P processors. The size of sums are in ascending order ...
4
votes
2answers
382 views

Big Oh notation of $7x^2$, confused

I'm supposed to figure out the Big-Oh notation of $7x^2$. Take a look at this. Now this says: Show that $7x^2$ is $O(x^3)$ When $x>7, 7x^2<x^3$, So let $C=1$ and $k=7$, we see $7x^2$ is ...