# Tagged Questions

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 ...

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 ...
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 ...
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(... 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 ... 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 ... 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 ... 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 \... 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\}, \... 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=\{... 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 ... 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 ... 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.... 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 ... 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 ... 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 ... 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: (... 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 ... 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 ... 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. 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 ... 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 ... 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 ... 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~\&... 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. ... 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 ... 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, ... 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 ... 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,... 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 ... 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\}^* \... 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 ... 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 ... 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 ... 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 ... 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 ... 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{... 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 ... 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,... 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 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), ... 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 ... 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\{ \... 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 ... 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 ... 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 ... 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 ... 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 +... 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 ... 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\...
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, ...