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

Refer Back to an old question: What is an general machine way to find $x^3\equiv 10 \pmod{990}$?

refer back: How to solve $x^3\equiv 10 \pmod{990}$? That question had been put on hold, and therefore no answer will be in the machine proof method, i want to know the exact way how do the common ...
2
votes
1answer
22 views

How to show that recurrence $T(n) \in \Omega(n^{0.5})$ using proof by induction?

This is recurrence $T(n)$ $ T(n) = \begin{cases} c, & \text{if $n$ is 1} \\ 2T(\lfloor(n/4)\rfloor) + 16, & \text{if $n$ is > 1} \end{cases}$ This is my attempt to show that $T(n) \in ...
0
votes
1answer
16 views

Does this recurrence relation run in $\theta$(n)?

This is the recurrence relation I am trying to solve $T(n) = 2T(\frac{n}{4}) + 16 $ $T(1) =c $ I broke down(solved this reurrence relation) to $\sqrt2*c*n + 32 * \sqrt2* n - 32$ which runs in tight ...
1
vote
0answers
19 views

The graph has an Euler tour iff in-degree($v$)=out-degree($v$)

I am looking at the proof that $G$ has an Euler tour iff in-degree($v$)=out-degree($v$), that I found at this site: www.cs.duke.edu/courses/fall09/cps230/hws/hw3/headsol.pdf (Problem 2) A simple ...
2
votes
1answer
50 views

Prove that sets don't intersect

I am trying to solve a computer algorithm problem that boils down to solving the following. I would appreciate some mathematician assistance on the proof. So here goes: Having: Set $S$ - rational ...
0
votes
1answer
20 views

Solving Recurrence Relations with Geometric Series

If given the following problem... $$4T \left(\frac n2\right) + c$$ after getting the pattern down you see the following $$4^k T\left(\frac {n}{2^k}\right) + 3^{k-1}c + 3^{k-2} c + \cdots + 3c + c$$ ...
0
votes
0answers
12 views

Questions regarding notation (multiple variables, rounding)

I am calculating the coordinates of the Center of Gravity for a 3D volume using the following pseudocode (where A denotes the dimension length and cogA denotes the COG for that dimension) ...
2
votes
1answer
27 views

Given the graph below, use Dijkstra’s algorithm to find the shortest path (More details included)

So I've found out a few things and was wondering if someone could verify if I'm doing this correctly. So here is an example I've been given: Here is the solution to that example: Now here is the ...
2
votes
0answers
46 views

Tree decomposition by hand for understanding

I am implementing "algorithm 2" from the paper "Treewidth computations I. Upper bounds" by Bodlander and Koster[1,page5] and I am not sure if I understand it or not. As I understand, the algoritm ...
1
vote
0answers
8 views

Determining the sequence that yields a balanced search tree in the form of a recurrence / sequence

Let's say I have a sequence of (distinct) monotonically increasing numbers S. I'll want to add them sequentially to a Binary Search Tree (BST) but as the numbers ...
0
votes
1answer
14 views

Prove a language isn't regular using Myhill-Nerode thm.

Let $L$, a language above $\Sigma = \{x,y, (,),+,* \}$. $L$ can be defined recursively as follows: Basis Clause: $x$ and $y$ are in $L$. Inductive Clause: If $\alpha$ and $\beta$ are in $L$, then ...
1
vote
2answers
16 views

Computability: is there an alternative method to decide this language?

For my computability revision I am trying to decide the language, $$L = \{ \text{all binary strings containing the pattern 001 (not necessarily in consecutive places)} \}.$$ I believe that I can do ...
1
vote
0answers
40 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
11 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
27 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
22 views
-1
votes
1answer
19 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
28 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
15 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
18 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
23 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
20 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
29 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
22 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
32 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
40 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
12 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
17 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
38 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
38 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
34 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
60 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
41 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
72 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
56 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
14 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.