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

Additive combinatorics in Hamming weights of addition of numbers modulo $2^n$ with prescribed Hamming weight

I wonder if anyone could point me to a reference about the following type of combinatorics problem: Fix $n $. For an integer $k \in [n] = \{1, \ldots, n\}$, let $A(k)$ be the set of integers in $[0, ...
0
votes
1answer
26 views

How does state transition matrix works

Suppose I have a simple vehicle moving in 2D. The state vector for the vehicle is X=[x y vx vy ax ay], that is, it contains the position (x,y), the velocity (vx, vy) and the acceleration (ax, ay) of ...
0
votes
1answer
33 views

What do these propositions show?

I am going through some lecture slides and have come to something that I do not understand. I get the general idea of what he is trying to do but I am not sure how the propositions show this. The ...
4
votes
4answers
71 views

Origin of the phrase 'in polynomial time'

What is the origin and context of the phrase 'solvable in polynomial time' in computer science? Are they related to the notion of 'polynomials' in mathematics?
3
votes
1answer
30 views

How do you solve the recurrence relation $T(n) = cn(dn + T(n-k))$?

How do I come up with a big-O approximation to $T(n) = cn(dn + T(n-k))$ where $c, d \in \Bbb{R}$ are fixed. $T(n)$ is the running time of a recursive algorithm. This seems difficult as usual. :)
3
votes
1answer
33 views

Algorithms for a “Travelling Salesman with radius / time limit”?

I can't talk about my real-world situation I need this for, but imagine you walk around a warehouse that has things with RFID tags scattered around in it, and you have ten minutes to get within 2m of ...
1
vote
0answers
19 views

The significance of odds and logs in Bayes Naive Classification

I do understand the concept of Naive Bayesian classification, as it tries to calculate the probability of an outcome of a class given multiple evidences. It comes from the Bayes theorem and it is ...
0
votes
2answers
36 views

Is constructing a DFA enough to prove that a language is decidable?

If the axiom $A_{DFA}$ is known to be decidable, would simply constructing a $DFA$ diagram be enough to prove that $L(M)$ is decidable? Most of what I can find on the internet tells me that you need ...
1
vote
1answer
21 views

Deciding set of all Turing machine codes of TMs accepting languages of cardinality $\leq 10$.

Problem: I need to show that the following language is decidable and if not, if $S$ or $\overline{S}$ is partialy decidable language. $S=\{w_e\;|\;|L(M_e)|\leq 10\}$ That is set of all Turing ...
2
votes
0answers
28 views

Probabilistic methods and equations over $m$-dimensional space

