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
28 views

P vs NP and Countable vs Uncountable Decision Space

I have noticed that whenever the scope of a problem is pushed to infinity, problems in NP have an uncountably infinite decision space whereas problems in P seem to have a countably infinite decision ...
1
vote
1answer
31 views

Formal language: Proving the reverse operation on a word through induction

I'm practicing proofs and given the following statement: Let $\Sigma$ be an alphabet, $\epsilon$ the empty word and $\sigma:\Sigma^{*}\rightarrow\Sigma^{*}$ an operation which for $a\in\Sigma$ and ...
4
votes
2answers
464 views

“Opposite” of idempotent operation?

What is the adjective given to a mathematical operation/expression on a variable whose new value can only be described in terms of that variable's existing value? Sequential operation? Example: i = ...
2
votes
0answers
16 views

Optimality of lower bounds for Max-cut on specific graphs

The Max-Cut problem asks to find a subset $S$ of the vertices of a graph (with $m$ edges) such that the number of edges from $S$ to it's complement is as large as possible. The size $|M|$ of a max cut ...
0
votes
1answer
195 views

How to convert this NFA to DFA?

What are the steps for converting this NFA to a DFA??
-2
votes
1answer
45 views

Cryptography Combinatorics question [on hold]

I 'invented' this encryption device - take a string, and start with the first character. Swap this character with the second with probability $50$%. Move to the (now) second character, and repeat ...
1
vote
1answer
30 views

Finding the time for an epidemic/computer virus to infect a population

Question: "Suppose a computer worm makes 2 copies of itself on another computer in one millisecond. Estimate the time that is needed to spread to a population of 1,000,000 computers" How would I ...
1
vote
1answer
26 views

validity of isbns in catching jump transposition errors

Does the isbn detect jump transpositions? $$a_1+2a_2+3a_3+\cdots+10a_{10}=0\pmod{11}$$ I think it does because the specific formula multiplying 1 times 1st digit, 2 times 2nd digit... will give you ...
0
votes
1answer
18 views

Finding error control capability of Hamming distance

I have known how to calculate the Hamming distance between two message codes. But I don't know how to get the error control capability. In one case I have hamming distance of: $$ d = 8 $$ Errors ...
1
vote
1answer
16 views

Essential Prime Implicants and Minterm Expressions

I have an exam for a university course shortly, and upon reviewing one of my assignments I have come to realize that I don't understand why I have lost marks/how to do a couple of questions. Hopefully ...
1
vote
0answers
10 views

Random DFS properties

Have there been any work analyzing some properties of random DFS walks? By that I mean a DFS search, which chooses the next node to visit with uniform probability. i.e, it still refrains from visiting ...
1
vote
0answers
33 views

Probability distribution of request handling

I have values representing time taken to execute one request on server. Could somebody advise what type of distribution it is? I think that normal distribution but I am not really sure about it. ...
0
votes
1answer
19 views

How to find the order of G using the size of G and its complement

If the size of graph G is 19 and the size of its complement G-bar is 17 then find the order of G?
0
votes
1answer
27 views

join-semilattice vs Upper-semilattice ?! definition problem ?!

In mathematics, a join-semilattice (or upper semilattice) is a partially ordered set that has a join (a least upper bound) for any nonempty finite subset. I ran into some definition challenge. I ...
0
votes
1answer
21 views

Prove that $w/w_0$ (no idle over minimum possible) $\le 2-1/n$ for any set of tasks on an n processor system

$w/w_0 $ $\le 2-1/n$ I've noticed this problem in a couple of discrete math and algorithm analysis textbooks. Many of them prove it for n=2, but I want to prove it for all n. The idea is that we ...
1
vote
2answers
53 views

Shortest Path on Specific Graph with one Property !?

I stuck in one challenging question, I read on my notes. An undirected, weighted, connected graph $G$, (with no negative weights and with all weights distinct) is given. We know that, in this ...
0
votes
0answers
21 views

Gauss elimination using 4 digit arithmetic with rounding

I wanted to solve the following system with 4 digit arithmetic and rounding, $0.00300x_1+59.14x_2=59.17$ $5.291x_1-6.130x_2=46.78$ I know how to do Gauss elimination, but i am confused about what ...
0
votes
2answers
29 views

