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.

learn more… | top users | synonyms

1
vote
1answer
45 views

Logic question- its about propositional logic and it asks for a valuation for statisfiability

I dont understand this question that comes from a past paper, so please any help is appreciated. The part that i dont understand is what does it mean (question 3) that it wants me to consider the ...
4
votes
2answers
107 views

Need Help to convert a grammar into Chomsky Form

I have to convert the following grammar into Chomsky Form $$( \Sigma=\{a,b,c,+\}, \Sigma_Q=\{S,V\},I=S)$$ $$S -> S+S|V$$ $$V -> a|b|c$$ My idea is the following: $$S_0 \rightarrow S$$ $$S ...
0
votes
2answers
56 views

110 people divided into 3 groups of different sizes

I need to distribute 110 people to 3 groups of different sizes as follows: 50 people to group 1 40 people to group 2 20 people to group 3 Instead of simply filling each group up to the desired size ...
1
vote
2answers
35 views

binary representation shrinkage question

Suppose for a given number $n$, every operation is to add $+$ signs arbitrarily into its binary representation. Repeat this process $K$ times. Prove: It is always possible to reduce the number to ...
0
votes
0answers
31 views

Online machine learning algorithm for dynamical system

I have a complex dynamical system which takes input as x1, x2, x3 and gives output as y1, y2, y3. I don't have any mathematical model of the system. x(k) is the present input to the system and y(k) is ...
2
votes
2answers
66 views

Height at 2D coordinate on a 3D rectangular surface

The Problem: How can I obtain every 3D coordinate on a rectangular surface given x and z? For those who are visual, picture looking down on the surface, and finding the height at where the x and z ...
2
votes
1answer
46 views

Why do we need “alphabets” defined?

I'm reading over my computational theory book before quarter starts and it's giving me the following definitions. alphabet: any nonempty finite set symbols: members of the alphabet I ...
1
vote
2answers
41 views

Best way to generalize a distribution of data into smaller subsets?

Suppose I had a data set as follows: 168.95, 176.83, 178.13, 179.61, 179.44, 172.83, 173.37, 174.06, 174.94, 175.43, 175.73, 175.5, 173.78, 174.06, 172.71, 174.3, 178.38, 178.43, 177.18, 175.34, ...
0
votes
1answer
41 views

Help with probability formula in programming problem

I am trying to solve this dynamic programming problem using probabilities. I know how the recurrence for it should look but I have problems using a probability formula. I have the next case: In a ...
4
votes
0answers
51 views

Minimizing the distance between points in two sets

Given two sets $A, B\subset \mathbb{N}^2$, each with finite cardinality, what's the most efficient algorithm to compute $\min_{u\in A, v\in B}d(u, v)$ where $d(u,v)$ is the (Euclidean) distance ...
3
votes
1answer
28 views

Mapping reduction to show NeverHalt is undecidable

I need help with showing that $NeverHalt_{TM} = \{\langle M\rangle|M\text{ is a TM which runs forever on every input $w$}\}$ is undecidable by giving an explicit mapping reduction. To show that a ...
0
votes
1answer
50 views

How to prove such program is uncomputable

We say that two programs are equivalent if they give the same output on every input. Prove that it is impossible to write a computer program that takes as input two pieces of code, code1 and code2, ...
1
vote
1answer
62 views

Does proving that a function is not in big O mean that the function is in big Omega?

If I determine that a function is not in Big O of another function, can you assume that the function is in big Omega of the same function?
1
vote
2answers
91 views

Choosing Codes or sequences with excellent Auto-Correlation properties

The Auto-Correlation function of Walsh-Hadamard codewords does not have a good characteristics. It can have more than one peak and thus, the Walsh-Hadamard codes do not have the best spreading ...
1
vote
1answer
30 views

Tight bound on the worst running time

I have to find a tight bound for an algorithm. I ended up with $3n^2 + 5$ as the worst running time of the piece of code. Is it ok if I consider $n^2$ as the tight bound? $$3n^2 + 5 \in ...
1
vote
2answers
133 views

Probability that $\frac{n}{2}$ bins are empty [close]

A Bloom filter of length $n$ was built. I have only the first $\frac{n}{2}$ bits of this filter. How will the false positive probability change? For the whole Bloom filter, the false positive ...
0
votes
1answer
92 views

Calculating normals for a polygon mesh (3D computer graphics)

I want to write a program to generate arches, a common architectural form, and export them to a wavefront object format for sharing with various three dimensional graphics editors. To do this, I need ...
0
votes
1answer
17 views

