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

Construct Context Free Grammar for $\{0,1\}^*-\{www~|~w\in\{0,1\}^*\}$

I'm working on the exercises in "Problem Solving in Automata, Languages, and Complexity" and I've run into the below problem. The question asks to construct a CFG for the language , and I just can't ...
0
votes
0answers
17 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
28 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 ...
1
vote
2answers
53 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
17 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
22 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
31 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
30 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
28 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 ...
5
votes
0answers
57 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
25 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
54 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
45 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
21 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
29 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
47 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
28 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
19 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
27 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
22 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?
2
votes
1answer
38 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
40 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
22 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
57 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
30 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
26 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
51 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
65 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
90 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
2answers
98 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
86 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
63 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
26 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
21 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.
2
votes
2answers
75 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
52 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
76 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
2
votes
0answers
53 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
12 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
72 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 ...
3
votes
1answer
80 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
votes
1answer
29 views

mpz_class as vectors element number [closed]

so I have this function ...
0
votes
1answer
23 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) = ...
0
votes
0answers
19 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 ...
2
votes
1answer
46 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
2answers
55 views

Finding a grammar for given language

So for this problem we are given a language and we have to find the grammar for that set. I am confused and what the constructors should be. The language in this problem is: $\{bb, bab, baab, ...
0
votes
2answers
56 views

How many ways are there to sit 4 people from a group of 10 people around a circular table where two sittings are considered

How many ways are there to sit 4 people from a group of 10 people around a circular table where two sittings are considered the same when everyone has the same immediate left and immediate right ...
1
vote
1answer
51 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$ ?
1
vote
1answer
22 views

How to show that a language is regular?

Let $L$ be a regular language over $\Sigma$. Show that: $$\left\{ x_1x_2 \dotsm x_k \mid x_1,x_2,\ldots , x_k \in \Sigma, \exists y_1, y_2, \ldots, y_k \in \Sigma: x_1y_1\dotsm x_ky_k \in L ...