Proving that the set of languages over an alphabet Σ is a monoid regarding concatenation

I'm practicing proofs and would like to prove that the set of languages over an alphabet $\Sigma$ is a monoid regarding concatenation by showing that the following statements are true: There is a ...
2
votes
1answer
30 views

Non regular language that satisfies pumping lemma

Let $$L = \{ ww^rx \mid w,x \in \{a,b \}^+\} $$ where $\{a,b\}^+$ means the set of words over $\{a,b \}$ that has at least length 1, and $w^r$ is the reverse of $w$. I'm trying to prove that this ...
1
vote
1answer
36 views

Why is Mergesort $O(n)$ rather than $O(n\log{n})$?

Assume we want a divide-and-conquer algorithm that finds the max and min of a set $S$ with $n = 2^k$ elements, e.g. mergesort. The recurrence for time complexity is $T(n)=2*T(n/2) +2$, for $n>2$, ...
0
votes
1answer
341 views

Y-Axis units on FFT graph

A 50Hz sinusoid wave with a voltage range of +/-20V is sampled at 512Hz for 1 second. No bias or phase shift are present. The signal is run through an FFT. The result is one spike at 50Hz on the ...
2
votes
3answers
49 views

How many ways can we split a group of $n$ elements into groups of different sizes such that each group contains more than $1$element

let's assume $p[n]$ is the name of this partitioning method Let's see some examples: $n=3$: all possibilities are: $[(3,0),(2,1),(1,1,1)]$ all cases don't meet the condition $minSize > 1$ so ...
1
vote
0answers
20 views

Does bitwise-XORing substrings results in a uniform distribution?

Let's say I have an integer $k$ whose bit string representation can be exactly divided into $l$ substrings of length $\log_2(m)$. Let's call each one of these substrings $B_i(k)$, for ...
0
votes
1answer
324 views

Calculating normals for a polygon mesh (3D computer graphics)

I want to write a program to generate arches, a common architectural form, and export them to a wavefront object format for sharing with various three dimensional graphics editors. To do this, I need ...
2
votes
3answers
86 views

Proving the infinite sum of $1/2^i$ without induction

Prove $$\sum_{i=1}^n \frac{i}{2^i} = 2-\frac{n+2}{2^n} $$ Pretty trivial to do with induction, but as a practice problem for solving recurrences we have to do this only by repeating $\sum_{i=1}^n ...
2
votes
1answer
33 views

How can a Moore machine be converted into an equivalent Mealy machine and vice versa?

Moore machine is a finite-state machine whose output values are determined by its current state only. Mealy machine is a finite-state machine whose output values are determined both by its current ...
2
votes
0answers
54 views

Trouble with induction on the length of a word

In the accepted solution of the question If L is regular, prove that $\sqrt{L}=\{w:ww\in L\}$ is regular the answerer made the claim that "What's left is to show that $δ ′ (q_{0}' ,w)=h$ , which can ...
1
vote
2answers
72 views

Prove the following by using mathematical induction

If we define the alphabet such that $$ \Sigma = {\{a,b}\} $$ and let $w$ be a string over it. I'd like to prove $$ ( \operatorname{comp}(w))^R = \operatorname{comp}(w^R) $$ where $$ w^R$$ and ...
0
votes
2answers
30 views

Formula to calculate password cracking time in years, taking into account Moore's law and known adversary guessing power [closed]

We know that the biggest human rights violators in human history are capable of one trillion password guesses per second as of approximately January 2013. Assume that the 1 trillion guesses per ...
3
votes
1answer
68 views

The Ackermann's function “grows faster” than any primitive recursive function

I am looking at the proof that the Ackermann's function is not primitive recursive. At the part: "We will prove that Ackermann's function is not primitive recursive by showing that it "grows ...
1
vote
0answers
18 views

Runtime of recursive algorithm - Master's Theorem

I wrote a computer program that solves a question, and I am interested in knowing what is the runtime. My aim is for $O(\log n)$, and I'd like someone more experienced (and smarter?) to review my ...
0
votes
1answer
9 views