proving regular language

let $L$ be a language over the alphabet $\{a,b\}$ that maintains that for each $w \in L$ ,the difference in absolute between the number of apearences of the letter $a$ and the number of apearences ...
0
votes
1answer
55 views

Regular expression-language

I want to draw the DFA of the language that is given of the following expression, but I got stuck... Let the expression be {$(xy)^{*},(zx)^{+}$}$xz$ . Could you help me understanding which language it ...
7
votes
1answer
123 views

Is it possible that P != NP cannot be proved?

I am probably asking a stupid question but what I gather from a layman explanation of Godel's incompleteness theorem is that it is completely possible that a true statement cannot be derived from ...
0
votes
1answer
27 views

first order definability with $<$ vs $Succ, 0$.

In first order logic formulae with just the predicate $<$ could describe more structures than first order formulaes with $Succ$ (successor predicate) and a constant $0$ such that $\forall x (\neg ...
1
vote
0answers
55 views

Cut-off Subtraction in Coq

I am new to the world of computer assistant proof programs in general, and Coq in particular. As a result, I have sought to prove some elementary results about integers as a way to … At the moment, I ...
1
vote
1answer
74 views

Is there a DFA with $k+2$ states which its reverse has $2^k$ states

I am trying to figure out if there exists a DFA $M$ with $k+2$ states (for every $k\in \mathbb{N}$ ) so that every automaton which accepts $L(M)^R$ has at least $2^k$ states. I am trying to find an ...
3
votes
2answers
159 views

How to understand the definition of sets in homotopy type theory and the role of univalence?

Bear with me, I'm a physicist. In homotopy type theory, as I understand it, a type $X$ is a set if all the morphisms over its terms $x:X$ are identies. When I say "morphisms", then I view the term as ...
2
votes
1answer
38 views

Finding aggregate score from incomplete data

$$ \begin{align} n & = \text{number of reviews}\\ x & = \text{review score}\\ \bar{x} & = \text{aggregate score} \end{align} $$ I have a specified number of reviews for a product, I have ...
1
vote
1answer
41 views

Prove the existence of $C\in L_{regular}$ so that: $A \prec C \prec B $

Given $A,B$ regular languages. Prove the existence of $C\in L_{regular}$ so that: $A \prec C \prec B $ Whereas $A\prec B$ stands for: $A\subset B $ and $B\setminus A $ is infinite regular language. I ...
0
votes
1answer
32 views

Communication complexity example problem

Let $G = (V,E)$ and $H = (W,F)$ be two undirected graphs with $|V| = |W| = n$. G and H are isomorphic if there is a bijection f : V -> W such that: $\{u,v\} \in E$ <=> $\{f(u),f(v)\} \in F$ ...
2
votes
1answer
45 views

Proving that $L=\{w\in \Sigma^*: |w|_a= 2^n +273$, $n\in \mathbb{N} \}$ is irregular. [duplicate]

I am trying to prove that $L=\{w\in \Sigma^*: |w|_a= 2^n +273$, $n\in \mathbb{N} \}$ is irregular, whereas: $\Sigma=\{a,b\}$. I tried to use the pumping lemma with no success. I have also tried to ...
5
votes
2answers
187 views

NP-complete: One proof to rule them all

To prove a decision problem $C$ is in NP-complete, 2 things need to be shown: There is a polynomial verification for $C$ solution. Every problem in NP is reducible to $C$ - You can solve all the ...
1
vote
3answers
118 views

Context free grammar question

i have two context free grammar questions and I don't know how to do them. $$\{(a^n)b(c^n) \mid n >0 \}$$ I'm having trouble with this one because I don't know how to account for $a$ or $b$ not ...
1
vote
1answer
99 views

Time complexity of binary sum

What is the time complexity of binary sum, the sum of two binary numbers done like in elementary school? Say one number is F and his length is $s$ bits, and another number is H and his length is $t$. ...
2
votes
1answer
102 views

lambda calculus and category theory

I am not particularly knowledgeable in either lambda calculus or category theory, but I am starting to learn Haskell so I would like to ask: are there connections between category theory and lambda ...
0
votes
0answers
33 views

mathematical structure or algorithm for mapping a sinuous pattern ( a river)

I have a java application where I need to show a wooden log floating down a sinuous river. the problem is the river is in the shape of an S and for every frame i need to draw the wooden log. So I was ...
0
votes
1answer
309 views

Proving a tight bound on the worst case running time of an algorithm?

This exercise I don't understand what 'give a tight bound' implies here. The correct way to prove this is to consider that the runtime is in O and then use the definition of BIG O to prove that it ...
5
votes
1answer
125 views

Reference Request on Order Theory topics

I am looking for some references (especially a good recent book) that covers important topics involving partial orders such as: order polytopes, sorting/selection in partially ordered sets, upper and ...
2
votes
1answer
81 views

Turing Machine for comparing, copying, and operating

If one wants to design a Turing Machine for a function such as this: Where $x>0,y>0$ and are both integers represented in unary, so an example movement in this TM on the read-write head would ...
3
votes
1answer
57 views

Could every ultimately periodic word $\eta$ factored $\eta = pq^{\omega}$ such that $pq$ is primitive?

An infinite word $\eta$ is called ultimately periodic iff $\eta = pq^{\omega}$ for some $p, q \in X^*$. A word $w \in X^*$ is called primitive iff it is not a power of another word, i.e. it could not ...
1
vote
1answer
92 views

What is meaning of strict weak ordering in layman's term?

I gone through many pages using Google, but not understand exact meaning of Stick-weak Ordering term. I have this requirement while sorting strings. Thanks.
4
votes
1answer
164 views

Applications of Differential Geometry in Artificial Intelligence

I am new to this wonderful site. I searched around a bit but I couldn't find any well-discussed posts on applications of differential geometry to artificial intelligence, or more generally to computer ...
4
votes
0answers
128 views

Math or CS PhD areas to look at. [closed]

I am looking into getting back to school to get a PhD in Mathematics or Computer Science (I hold MA in Math). I am wondering what new areas of research in Math and CS are promising in a sense that ...
3
votes
1answer
74 views

Prove that Y is not context free.

2.42 Let $$Y = \{w\mid \text{$w=t_1\#t_2\#\cdots\#t_k$ for $k \ge 0$, each $t_i \in 1^*$, and $t_i \ne t_j$ whenever $i \ne j$}\}.$$ Here $\Sigma = \{1,\#\}$. Prove that $Y$ is not context free. ...
0
votes
1answer
17 views

How do I know that this is the density of the Chebyshev Points?

By knowing that a discrete distribution of points go asymptotically to the density: $\displaystyle p(x)= \frac{1}{\pi \sqrt{1-x²}}$ in $[-1, 1]$ I am able to conclude that interpolating at those ...
1
vote
1answer
54 views

Suppose $f_1 \in \Theta(g_1) \land f_2 \in \Theta(g_2)$. Prove $(f_1 + f_2) \in \Theta(\max\{g_1, g_2\})$.

I need to prove that $f_1 \in \Theta(g_1) \land f_2 \in \Theta(g_2) \implies (f_1 + f_2) \in \Theta(\max\{g_1, g_2\})$ This question is relevant, but I have a slightly different case, so I don't ...
1
vote
0answers
49 views

What exactly is 'computer mathematics'?

I'm looking at some potential things to study next semester and I see a full B.sc. degree called 'Computer mathematics'. It says it's a hybrid between computer-science and mathematics. Does anyone ...
0
votes
0answers
34 views

Inward-pointing normal and co-ordinate systems

I'm doing a course in computer graphics, and as such, we're being taught measures on how to deal with the Hidden Surface Removal problem. One of the topics covered was "back-face detection", that is, ...
0
votes
2answers
273 views

problem simplifying boolean algebra expression using consensus theorem

Please simplify this logic expression for me with helping boolean algebra : A'C'D + A'BD + BCD + ABC + ACD' I know that must use consensus theorem . my solve : STEP 1 : Terms 1 & 3 ...
1
vote
0answers
34 views

simplifying boolean algebra expression [duplicate]

A very urgent question : Please simplify this logic expression for me with helping boolean algebra : A'C'D + A'BD + BCD + ABC + ACD' I know that must use consensus theorem . my solve : STEP 1 : ...
3
votes
3answers
52 views

algorithm question how prove that $(n+a)^b = \Theta(n^b)$ [closed]

this question doctor in college give us as home work but I don't know how approve it
1
vote
1answer
635 views

Colored ball probablity

A triangular box contains five differently colored balls: red (R), green (G), blue (B), white (W), and yellow (Y). Define an appropriate sample space to study the outcome of an experiment where a ...
0
votes
0answers
28 views

What is the simplest form of the Boolean expression below? [duplicate]

I'm completely new to Boolean algebra, and I'm trying to simplify the expression below, using the distributive law, cancellation, negative absorption and De Morgan's theorem. I would start with the ...