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
0answers
6 views

Time complexity of a recursive function on a given set

I am computing a function $fun$ which is defined as follows. $fun(m,s)=\sum_{\sigma_{p}\subset s;|\sigma_p|=m}\left [\prod_{i}i\in \sigma_p \sum_{j=1}^{|s-\sigma_p|}\sum_{\gamma_p\subset ...
0
votes
2answers
22 views

Why can any values of C and N be chosen for the proof of Big-Oh?

In my CS course, they have taught us that, when proving Big-Oh, you can choose any positive integers to be C and k, following the definition. Based on that, they have taught us two different ways of ...
0
votes
0answers
15 views
-1
votes
1answer
12 views

Determine which of these are strongly connected. Explain why or why not. [on hold]

I'm not sure how to determine this.. Is there a certain formula?
1
vote
2answers
9 views

Given a complete graph of n vertices Kn (has all possible edges – one edge between pair of vertices).

Given a complete graph of n vertices $K_n$ (has all possible edges – one edge between pair of vertices). Use counting to find a formula in $n$ for the number of edges in the graph. I know that the ...
1
vote
0answers
14 views

A doubly infinite tape Turing machine can simulate a ordinary Turing machine, a rigorous proof.

Let $M$ be a ordinary Turing machine. Intuitively, we can say that $M$ can be transformed to a machine $M_D$ with doubly infinite tape, by placing to the left on every input $w = w_1, \dots , w_n$ ...
0
votes
0answers
11 views

(a) Given the graph below, for each pair of vertices given in (i) and (ii) gi

so I think I've figured out part a) but I'm not sure.. my solution is: a) part i) $v_1 \rightarrow v_3 \rightarrow v_7 \rightarrow v_5 \rightarrow v_8 \rightarrow v_4 \rightarrow v_2 \rightarrow ...
1
vote
1answer
14 views

Graphing digraphs with the following vertex set

Just want to make sure I did this correctly.. I think I did part a) correctly? Here is my solution for part a) Not sure how to do b) and c) though. Any advice would be great. Thanks in advance
1
vote
1answer
14 views

Is $L = \{0^{i}1^{i}0^{j}1^{i} | i, j > 0\}$ a context free language?

Is the following argument correct? $L = (A \circ B) \cap C$ where, $A = \{0^{i}1^{i}$ $|$ $i > 0\}$ $B = \{0^{j}1^{i}$ $|$ $i, j > 0\}$ $C = \{0^{i}1^{j}0^{k}1^{i}$ $|$ $i, j, k > 0\}$ We ...
0
votes
1answer
25 views

Elaboration needed on a section of a published paper about dictionary learning

I will be doing my master thesis on dictionary learning, and I am trying to understand basic concepts of the subject reading the following paper: K-SVD: An Algorithm for Designing Overcomplete ...
2
votes
0answers
28 views

Where can I learn more about the “else” operation / “else monoid”?

(The set of natural numbers $\mathbb{N}$ starts at $0$ for me.) Let $X$ denote a set, and define $X_\bot = X \uplus \{\bot\}.$ Let $\mathbf{else}$ denote the binary operation on $X_\bot$ defined as ...
1
vote
1answer
20 views

Representing Several IF statements inside a FOR loop in Math Notation

I wish to correctly represent several IF statements within a for loop in math notation. The FOR loop can be represented as: ...
0
votes
2answers
30 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
39 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 ...
2
votes
0answers
17 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 ...
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 ...
1
vote
1answer
34 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 ...
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
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
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 ...
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
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 ...
2
votes
1answer
32 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
37 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
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
0answers
35 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
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 ...
1
vote
0answers
21 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 ...
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
58 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 ...
2
votes
3answers
87 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 ...
0
votes
1answer
29 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
2answers
37 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
71 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
2answers
55 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 ...
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 ...
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
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
66 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
vote
2answers
38 views
-1
votes
0answers
54 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 ...
1
vote
1answer
71 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 ...
2
votes
1answer
52 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 \ \ ...
-2
votes
0answers
32 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
1answer
13 views

mpz_class as vectors element number [closed]

so I have this function ...
0
votes
1answer
19 views

How many 5-permutations of Q are there? (No repetition of character within a string and order matters)

How many 5-permutations of Q are there? (No repetition of character within a string and order matters) Q = {A, B, C, D, E}. So I think i'm supposed to be using the formula $(^n_k) = ...