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

0
votes
2answers
246 views

Prove that entropy is maximized when probability is $1/n$

How can be proven that the entropy of a dice roll is maximized when the probability of each of its $6$ faces is equal, $1/6$?
3
votes
1answer
1k views

Computational Complexity of Modular Exponentiation

The following was posted from a lecture: "($a^n \bmod N$) has a runtime complexity of $\mathcal{O}(n*|a|*|N|)$ using the brute force method. $Z_1 = a \bmod N$ $Z_2 = (aZ_1) \bmod N$ $Z_3 = (aZ_2) ...
8
votes
3answers
775 views

Does the recursion theorem give quines?

Wikipedia claims that the recursion theorem guarantees that quines (i.e. programs that output their own source code) exist in any (Turing complete) programming language. This seems to imply that one ...
1
vote
1answer
141 views

Conditional entropy of sum of random variables

How can be proven that for random variables $A$ and $B$, and $C = A + B$, $$H(C\mid A) = H(B\mid A).$$ Also, would it be possible to determine if $H(C)$ would be greater than $H(A)$?
0
votes
1answer
151 views

Prove that if $f(n) \in \mathcal{O}(h(n))$ and $g(n) \in \mathcal{O}(h(n))$ then $f(n) + g(n) \in \mathcal{O}(h(n))$

Prove that if $f(n) \in \mathcal{O}(h(n))$ and $g(n) \in \mathcal{O}(h(n))$ then $f(n) + g(n) \in \mathcal{O}(h(n))$. I know that $\mathcal{O}(g(n))=\{f\space | \space\exists ...
-1
votes
4answers
163 views

Is $O(n^2) = O(n^3)$? Prove your answer.

I am not sure how to go about doing this, I know that: $$O(g(n))=\{f : \exists \ c \ \in \Bbb R_+, \ \exists \ n_0 \in \Bbb N, \ \forall \ n\geq n_0 :f(n) \le c·g(n)\},$$ but how do I go about using ...
0
votes
3answers
45 views

Asymptotic analysis of a ratio

Is $ \frac{n^2}{n-2}\in O(n) $ true? Intuitively it seems so but how would I rigorously prove this?
3
votes
1answer
1k views

Radial Basis Function and Neural Networks

I need a simple explanation about what is the radial basis function? And what is the relationship between the radial basis function and neural networks? And are there any simple examples to explain ...
2
votes
1answer
586 views

Polynomial complexity algorithm of partition problem with sets of equal size

Partition problem is well known ( http://en.wikipedia.org/wiki/Partition_problem ). Let's add an additional condition: sizes of both sets should be equal. Is there a pseudo-polynomial solution to ...
0
votes
1answer
78 views

EFA and recursive algorithm

1) Is EFA stronger than recursive algorithm? (This can be in term of proof theoretic ordinal, or whatsoever - to rephrase the question, are all problems that can be solved(and halt) by recursive ...
2
votes
2answers
1k views

Big - O estimation

I want to establish a Big-O estimate for the following: $$(n! + 2^{n+3})(111n^3 + 15\log(n^{201} +1))$$ Would the following be correct? $n! = O(n^{n})$ $2^{n+3}=O(2^{n+3})$ $111n^{3}=O(n^{3})$ ...
3
votes
2answers
3k views

Solve the Relation $T(n)=T(n/4)+T(3n/4)+n$

Solve the recurrence relation: $T(n)=T(n/4)+T(3n/4)+n$. Also, specify an asymptotic bound. Clearly $T(n)\in \Omega(n)$ because of the constant factor. The recursive nature hints at a possibly ...
1
vote
1answer
100 views

How do you encode a programm in a category?

A Type-0 language (in the Chomsky hierarchy) is Turing complete and so you can encode all machines in them - you only need a compiler which translates it to the respective machine code. Appearently, ...
2
votes
1answer
2k views

Showing that a language is not regular using Myhill-Nerode Theorem

I'd like to show that the language below is not regular using Myhill-Nerode Theorem. How can I do that? Thanks in advance. Let $Σ = \{0, 1, +, =\}$ and $\mathrm{ADD} = \{x = y + z \mid x, y, ...
0
votes
1answer
125 views

Proving if equations are products of XOR

I have to prove analytically to see if these equations are exclusively or. $$A⊕ A=0$$ Do I solve this by using the truth table? ...
1
vote
2answers
2k views

Big O Notation and finding witnesses

I am trying to figure out some stuff here with Big O Notation. I mean I understand the concept of it and can generally be able to tell what the efficiency of something is, but I do not really ...
1
vote
1answer
3k views

Prove that if $f(n) \in O(g(n))$ then $g(n) \in \Omega(f(n))$

Prove that if $f(n) \in O(g(n))$ then $g(n) \in \Omega(f(n))$. So I know that $$O(g(n)) \Rightarrow f(n) \leq c\cdot g(n)$$ and that $$\Omega(g(n)) \Rightarrow f(n) \geq c\cdot g(n)$$ but how ...
1
vote
1answer
570 views

Prove that if $f(n) ∈ Θ(g(n))$ and $g(n) ∈ Θ(h(n))$ then $f(n) ∈ Θ(h(n))$.

I know that by the assumption that $f ∈ Θ(g)$ we know that there exist constants $c_0$ and $c_1$ in $\mathbb R^+$, and there exists $n_0 ∈ \mathbb N$ such that: $$c_0 \cdot g(n)\le f(n)\le c_1 \cdot ...
1
vote
1answer
35 views

Round numbers in a set of limits

I'm trying to create a mathematical operation that help me to resolve this scenario. I have a list of "limits" as show below: 0---4---8---12... (n + 4) Suppose that we have a software that ...
-2
votes
1answer
127 views

Show that if $(L_1;≤_1)$ and $(L_2;≤_2)$ are both modular lattices then so is $(L_1 \times L_2;≤)$ [duplicate]

Possible Duplicate: Cross Product of Partial Orders Suppose that $(L_1;≤_1)$ and $(L_2;≤_2)$ are partially ordered sets. We define a partial order $≤$ on the set $L_1 \times L_2$ in the ...
0
votes
1answer
270 views

Boolean simplification

So I am giving this expression D +B’C’ + CD’ +A B’C and I ask to simplify it When working through it I get D+B'C'+CD'+AB'C D'(A'B'+CD'+AB) D'(A'B'+A(B'+B)) D'(A'B'+AC') D'(B'+A) Am I on the right ...
0
votes
1answer
83 views