Given a set $A$ of $n$ different points in the space $(\mathbb{Z}_p)^m$ (assume $p$ is prime), and given $\delta>0$. show the following property holds for a big enough $n$ and $p$ (you can demand ...
1
vote
0answers
36 views

question about isolation lemma.

Given the set $\mathcal{F}\in\mathcal{P}(\{1,...,m\})$, I need to provide it with probability $\frac{1}{2}$ a weight function $w:\{1,...,m\}\rightarrow\{1,...,n\}$ such that there will be a single ...
0
votes
0answers
18 views

How can a program calculate the distance along a road from point $A$ to point $B$?

Just as an example, when I go to Google Maps and get directions, it tells me how far along a road I need to travel to get to my next turn. For example, when I get directions from SeaWorld San Antonio ...
1
vote
2answers
32 views

Unprovable behavior of a turing machine

The wikipedia-article for the P-NP problem [1] says there are three possible answers to the P-NP-problem: $P=NP$ $P\neq NP$ $P=NP$ is independent of ZFC The third possible solution seems to be ...
3
votes
2answers
43 views

Understanding mathematical notation for coding problems.

The majority of my questions revolve around code (thus my activity on stackoverflow), but I've been going over interview question that assume a good understanding of mathematical notation. I don't ...
0
votes
2answers
51 views

Fewest operations on an algorithm?

I'm very stumped on this problem I have and was wondering if anyone could lend me a hand here? Suppose that you have two different algorithms for solving a problem. To solve a problem of size $n$, ...
0
votes
1answer
22 views

Understanding Kleene star in relation to regular expressions

I have a homework problem for my intro computation class where I have to write a regular expression for an NFA. In order to help understand if my language is correct- I want to post some example ...
-1
votes
1answer
39 views

Graph Algorithms Question (Design and Analysis)

I'm trying to design the algorithm and answer these two questions but can't produce a solution. I've tried drawing the pictures for the graph as well.
3
votes
1answer
33 views

Computerized search for integer identities. Suggestion of representation

I'm writing an app in Nim to search for curious integer identities such as those ones listed on:MathWorld: Divisor Function where it says "curious identities derived using modular theory". The ...
0
votes
2answers
27 views

$[ \cdot ]_{\times}$ operator meaning

In reading articles about stereo image rectification, I've come across the operator $[ \cdot ]_{\times}$ in a few places. One example is here where it says When we have determined a decomposition ...
0
votes
1answer
40 views

how to take the dual problem of a problem that has a sum in it?

I'm learning about dual problems and was trying to get to an understanding of how to take the dual of a problem that has a sum in it. For example if we try to optimize the sum of all values while ...
1
vote
1answer
26 views

Cocke-Younger-Kasami (CYK) Proving a word is in a language

Using CYK algorithm I need to figure out whether the word abbabb is a word of the language of the following grammar. I think I have completed the problem correctly but I'm not sure, I'm hoping ...
1
vote
0answers
31 views

Big O Notation Clarification

Working through a textbook on algorithms (CLRS intro to algorithms) and just wanted to see if someone could help me understand one of the exercises at the end of a chapter. Problem: Is $n^{2 + 1} = ...
0
votes
1answer
18 views

Designing a DFA to accept a string

I have created the following FA Im i correct?
0
votes
1answer
12 views

Formula to find an angle of point on a coordinate plane

Given a plane and an arbitrary (x,y) point, is there a succinct formula to find the angle of that point against the positive y-axis? For example, pictured below the green point is 0 degrees, blue 45 ...
0
votes
1answer
44 views

Less-than full rank rectangular matrix P has a unique vector c s.t. Pc = 0-vector

Below is a passage from a computer vision paper on projective geometry (emphasis added): A projection from $P^3$ into $P^2$ is represented by a 3×4 matrix $P$,whereby a point x maps to the point ...
0
votes
1answer
32 views

Proving that $\mathscr L=\{0^n \big|\text{n is the square of a natural number }\}$ is non regular using the pumping lemma

I need to prove that the language $\mathscr L=\{0^n \big|\text{n is the square of a natural number}\}$ is non regular using the pumping lemma My try: $\mathscr ...
-1
votes
1answer
43 views

Time Complexity

Prepping for an exam and wondering whether I correctly calculated the time complexity. Function is given as: $function XYZ(n:integer)\\ begin for\ i:=1 \ do \ 2*n^2 \ do;\\ ...
1
vote
1answer
11 views

Proving that the language $\{w\in \{a,b\}^* \big|\#_a(w)< \#_b (w)\}$ is non regular using the pumping lemma

I need to prove that the language $\mathscr L=\{w\in \{a,b\}^* \big|\#_a(w)< \#_b (w)\}$ is non regular using the pumping lemma My try: $\{a,b\}^*=\{\epsilon,a,b,aa,ab,ba,bb,aaa,aab,\dots\}$ ...
0
votes
1answer
22 views

How could I design a turing machine that prints all natural numbers on its tape in order?

How one could implement a turing machine that prints all natural numbers of its tape in order. Two consecutive numbers are separated on the tape with the symbol #. The tape should look like this: ...
0
votes
0answers
35 views

How could I modify a Turing machine that attempts to move the head past the leftmost square(crash) on some inputs so that it doesn't crash at all?

Suppose that M is a TM that crashes on some inputs. How would I modify M so that the new machine accepts the same language but does not crash on any input ?
-1
votes
1answer
61 views

Show that every finite subset of $\{0,1\}^*$ is recursive [closed]

How can I show that every finite subset of $\{0,1\}^*$ is recursive ?
0
votes
1answer
44 views

Likelihood for a random hash function not to be surjective

Let us define a hash function $$\begin{align*} H \colon A &\to B\\ a &\mapsto b \end{align*}$$ $$|A| \geq |B|$$ Assuming it is perfectly random (Hyp 1), we estimate the probability that ...
1
vote
1answer
24 views

Checking if Post Correspondence Problem has a Solution

I have the following problem I think that solution is wrong because x1=b and y1=b3(cube).They do not match,So how is this solution possible?
0
votes
0answers
17 views

Finite element boundary conditions

I have a boundary condition given by $\mathbf{n}\cdot \nabla m=\phi$, where $n$ is a vector normal to a surface, $m$ is a physical quantity (say mass) and $\phi$ is a constant. The boundary condition ...
0
votes
0answers
17 views

Conversion of CFG to Chomsky Normal Form

I have the following question I have answer for the first one as S->C1S C1->C2A C2->a S->C2A ...
0
votes
0answers
25 views

Does 3-SAT reduce to 3-CNF-SAT?

I know that SAT goes to 3-SAT and SAT is reducible to CNF-SAT and CNF-SAT is reducible to 3-CNF-SAT but is 3-SAT reducible to 3-CNF-SAT? They are not the same thing though right because cnf makes it ...
2
votes
0answers
19 views

Writing a regular expertion for the language $L=\{0^n1^m|n\equiv m(\mod 2)\}$

I need to write a regular expertion for the language of all the binary words that contains continuum of even number of zeros and after that even number of ones or odd number of zeros and after that ...
0
votes
1answer
11 views

Language of all the binary words that not contains continuum of more then $3$ zeros

I need to write a regular expertion for the language of all the binary words that not contains continuum of more then $3$ zeros, for example $0011110100\in L,\,\,\,\,\,\,\,\,\,11000001100\notin L $ ...
1
vote
1answer
40 views

Design a DFA to check whether the Given Number is Even

I have the following question I have designed the following A Binary String is even if it is ending with 0 and odd if its ending with 1.I have applied this.Im i right ? UPDATE:
0
votes
1answer
24 views

Language of all the binary words that contain $010$ at least twise

I need to write a regular expertion for the language of all the binary words that contain $010$ at leasr twise, note that $101010$ should be accept too because $1\color{blue} {010}10$ and ...
0
votes
0answers
17 views

Minimization of DFA

I have the following question I have minimized the DFA as the following since the states can only be partitioned to [S0][S1 S2] EDIT: Is my Minimization correct?
1
vote
1answer
23 views

Graph thoery tree rank sequence

let $T=(V,E)$ be a tree with $n$ vertices , which his degree sequence is $d_1 \le d_2 \le ... \le d_n$ if and only if $d_1\gt 0$ and $d_1+d_2+...+d_n=2(n-1)$ $$$$ i managed to prove it one direction ...
1
vote
2answers
37 views

Checking whether a Language is Regular

I have the following question My approach in solving this problem would be. For a language to be regular we should be able to create a Finite Automata that could accept it.In the above example n ...
0
votes
1answer
24 views

Pumping lemma for context free. How do I define the string 'w' and define cases?

I am new to the pumping lemma for context free grammars. I have read books and researched online about the pumping lemma, however I am finding it difficult to understand the actual concept and how to ...
0
votes
0answers
40 views

nocomputable function f such that x is not in the Halting Problem iff f ( x ) belongs to set of Kolmogorov-random strings

taking clue from this question set of Kolmogorov-random strings is co-re the paper mentioned in the above link talks about the non existence of a computable function how can I show that there is ...
1
vote
2answers
45 views

Use Weak Mathematical Induction to show that in a full binary tree the number of leaves is one more than the number of internal nodes

Use Weak Mathematical Induction to show that in a full binary tree the number of leaves is one more than the number of internal nodes (i.e., $L = I + 1$). Induct on the number of leaves. What is the ...
0
votes
1answer
14 views

NFA Containing 'a'

I have L={Contains 'a'} and Alphabet(E)={a,b} Can i create a NFA Like this
1
vote
1answer
20 views

Checking if $L_1 \cup L_2$ is regular language

Let $L_1=\{a^n b^r|n \geq 1, r\geq1,n=r\}$ $L_2=\{a^n b^r|n \geq 1, r\geq1,n\neq r\}$ be a non regular languages $L_1 \cup L_2$ is regular? I think that $L_1 \cup L_2$ is regular because we ...
1
vote
1answer
47 views

Is a Turing machine on an arbitrary (finite) alphabet equivalent to one on {0, 1}?

Brief context: I'm trying to understand why a Universal Turing Machine exists, on a tape with alphabet $\{0, 1\}$. I think I can see that a $3$-tape Turing machine can represent a Universal Turing ...
1
vote
0answers
36 views

Polynomial time algorithm for variety of an ideal

Is there a polynomial time algorithm to determine the variety of a zero dimensional ideal in $k[x_1,\ldots,x_n]$? Or is it a NP hard problem?