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
1answer
23 views

Alphabet on homomorphism

So I am trying to learn for an exam, and I found an exercise but without solutions and I can't really get behind the topic: Let $G = (V,E)$ be a connected graph with $v \geq 2$ Vertices. $P(G)$ is ...
0
votes
0answers
19 views

3d pattern matching for object recognition? [on hold]

How do i measure the similarities between two set of 3d points made by group of points in 3d? Is their any mathematical equation? In keypoint detection i get set of keypoints from 3d point cloud, now ...
2
votes
2answers
36 views

Fast Rational Bézier Surface Evaluation Problem

I am currently writing a NURBS ray tracer. What I do is convert the NURBS into rational Bézier patches and then perform the intersection test using Newton's method. To do this fast (the ray tracer ...
2
votes
2answers
36 views

How to evaluate this infinite series arising from a CS problem? [duplicate]

$$\sum_{i=1}^{\infty}i\cdot((1-\frac{1}{N!})^{i-1}\cdot\frac{1}{N!})$$ where N is an integer and $N \geq 2$? I obtained this series from the following problem: Given a sequence of $N > 2$ unique ...
1
vote
2answers
17 views

Growth function and one misunderstanding point?!

I have a question about Growth and Asymptotic notation topic. My question is as follows: $2^n$ > $n^{log_2{(n)}}$ is True. anyone could say how we can deduce that this fact is true?
3
votes
4answers
70 views

Does this thing I'm calling 'the operationalization of $x$' have an accepted name?

Given a set $X$ and an element $x \in X$, we can turn $x$ into a function denoted $\tilde{x}$ as follows: for any set $Y$ and any function $f : X \rightarrow Y$, define $$\tilde{x}(f) = f(x).$$ For ...
1
vote
1answer
85 views

Contradiction in Davis–Putnam–Logemann–Loveland (DPLL) Method?!

As we see on page $10,11$ and $12$ on Google Books we know about Unit Clause (UC) and Pure Literal (PL) in DPLL Algorithms. in the following example if assign value $0$ to variables is prior to ...
2
votes
3answers
2k views

An algorithm to convert float number to binary representation

I want to know the algorithm of converting a given float (e.g, 3.14) to binary in the memory. I read this wikipedia page, but it only mentions about the conversion the other way. Let me quickly give ...
0
votes
1answer
23 views

Big O notation for summation function

May be I am missing something very simple but I am finding it hard to understand why Big O for summation is O(n^2). I know that Big O for summation comes from fact that sum(1 to n) = n(n+1)/2. But if ...
0
votes
0answers
21 views

Explaining something in Kraft-McMilan inequality proof

I was asked to present the Kraft-McMillan inequality, but I have trouble in understanding why in the following segment of the proof: there is a $$k\ge0 $$such that: $$ a^{-l_1}+a^{-l_2}+.....+(k+1)a^{...
1
vote
1answer
40 views

pumping lemma - choice of partition

there is some thing in pumping lemma that I don't understand it. I think about application to prove irregularity of language. We have for each word (actual length) find partition: $xyz$ such that $\...
0
votes
1answer
36 views
+50

A question about many-one reducibility of two sets

We want to show that $ \big\{x:W_{x}$ is finite }$=Fin \leq _m Cof=\big\{x : W_{x}$ is cofinite}. But I really have not any idea. Would be grateful for your help.
0
votes
1answer
17 views

Is there any approach to computer vision that doesn't make use of geometry?

I've long been interested in applying my background in functional analysis (especially wavelets) and other related areas to actually create something with "real world" value (not that I don't enjoy ...
0
votes
1answer
22 views

is this k-SAT or 3-SAT reduction?

On introduction to the theory of computation - 2nd edition by Michael Sipser, there's this question with the solution: Question: "7.31: In the following solitaire game, you are given an m x m board. ...
0
votes
0answers
20 views

Henkin theory follow complete

Assume that Γ is a a Henkin theory. For any two constants c,d, either $\Gamma \vdash c=d$ or $\Gamma \vdash c \neq d$. There are two constants a,b such that $\Gamma \vdash a\neq b$.Show that Γ is a ...
0
votes
1answer
74 views

What is the maximum number of reduce moves that can be taken by a bottom-up parser for a grammar with no epsilon and unit-production

What is the maximum number of reduce moves that can be taken by a bottom-up parser for a grammar with no epsilon and unit-production (i.e., of type $A \rightarrow \epsilon$ and $A \rightarrow a$) to ...
-5
votes
1answer
217 views

Let $G$ be finite group. if $A,B\le G$ with orders $4, 5$ respectively then $A \cap B$? [closed]

Let $G$ be finite group. If $A$ and $B$ are subgroups of $G$ with orders 4 and 5 respectively, what is $A \cap B$ ?
0
votes
1answer
24 views

Which one of the following is true of this relation?

Consider the set of A all the people who are living down Italy."x lives in the same house as y" is a relation on the set A.Consider the following properties of a relation on a set: a)Symmetric b)...
0
votes
0answers
9 views

