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

5
votes
3answers
908 views

What are some interesting coding projects (doable in Java) that relates to group theory?

I would like some ideas of possible programs I can write in Java that involves some computational aspects of group theory. My only ideas so far is to write a program that computes the product of two ...
0
votes
1answer
120 views

Decimal expansion in logic Church thesis

How can we show that the function $n \mapsto e_n$, where $e_n$ is the $n$-th digit in the decimal expansion of $e$, is computable? I have some idea in terms of Cantor's diag. argument, but I need to ...
8
votes
2answers
10k views

Determining Ambiguity in Context Free Grammars

What are some common ways to determine if a grammar is ambiguous or not? What are some common attributes that ambiguous grammars have? For example, consider the following Grammar G: $S \rightarrow S(...
1
vote
1answer
181 views

Proof of the pumping lemma for Context-Free Languages

I have a doubt concerning the proof of the pumping lemma for context-free languages. The pumping lemma for context-free languages is stated as follows: If $A$ is a context-free language, then ...
2
votes
2answers
1k views

Master Theorem $T(n) = 4T(n/2) + \lg n$

In class today, we did the following problem: $T(n)=4T(n/2) + \lg n$ So by notation in CLRS, we have $a = 4$, $b = 2$, $f(n) = \lg n$. Thus, $n^{\log_b a} = n^2$. My algorithm lecturer claimed that ...
2
votes
1answer
308 views

Are linear shift register sequences corresponding to reciprocal polynomials equivalent?

I am looking into sequences generated by LFSRs (linear shift register sequences). I was wondering if sequences corresponding to reciprocal connection polynomials (that is, corresponding to shift ...
1
vote
1answer
77 views

Knapsack-like problem

I need to express an integer $n$ as the sum of integers $x_i$ below some threshold $t$, minimizing the number of $x$s, and maximizing a lower threshold $q$. $$\min_{\# x} \max_{q} : \sum_i x_i = n \...
2
votes
1answer
1k views

How to construct a grammar $G$ such that $L(G) = \{ a^nb^m|n \neq 2m,m,n \ge 0\} $?

Construct a grammar $G$ such that $$L(G) = \{ a^nb^m|n \neq 2m,m,n \ge 0\}$$ My attempt: I first constructed a grammar for the langugage $L(G_1) = \{ a^nb^m|n = 2m,m,n \ge = 0\}$, $G_1 = (\{ S\}, \...
5
votes
1answer
197 views

Maximal subset with rank $k$

I'm trying to solve the following problem for an algorithm I'm trying to develop and I couldn't find anything helpful in scholar google. Here is the question: Suppose I have a set of $N$ vectors $V=\{...
3
votes
1answer
197 views

Explain why if the language A is recursive, then A is reducible to 0*1*

I'm in a theory of computation class and there is a problem that I think I am way overthinking. Can anyone point me in the right direction with the following: Give a short justification of the fact ...
5
votes
3answers
1k views

Formally prove that $\Theta(\max(f,g)) = \Theta(f+g)$

I am having a hard time proving that $\Theta(\max(f,g)) = \Theta(f+g) $ where $(f+g)(n) = f(n) + g(n) $ and $(\max{f,g})(n) = \max(f(n), g(n))$ I know that $\Theta$ is the combination of the ...
3
votes
0answers
56 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$ points....
3
votes
3answers
1k 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
369 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
80 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
49 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
45 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
26 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
87 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
188 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
105 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
1k 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
118 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 c~\&~d)+(b~\&~c~\&...
2
votes
1answer
304 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
117 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
197 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, ...
-2
votes
1answer
90 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
223 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$} \\ A(m-1,...
1
vote
1answer
1k 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
917 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
405 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
118 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
154 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
2answers
4k 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
118 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
379 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 $\sqrt{...
4
votes
1answer
168 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
139 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 T{O,...
1
vote
2answers
201 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
149 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
316 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
110 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
68 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
221 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
366 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
103 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
71 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
221 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
1k 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 $\mathit{PERM\...
0
votes
2answers
108 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, ...