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
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
23 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
58 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
33 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
29 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
61 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
131 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
88 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
65 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
29 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
22 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
77 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
55 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
13 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
87 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
34 views

mpz_class as vectors element number [closed]

so I have this function ...
0
votes
1answer
26 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
49 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
59 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
59 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 ...
0
votes
0answers
19 views

How did we get the relation?

The fractional knapsack has the greedy choice property. Proof: Let`s consider that the ratio $\frac{V°}{w°}$ is maximal. This assumption implies that $$\frac{V°}{w°}\geq \frac{v}{w}\text{ for ...
2
votes
1answer
28 views

Average case complexity for checking if list is sorted

Consider the obvious algorithm for checking whether a list of integers is sorted: start at the beginning of the list, and scan along until we first find a successive pair of elements that is ...
2
votes
0answers
46 views

Hashing Probability

I have just started to learn about the topic of hashing. I understand how it works and the difference between closed address and open address, but do not know how to calculate the probability of a ...
0
votes
1answer
35 views

Greedy choice property

There are two versions of the Knapsack problem, the integer and the fractional one. The difference between the integer and the fractional version of the Knapsack problem is the following: At the ...
0
votes
0answers
8 views

How to find a strictly increasing sequence of words $(t_i)_{0\leq i\leq n}$ of maximum length ?

Let $L=\{0,1\}^*$ be the set of all words consisting of $0$ or $1$, we define an order in $L$ by: $$\begin{align}\forall (x,y)\in L^2 && \big( x\leq y&&\Leftrightarrow y=x\text{ or ...
0
votes
0answers
13 views

a proof about Gastnel's Method

this is a proof problem in in the book that i meet consider the linear system $Ax=B$,where $A$ is SPD matrix.Consider a projection step with $\mathcal{K}=\mathcal{L}=span\{v\}$,where $v$ is some ...
7
votes
0answers
185 views

How to maximize the number of operations in process

In my research project I have encountered the following problem, concerning a tuple of words in the formal language $L=\{0,1\}^*$, with $\epsilon$ denoting the empty word. If we are given an ordered ...
0
votes
0answers
88 views

The problem of making change for $n$ using the fewest number of coins

Consider the problem of making change for $n$ cents using the fewest number of coins. Assume that each coin’s value is an integer. Describe a greedy algorithm to make change consisting of quarters ...
-1
votes
1answer
85 views

Application of the Knapsack Algorithm

I want to apply the Knapsack algorithm at the following: n = 4 (# of elements) W = 5 (max weight) Elements (weight, benefit): (2,3), (3,4), (4,5), (5,6) The ...
1
vote
0answers
43 views

The algorithm yields optimal ternary codes

Steps to build Huffman Tree Input is array of unique characters along with their frequency of occurrences and output is Huffman Tree. Create a leaf node for each unique character and build a min ...
0
votes
0answers
42 views

Are the expressions (a/b) %c and (a%(b*c)) /b equivalent?

As far as I know, to determine (a/b)%c, we need to determine (b^-1)%c which can be done using extended euclid, fermat's theorem, euler's theorem or there may be some other way, but what we must need ...
1
vote
1answer
69 views

A decision problem that is Cook reducible to its complement

I'm taking an algorithms course and we are covering polynomial time reductions, and I've read online that many decision problems are polynomial-time reducible to their complements. Can anyone give me ...
0
votes
1answer
27 views

Prove that $ (lg\; lg\; n)^k=o(lg^\epsilon n)$ for all $0<k,\epsilon$

I am stuck at this problem for a long time: Prove that $ (lg\; lg\; n)^k=o(lg^\epsilon n)$ for all $0<k,\epsilon$ I tried to show that $\lim_{x\to\infty}\frac{ (lg\; lg\; x)^k}{lg^\epsilon ...
2
votes
2answers
125 views

How much knowledge of math do I need before taking bachelor of software engineering ?

I asked this question before, but now I knew who to form it correctly after doing some research for months. It always puzzles me what someone need to know before enrolling in bachelor of software ...
-1
votes
2answers
131 views

What is the algorithm to add binary numbers with boolean operations? [closed]

What is the algorithm to add up two binary numbers using only boolean operations (negation, conjunction, disjunction) in linear time? Also the program flow needs to be "linear" as well, meaning there ...
2
votes
2answers
21 views

Find the minimum value of $n$ such that $\sin^n(c)<\varepsilon$ for some small constant $\varepsilon>0$

Let $c$ be a constant such that $0 <c \le \pi/2$ and $\sin(c) \ne 0$. Question: What is the minimum value of $n$ such that $\sin^n(c)< \varepsilon$ for some small constant $\varepsilon >0$ ? ...
0
votes
3answers
69 views

Decrypt the following message that was encrypted using: Caesar’s cipher: WHVWWRGDB

Decrypt the following message that was encrypted using: (a) Caesar’s cipher: WHVWWRGDB I'm told to decrypt the message using Ceasar's cipher but they don't tell me the key shift so how in the world ...
1
vote
1answer
50 views

Huffman Encoding Symbol Probability [duplicate]

Prove for two symbols a and b, if p(a) >= p(b), then according to Huffman encoding algorithm, the resultant code length L(a) <= L(b). I did several examples of this and it is true. But how can I ...
1
vote
2answers
90 views

Huffman Encoding Proof Probability and Length

If the frequency of symbol i is strictly larger than the frequency of symbol j, then the length of the codeword for symbol i is less than or equal to the length of the codeword for symbol j. I ...
1
vote
1answer
46 views

Write the regular expression of the language that the DFA accepts.

I am given a DFA and I have tried to write the regular expression of the language that it accepts. This is the DFA that I am given: I have found some words that the DFA accepts: ...