Change In Time from Bidirectional Turing Machine to Standard Turing Machine

I'm reading this book on Computational Complexity and on page 37, it has a proof that a bidirectional TM $M$ running in $T(n)$ time can be converted to a unidirectional TM $\widetilde M$ running $4T(n)...
1
vote
1answer
28 views

Proving that $A+B - (A \cap B) = A \cup B$ for binary integers

I hope computing questions are fine here. I'm trying to show that for all binary numbers $A$ and $B$, $A+B - (A \cap B) = A \cup B$. It's confusing me firstly because I'm not sure what the "set ...
1
vote
2answers
164 views

Sequences of a computable function

Is there any computable function $f(n)$, which given any integer $n$ has been proven to return either $0$ or $1$ in finite time, and for which the statement "$f(1), f(2), f(3),\ldots$ contains ...
0
votes
1answer
13 views

How can I show a set B with 8 elements and two operations (huntington axioms)

How can I show a set B with 8 elements and two operations, such that the axioms of huntington for boolean algebra holds? I found it with set of 2 elemtnts. but can't understand how to start with 8 ...
-1
votes
0answers
33 views

i dont understand how theorem calculation proofs work please help [closed]

I do not understand hilbert style proofs and how they work. Can someone please explain them to me? some things i need to know are: • Write theorem-calculations from Γ (equivalently, Γ−...
0
votes
1answer
37 views

Help in proving inequalities in information theory-Kraft-McMillan

I was given a task of proving some inequalities that are related to Kraft-McMillan's inequalities, and i have been scratching my head for quite some time trying to prove it: $$ F(x)= \frac{1}{1-Q(x) }...
0
votes
1answer
87 views

Trying to prove Equivalency using Boolean Algebra

The question presented was to use boolean algebra to show that XY’Z + X’Y’Z’ + XY’Z’ + X’YZ’ ≡ XYZ’ + XY’Z + XY’Z’ + XYZ’ I've tried using various laws of Boolean algebra, but the answer that I ...
0
votes
1answer
34 views

comparing two strings with Turing Machine

Reading about Multitape Turing Machines and coming across this exercise: Construct a Turing Machine, that can "tell" if a word w1 on strip 1 matches w2 on strip 2. Given approach : Compare the states ...
0
votes
1answer
713 views

Y-Axis units on FFT graph

A 50Hz sinusoid wave with a voltage range of +/-20V is sampled at 512Hz for 1 second. No bias or phase shift are present. The signal is run through an FFT. The result is one spike at 50Hz on the ...
0
votes
0answers
18 views

Defining the right number of columns for a website interface

While working on a website interface (I'm a web developer), I came across an interesting problem. 1/ SOME DEFINITIONS In web design, for maintaining a coherent flow of the different elements of the ...
1
vote
1answer
24 views

Floating point numbers

In a certain computer represents numbers in base2, if the distance between 7 and the next largest floating-point number is $2^{-12}$. What is the distance between 70 and the next largest floating ...
0
votes
0answers
16 views

Primitive recursive function, constructing a proof

I've came upon an example in the book that is not that clear to me. The disparity function is proved to be primitive recursive in the following way: $$disparity(x_0,x_1)=(x_0-x_1)-(x_1-x_0) = add(...
0
votes
1answer
636 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
0answers
29 views

Negative representation of a binary number

I saw online that if you want to convert a binary number to a negative binary number, you add 1.However, I don't understand why you do that.In a forum I saw someone explaining the following: ...
0
votes
0answers
31 views

How to show that a function is primitive recursive?

If we have a function $g ~:~ \mathbb{N}^{k+1} \rightarrow \mathbb{N}$ which is primitive-recursive. How to show that the function $f ~:~ \mathbb{N}^{k+1} \rightarrow \mathbb{N} $ with $f(x_1, ~...~, ...
1
vote
1answer
954 views

How to construct a context free grammar that generate following language. $\{a^nb^nc^k \in \{a,b,c\}^* | n,k >= 0\} $

$$\{a^nb^nc^k \in \{a,b,c\}^* | n,k >= 0\} $$ $E \to aEbS $ $S \to c$ I do not know where to go next, or even if this is right at all?
11
votes
4answers
1k views

How many bit strings of length 8 start with “1” or end with “01”?

A bit string is a finite sequence of the numbers $0$ and $1$. Suppose we have a bit string of length $8$ that starts with a $1$ or ends with an $01$, how many total possible bit strings do we have? I ...
1
vote
1answer
448 views

Solving recurrence relation: $ f(n) = 3f(n/2) - 2f(n/4) | f(2) = 5, f(1) = 3$

$f(n) = 3f(n/2) - 2f(n/4) | f(2) = 5, f(1) = 3$ I have attempted to solve it by letting $n = 2^k$ $f(2^k) = 3f(2^{k-1}) - 2f(2^{k-2})$ Then set $S(k) = f(2^k)$ $S(k) = 3*S(k-...
0
votes
1answer
18 views

the set of extendable p.c. functions is not N

Show that the set $Ext:= \big\{x\in N : \varphi_{x}$ is extendable to a total recursive function $\big\}$ is not equal to the set of non negative integers $N$. Would be grateful for your help.
0
votes
2answers
66 views

Turing Machine halts for at least $1024$ strings as input [closed]

Consider the language $$L = \{\text{"}M\text{"} \mid \text{Turing Machine } M \text{ halts for at least }1024\text{ input-strings}\}.$$ Is L a recursively enumerable language? My answer is no based ...
0
votes
1answer
32 views

Why This alternative way for retrieving the Original number from 2'S complement number works?

I was reading a book to learn about conversion from 2'S complement number to origianl binary number. During my past college study, I learened the following method for retrieving the Original number ...
0
votes
1answer
54 views

Turing Machine & Recursively enumerable languages. [closed]

Suppose Turing Machine(TM) M and language L. L = { "M" | M has as input strings which $∈$ $\{0,1\}^{*}$ and terminate at a maximum of $512^{512}$ steps} Is L a recursively enumerable language?
-1
votes
1answer
47 views

Iterate through integers solutions of linear inqualities [closed]

Say we have a set of integers value $x_1,\ldots x_n$ such that $$ \left\{ \begin{array}{l} a_{1,1} x_1 + \ldots a_{1,n}x_n \leq b_1 \\ \vdots \\ a_{m,1} x_1 + \ldots a_{m,n} x_n \leq b_m \\ x_1, \...
1
vote
2answers
40 views

Why can't this be a Regular Language?

Given $L$ - the language consisting of all the strings of the form $\{0^n 1 ^m\}$ where $m < n$. How can I prove that $L$ is not a regular language?
3
votes
1answer
48 views

Identify inherently ambiguous languages

Which of the following languages is/are inherently ambiguous languages? $L_1=\{a^nb^nc^m|m,n\geq0\}\cup\{a^nc^c|n\geq0\}$ $L_2=\{a^nb^nc^m|m,n\geq0\}\cup\{c^mb^na^n|m,n\geq0\}$ My attempt: A ...
2
votes
1answer
52 views

Hamiltonian circuit in at least one component

I'm having trouble proving that the problem stated in the title is NP-complete, specifically by reduction from Hamiltonian circuit. Intuitively it's clear - Hamiltonian circuit in one graph is NP-...
1
vote
0answers
42 views

Discretizations of Differential, Geometric and Topological Notions

I have noticed a recurring theme in Graph Theory / Theoretical Computer Science (abbreviated GT and TCS throughout this post) in that notions typically belonging to differential calculus / geometry / ...
3
votes
2answers
223 views
0
votes
0answers
15 views

Prove that reverse of regular L is also regular [duplicate]

Prove that reverse of regular language is also regular. I know, how i can to this by using DFA of L. Changing directions of edges and so on. But how can it be done with Structural induction? What ...
0
votes
2answers
2k 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
votes
1answer
42 views

Time complexity (in Θ –notation) in terms of n [closed]

I am struggling quite a bit trying to solve these and any help would be greatly appreciated. a) ...
2
votes
1answer
2k views

Induction Proof Check: For a binary tree T, Prove that the number of full nodes in T is always one less than the number of leaves in T.

This is a slight variant on a very common beginner's problem. I think I've got it figured out, but I wanted to make sure I actually proved what's being asked. We define a binary tree $T$: (a) A tree ...