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
3answers
67 views

Turing Machine divisibility by 6 [closed]

I need to design a TM to check if a binary number can be dividied by 6. I don't know how to design it. Thanks
0
votes
0answers
12 views

What is the size of Quotient in integer division with remainder?

Suppose $a=(a_{k-1},\dots,a_1,a_0)_Z$ and $b=(b_{l-1},\dots,b_1,b_0)_Z$ then $ab=m=(m_{k+l-1},\dots,m_1,m_0)_Z$ so $m$ is a $(k+l)$-digit number in the base $Z$. Let $b_{l-1}>0$ and $a=bq+r$ where ...
0
votes
4answers
107 views

Books recommendation on Graph Theory (Beginner level)

What are some of the best books on graph theory, particularly for the beginners. Thank you.
-6
votes
1answer
42 views

Cardinality of two power sets Question [closed]

Problem 5 (2 pts) Given two finite sets A and B with the cardinalities A= n and B = m. (a) What is the cardinality of the powerset P(A x B)? (b) How many functions is there from A to B?
1
vote
0answers
41 views

Optimal object in category? Metric, objective function on category objects. Optimization over category?

Is there notion about optimal object in category (that can be found by some algorithms, or - more importantly - that can be constructed (if unknown) by some algorithms), about metric and objective ...
0
votes
1answer
25 views

What is the complementary slackness conditions for a primal dual pair?

I'm trying to understand what exactly the complementary slackness conditions for a primal dual pair is and how it's calculated. I understand that we have a given linear programming problem. And that ...
1
vote
0answers
52 views

Levenberg-Marquart with Hessian and gradient

I am minimizing a sum-of-squared-differences function using the Levenberg-Marquardt method. The off-the-shelf numerical implementations I have have looked through (MATLAB, Numerical Recipes in C ...
2
votes
1answer
48 views

Understanding Turing Machines: Recognizable and Decidable langauges

I've searched tons of resources and while conceptually I understand the turing machine itself and what it does- I'm a bit stuck on Turing Recognizable and Turing Decidable languages and I'm not sure ...
5
votes
1answer
61 views

Concrete Mathematics - How is it that A(2n + 1) = 2A(n)?

This is might sound like a stupid question, and I'm pretty sure I know the answer to this question, but I'm not certain. Anyway, on page 14 of Concrete Mathematics, the author has just finished going ...
0
votes
0answers
76 views
5
votes
2answers
401 views

Programming and ZFC

Suppose I have a simple program that implements an algorithm (say depth-first search), written in a simple imperative programming language with the standard for loops, recursions, conditional ...
0
votes
1answer
25 views

what is the data byte encoded in binary Hamming code?

the problem I am presented with is a binary hamming code shown below: 011101000100, what was the data byte encoded and sent from this hamming code? and the solution is ...
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
28 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
72 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
21 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
23 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
33 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
52 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
25 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
19 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
34 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
12 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 $ ...