Boolean Function

A Boolean expression is given: (A B)’ + B C’ +A’ C = F. Construct the logical circuit and draw the timing diagram of the output F. I am not sure where to start.
3
votes
3answers
2k views

Approximate a convolution as a sum of separable convolutions

I want to compute the discrete convolution of two 3D arrays: $A(i, j, k) \ast B(i, j, k)$ Is there a general way to decompose the array $A$ into a sum of a small number of separable arrays? That is: ...
0
votes
1answer
117 views

Applications of Concrete Categories in Computer Science

From Wiki: "In mathematics, a concrete category is a category that is equipped with a faithful functor to the category of sets. This functor makes it possible to think of the objects of the category ...
0
votes
1answer
1k views

What Precalculus knowledge is required before learning Discrete Math Computer Science topics?

Below I've listed the chapters from a Precalculus book as well as the author recommended Computer Science chapters from a Discrete Mathematics book. Although these chapters are from two specific ...
2
votes
1answer
674 views

Prove a bound on matrix multiplication?

Show that $O(\log n)$ matrix multiplications suffice for computing $X^n$. (Hint:Think about computing $X^8$.) $X = \pmatrix{0 & 1 \\ 1 & 1}$ How would I go about doing this? I'm ...
2
votes
1answer
155 views

How does one approach asymptotic relation problems?

Consider the following functions: $f(n) = \frac{n^2}{\log n}$ $g(n) = n(\log n)^2$ Indicate the relation between the two (e.g. $f(n)= O(g)$, $f = Ω(g)$ or $f = Θ(g)$) The above ...
1
vote
1answer
97 views

Proving $\{ll^{R}l|l\in\{a,b\}^{*}\}$ is not context free using the pumping lemma

How can I prove, using the pumping lemma for context free languages, that $\{ll^{R}l|l\in\{a,b\}^{*}\}$is not a context free language ? I tried to put $n$ as the pumping lemma constant and chose ...
2
votes
3answers
858 views

What prime number generating algorithms are used?

You sometimes hear bout these huge prime numbers (RSA prime number challenge comes to mind) and I was curious about what algorithms or formulas prime-number generators use in practice ? For example in ...
1
vote
2answers
942 views

Converting each formula into Conjunctive Normal Form?

