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

2
votes
2answers
3k views

Meaning of amortized analysis of an algorithm

From Introduction to Algorithms by Cormen et al: In an amortized analysis, the time required to perform a sequence of data structure operations is averaged over all the operations performed. ...
3
votes
3answers
5k views

meaning of 'Hypothesis' in simple terms?

could anyone please clarify me the meaning of the term 'hypothesis'? with relation to terms 'reasoning' and 'assumption' ? Many thanks
3
votes
3answers
255 views

0-1 knapsack like - the set of all non-contained affordable binary selections

This is my first question here, so please go easy on me :) The following problem is – I think - similar to the 0-1 knapsack problem. It's simplified somehow in that each item has only a cost ...
2
votes
1answer
108 views

what is the best resource for foundation Computer Science related Maths

Could anyone please let me know what would be the best resource to get foundation for CS maths? Many Thanks
1
vote
2answers
63 views

What is this number $k$?

I'm reading A first Course on Logic, (Hedman). An algorithm is said to be polynomial-time if there is some number $k$ so that, given any input of size n, the algorithm reaches it's conclusion ...
1
vote
0answers
161 views

Question about the elementary divisors of a special matrix

I have the following question: Is there a closed formula for the elementary divisors of the Matrix $M={(m_{ij})}_{i=1,...,n,\ j=1,...,k}$, where ${m}_{ij}$ is the greates common divisor of $i$ and ...
12
votes
2answers
3k views

An efficient way to determine if two context free grammars are equivalent?

I'm wondering if there's an efficient way of checking to see if two context free grammars are equivalent, besides working out "test cases" by hand (ie, just trying to see if both grammars can generate ...
4
votes
1answer
414 views

Is there a polynomial-time algorithm to find a prime larger than $n$?

Is there a polynomial-time algorithm to find a prime larger than $n$? If Cramér's conjecture is true, we can use AKS to test $n+1$, $n+2$, etc. until the next prime is found, and this method will ...
2
votes
3answers
3k views

Time complexity of binary multiplication?

Using the grade school method of multiplying two binary numbers takes $O(n^2)$ time, where $n$ is the length of the number in bits. Why is this true?
0
votes
0answers
513 views

Square root using simple arithmetic shift, inversion etc

Suppose we have a function which is sampled by a sampling time 10ms. This function comes in to the computer, then this computer should calculate square root (for every sampling time) from that ...
2
votes
1answer
148 views

How to Reduce The Nested Sum $\sum_{j=1}^n\sum_{i=0}^{i<j} \frac{1}{2}$

I'm trying to find the expected number of swaps in a algorithm I'm working on. I've gotten to this point: $E[S] =\sum_{j=1}^n\sum_{i=0}^{i<j} \frac{1}{2}$ I don't know how to reduce this further. ...
1
vote
1answer
710 views

question on how to decrypt the message

A message is encrypted using an affine cryptosystem in which plaintext uses the 26 letters A through Z (all blanks are omitted), the letters are identified with the residue classes of integers (mod ...
7
votes
4answers
3k views

Big-O notation Basics, is it related to derivatives?

I am having the hardest time with Big-O notation (I am using this Rosen book for the class I am in). On the surface, Big-O reminds me of derivatives, rate of change and what not; is this proper ...
4
votes
1answer
82 views

Converting to base $-2$

How to convert a number given in Decimal to negative base.? For eg I want to convert $67$ given in decimal base to base $-2$.?
0
votes
1answer
695 views

How many bits of memory per character?

If I create an array with 10 random numbers in the range [0, 2^30]. How can calculate the number of bits that it will consume of memory? Let's assume that each of the numbers has 10 digits. That ...
2
votes
1answer
233 views

Proof that language is not context-free.

Is this the appropriate way to show that this language is not context-free? Given the language $L$ containing the words $1$, $101$, $101001$, $1010010001$, where each word $L_n$ is of the form ...
0
votes
1answer
700 views

DCT and Inverse DCT Formulas

I'm implementing DCT, but I don't see the difference with the Inverse DCT formula. Both formula are on the Wikipedia page. The difference looks to be the normalization factor, but I don't see how to ...
3
votes
2answers
136 views

Is there any book / tutorial where i can get the summary of all engineering math stuff

I studied math with all topics but that was 10 years back and now i have forgot them. Now i need to dive into statistics field and machine learning stuff. Now i don't have time for study different ...
1
vote
0answers
168 views

What was done to calculate the Ramsey numbers using a quantum computer?

I recently came across this paper titled Experimental determination of Ramsey numbers with quantum annealing I was wondering what exactly the gist of the paper, as I read it, it seems rather ...
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
805 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
153 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
590 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
79 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
126 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
582 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
271 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
679 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
862 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
960 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 ...