A graph that all its vertices are vertices cut [duplicate]

Is there any graph that all its vertices are cut vertices? I couldn't find a graph with this property? and if there is no such graph how can i prove that it does not exist.
0
votes
0answers
30 views

how can i find a grammar for this language?

The language is $L = \{a^i b^j c^k | k = (i + j)^2, i > 0, j > 0\}$. To produce a's and b's I have this solution: S -> aS | aB B -> bB | bC but for producing the right number of c's i have no ...
0
votes
1answer
457 views

Ceiling to Floor Function Conversion Proof

I am working on a proof to convert a ceiling of a fraction to a floor of a fraction. I found this: \begin{aligned} q=\left\lceil \frac{n}{m} \right\rceil \;&\Leftrightarrow\; \frac{n}{m} \leq q ...
1
vote
0answers
47 views

Solving the GCD m = 735, n =252

I understand everything except the values in $s_i$ and $t_i$ how do we get those values??? Can anyone please elaborate. I have no idea what the formula is for calculating the values in $s_i$ and ...
1
vote
3answers
65 views

Are there infinite sequences not reproducible by finite algorithms?

Let me know if this is a repeat question. I was thinking that sequence of integers we deal with (e.g., the digits of $\pi$, the prime numbers, the Fibonacci numbers, pseudorandom numbers) seem to be ...
-1
votes
0answers
53 views

Is there a formula for $\sum_{r=1}^x({n+r-1})Cr$? [duplicate]

I have an algorithm who is something like this : MOD = 1000003 ans = 0 while (r) : ans = (ans + nCrMod(n + r - 1, r, MOD))%MOD r-- print ans ...
2
votes
0answers
47 views

Sum of reversed numbers? [closed]

Here is the question that I'm confused with - Define $reverse(N)$ which reverses a given integer. For eg - $reverse(35)$ = $53$ Now, some natural numbers $N$ have a property that $N + ...
1
vote
0answers
11 views

The correctness of fast chung-lu model

This paper (fast generation of large scale social networks with clustering) mentioned in its proposition 1 that "in a regular graph, the probability of an edge existing in the fast Chung Lu model is ...
2
votes
1answer
28 views

Show that the function floor-log is primitive recursive

I have been stuck on this problem for a while and I was hoping someone could help me with it. This is for my computer science automata and formal languages class. Given an integer $b$ greater than or ...
2
votes
1answer
49 views

Why in RSA, the public exponent $e$ must be coprime with $\phi (n)$

I'm trying to understand the RSA cryptosystem, and that's what I know so far: If we think about some number $m$ as the message, then we are searching a $e$ and $d$ such that $$m^{ed} \equiv m \ \ ...
1
vote
1answer
70 views

Clarification of the statement of the Pumping Lemma

In class we were told that Pumping Lemma states: "Let A be a regular language over $\Sigma$. Then there exists k such that for any words $x,y,z\in\Sigma^{*}$, such that $w=xyz\in A$ and $\lvert ...
0
votes
1answer
13 views
1
vote
1answer
39 views

How many binary bit strings of length 32 are there

How many binary bit strings of length 32 are there? I think I know the answer but I'm not sure...wouldn't it just be $2^5$ ?
2
votes
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. ...
0
votes
1answer
757 views

How to calculate the angle between 2 vectors in 3D space given a preset function

In my application, I am attempting to connect 2 points in 3d space with a cylinder via a function taking in 2 vectors. I understand that I need the angle to apply to the cylinder. As I understand, I ...
-2
votes
0answers
31 views

Formulate an equivalent CFG that is not ambiguous

Given is the following grammar G: S -> SS | T | ab T -> aTb | empty string a) Formulate an equivalent CFG that is not ambiguous. It suffices to give the rules.
0
votes
0answers
18 views

Distance between line segments of sameline

I have line segments which are from the same line (in real wall, measured with sensors). with below values ...
1
vote
1answer
21 views

Solving a linear program using just one call to a procedure that gives a feasible solution.

Suppose we have some procedure $F$ which takes any set of linear constraints and either returns either infeasible or returns a vector satisfying these constraints. If we now take a linear program ...