How hard is it to translate an arbitrary well-formed formula into CNF formula? It seems it can get exponential in some occasions like $(a\wedge b)\vee (c\wedge d)$ is transformed into $(a\vee ...
1
vote
1answer
91 views

Is quasi-polynomial complexity related to quasi-polynomial?

From Wikipedia Quasi-polynomial time algorithms are algorithms which run slower than polynomial time, yet not so slow as to be exponential time. The worst case running time of a ...
3
votes
1answer
863 views

Help identifying math symbols: big crosshair and caret

https://www.dropbox.com/s/0d1sh8pxn6savgm/IMG_20121005_010828.jpg Can anyone identify the names of the crosshair and ^ symbols? 90% sure the ^ means bitwise AND from searching wikipedia, but I ...
2
votes
1answer
1k views

Calculating CRC code

I think I may be under a misconception. When calculating the CRC code, how many bits do you append to the original message? Is it the degree of the generator polynomial (e.g. x^3+1 you append three ...
-1
votes
1answer
165 views

Unbounded number of tapes of Turing Machine

Turing Machine with multiple tapes can be encoded such that its computational power is equivalent to Turing Machine with single tape. My question is if we have unbounded number of tapes, just like the ...
4
votes
2answers
355 views

What does “classical logic” mean?

I'm a junior researcher in Computer Science field and I've had some difficulties with some scientific terms like the one on the title "classical logic" which is used to represent and identify some ...
1
vote
2answers
354 views

How to find an equivalent formula?

I have a formula: $p \wedge \neg q \implies q \vee \neg p $, and i have calculated a truth table as follows: $$\begin{array}{c} p&q&\text{Formula}\\ \hline 0&0&1\\ 0&1&1\\ ...
1
vote
1answer
177 views

When can we exchange the order of big/little O and function composition

From Wikipedia Let $f(x)$ and $g(x)$ be two functions defined on some subset of the real numbers. One writes $$ f(x)=O(g(x))\text{ as }x\to\infty\, $$ if and only there exists a ...
2
votes
2answers
2k views

Prove that a language B is regular

here is the question I'm dealing with: Let B = {$1^{k}$y|y $\in$ {0,1}* and y contains at least k 1s, for k $\geq$ 1}. Show that B is a regular language. Can I use the pumping lemma to ...
2
votes
2answers
2k views

Why do we need Taylor polynomials?

This question doubles as "Is my understanding of what a Taylor polynomial is for, correct?" but In order to write out a Taylor polynomial for a function, which we will use to approximate said function ...
1
vote
1answer
309 views

Prime numbers and their products

I've been reading a bit about prime numbers and their use in cryptography. If i would create a table of primes and their products, would there be any way to point out the area where a given number x ...
0
votes
1answer
128 views

Runge Kutta ODE Solver question

How do I apply $${d\,v_x\over d\,t} ={FDv_x\over mv} \text{ and } {d\,v_y \over d\,t}=−g{FDv_y\over mv}$$ to the function of $f$ in the Runge Kutta ODE solver: $q1=f(v_yk)$ ...
2
votes
2answers
837 views

Context free languages closure property $\{a^n b^n : n\geq 0\} \cup \{a^n b^{2n}: n\geq 0\}$

I have been working on the following two problems: 1) Given any context free language L, form a new language by taking symbols at the odd positions, i.e. $w=a_1a_2\dots a_n \mapsto w'=a_1 a_3 a_5 ...
1
vote
1answer
166 views

Right adjoint to forgetful functor from “dynamical system” digraph

Question about "dynamical systems," as Lawvere/Schnauel calls them in their baby book (ie digraph w exactly 1 arrow out of each point). What would a "chaotic" dynamical system be? In the book's ...
31
votes
8answers
4k views

Is the set of all valid C++ programs countably infinite?

I have heard that the set of valid programs in a certain programming language is countably infinite. For instance, the set of all valid C++ programs is countably infinite. I don't understand why ...
4
votes
4answers
167 views

What sort of math is this, and how would I solve it?

I'm taking a computer science class after several years away from school and so far I'm doing all right. However, we're covering some math and I'm drawing a blank on what to even call this concept, ...
1
vote
2answers
58 views

Finding the probability of a client getting the same token in two consecutive interactions.

I am trying to find the probability in the following real-world inspired scenario. If I have a finite set of whole numbers from 0 to 4 billion which I call tokens and $n$ clients. Each time a client ...
11
votes
0answers
175 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)$ ...
1
vote
1answer
87 views

List number of moves to defeat the opponent

Given the position of chess board of two players, we have to find the minimum number of moves (and output them) so that only one player playing continuously and optimally defeat the other one ...
2
votes
2answers
503 views

Graph Run Time, Nodes and edges.

Hi i have these two problems that are part of a practice set i am doing for exams, i can't seem to get around them. If you can answer any of them thanks in advance. For a given graph $G=(V,E)$ and ...
1
vote
1answer
168 views

Fraction values around the vertices of a Loop's subdivision

In Loop's subdivision scheme, what do the variables $\alpha$ and $n$ refer to? Knowing what the variables refer to will help to derive the fractions around the vertices. But, what do these ...