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

1
vote
1answer
287 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
170 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
347 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 ...
1
vote
1answer
90 views

Diagonal of a convex polygon such that the obtained cuts have simmilar areas

Let $P$ be a convex polygon represented with a list of vertices specified by some orientation. Consider the following problem Problem. Find in linear time a diagonal of $P$ such that the absolute ...
1
vote
1answer
76 views

Seeking Alternate Proof Regarding Closure Of Recursively Enumerable Languages Under Shrink

So I would like to show that the class of Recursively Enumerable languages are closed under the shrink operation. In other words, $\mathrm{shrink}_a(L) = \{x \mid x=\mathrm{shrink}_a(w), w\in L\}$ and ...
2
votes
1answer
87 views

LTL translation to omega-regular languages

I tried to define a translation from LTL to ω-regular languages. I built it inductively on the structure of LTL formulae. No problem except with the 'until' operator where I came up with the ...
0
votes
1answer
2k views

Introduction to the Theory of Computation Solution Manual - Michael Sipser

I am hoping to test out a Theory of Computation class for next semester and have bought the course's textbook, Introduction to the Theory of Computation by Michael Sipser to prepare. I was trying to ...
4
votes
2answers
83 views

Finding N elements that are included in as many sets as possible

Say I have 20 sets, containing a variable amount of elements. How would I go about finding the 10 elements that cover the most number of sets? Imagine I could search for three terms at once on ...
0
votes
2answers
114 views

floating point binary arithmetic

Prove that the decimal number $\displaystyle \frac{1}{5}$ cannot be represented by a finite expansion in the binary system.
1
vote
2answers
189 views

Finite representation in the binary $\implies$ finite representation in the decimal system

Any number that has a finite representation in the binary system have a finite representation in the decimal system. Why?
1
vote
1answer
143 views

Floating point arithmetic

How can I prove that : a real number has a finite representation in the binary system if and only if it is of the form $$\pm \frac{m}{2^n}$$ where n and m are positive integers.
1
vote
0answers
335 views

Diffie-Hellman key exchange public key calculation

I encountered a question that I can't seem to get around it. Lets say user A and B uses the DHKE defined over $GF(2^8)$ induced by the irreducible polynomial $x^8 + x^4 + x^3 + x^2 + 1$ and the ...
6
votes
4answers
6k views

Great Book on Probability and Statistics (for Computer Scientists)

I'm a Computer Science sophomore and we're studying Probability and Statistics (fundamentals and all). The teacher recommends a book which I don't like since it does not even try and explain ...
0
votes
0answers
46 views

is it possible to reduce the weight of a best fit line (least squares) given new data points?

I have a simple best-fit-line algorithm similar to this description. Without memorizing the points history, it is easy to calculate a rolling best fit line as long as we remember (store) the ...
6
votes
2answers
771 views

Finding the 2,147,483,647th prime number

In computer science an array is indexed by an integer (int). Unlike in mathematics, the computer science integer (int) has a ...
1
vote
0answers
182 views

Power sums, fast algorithm

I know some schemes to compute power sums (I mean $1^k + 2^k + ... + n^k$) (here I assume that every integer multiplication can be done in $O(1)$ time for simplicity): one using just fast algorithm ...
0
votes
4answers
118 views

Language over $\{0,1\}$

I am learning about languages but struggling with operations on them. In my book there are some simple examples but how would I for example describe a language over $\Sigma=\{0,1\}$ such that every ...
0
votes
1answer
45 views

Is a statement concerning the future part of a decidable problem?

Let Did I ever get 100% in an exam? be a problem and the corresponding (characteristic) function $$\chi(x)=\begin{cases}1,& \text{if the statement can be answered with ...
1
vote
2answers
2k 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. ...
2
votes
2answers
2k 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
226 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
90 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
61 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
150 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 ...
8
votes
1answer
1k 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
322 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
1k 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
376 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
142 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
422 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
2k 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 ...
3
votes
1answer
75 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
174 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
167 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
547 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
119 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
125 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
181 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$?
2
votes
1answer
556 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) ...
5
votes
2answers
425 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
90 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
131 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
148 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
43 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?
2
votes
1answer
676 views

radial basis function and neural networks

actually i need a simple explanation consider it for dummies about what is Radial basis function are?and what is the relation between radial basis function and neural networks ?and is there's any ...
2
votes
1answer
354 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
71 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
578 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})$ ...
1
vote
1answer
93 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, ...