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

0
votes
0answers
9 views

The approximation rule implies the equality rule in systems of type assignments

I'm reading Barendregt's Lambda calculi with types (1992). In Proposition 4.1.4.1., he "proves" a lemma which shows the approximation rule implies the equality rule in typed lambda-calculi à la ...
1
vote
2answers
24 views

Which discrete mathematics book to read for a software engineer?

I'm a computer science student, but I lack a good mathematics background. So I decided to start working on that. I was searching in the topic and I found that for computer science a good knowledge of ...
0
votes
0answers
7 views

Computing Object Classification with bayesian statistics

Say I want to know if there is a zebra $\theta$, in an image $x$. According to Bayes statistics applies to image recognition, I should be computing: ...
1
vote
0answers
17 views

Why we take transpose of Vector (Displacement Vector)?

I'm trying to understand some equations that involves transpose of vectors (displacement vectors to be precise) Two set of vectors F and G (with i,j) that corresponds to X,Y value in plane and ...
-2
votes
1answer
21 views

Which is a linear and homogeneous recurrence?

Which of the following choices is a linear and homogenous recurrence? $1)$ $A_n = A_{n-1} + 4A_{n-2} + 3n$ $2)$ $A_n = n + 1$ $3)$ $A_n = (A_{n-1})^2$ $4)$ $A_n = 5A_{n-1} + A_{n-2} + 3A_{n-3}$
1
vote
0answers
14 views

What about generlizing grammars?

Say we came up with a finite grammar (specifies a finite number of strings) given a set of input strings. How then do we generalize the grammar so that it works for larger input strings and also ...
0
votes
1answer
80 views

Find all subsets whose sum modulo a value is 0.

How can we find the count of number of subsets of a given set (e.g. {1,7,4,90,23} ) whose sum is a multiple of a given value A. One method which I know of is to store all subset sums modulo A and ...
0
votes
1answer
12 views

(Linear regression and data points) Does anyone have links to good tutorials, or advice? [on hold]

I have gathered several sets of 1500 data points. I am trying to import the data and run a simple linear regression model on the points. I have found very vague tutorials to teach me how to do this. I ...
0
votes
1answer
20 views

uniqueness of Maximal Independent Set(MIS)

Is maximal independent set of a graph unique? I think between indepent sets, only one of them is maximal. So does it prove that MIS is unique?
1
vote
1answer
21 views

Proving this tree definition with pigeonhole principle

I am studying the following tree definition: Let $T$ be a finite set and a function: $p: T \mathbin{\backslash} \{r\} \rightarrow T$. Then, $(T,p)$ is a tree if and only if, for all $x \in T, p^k(x) ...
0
votes
1answer
27 views

Java Shift Equation Simplification [closed]

I have a java program that converts a color image to a grayscale image and to change the rgb values to a value that the computer can understand I do the equation bellow but how can I simplify it and ...
1
vote
1answer
620 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
45 views

How to simplify following equation?

Here is the equtation: $$\mathrm{P} = \prod_{1\le i \le n}(a_i+1)^2+\left(\sum_{1\le i \le n}a_i\right)\prod_{1\le i \le n}(a_i+1)+\sum_{1\le i \le n}a_i^2-1$$ It is hard to compute each $a_i$, but I ...
13
votes
1answer
230 views

Mathematics of Torrenting

It is more or less common knowledge that a bittorrent network has the potential to be much faster than direct downloads, but I have never seen any real math describing why, or any theoretical bounds ...
0
votes
0answers
36 views

Existence of a det. poly-time algo for problem $f: X \to Y$.

$f : X \to Y$ is a deterministic polynomial-time algorithm for problem inputs $x \in X$ and problem outputs $f(x) = y \in Y \iff $there exists a polynomial $P_f \in \Bbb{Z}[x_1]$ such that $C\cdot ...
2
votes
0answers
24 views

How do you find a minimum of a function with these tools?

Let's say I can define a group $G$ acting on a set of combinatorial objects $X$ and I have a function $f: X \to \Bbb{N}$ that I want to find a minimum of in $X$. Is there a polynomial time ...
2
votes
1answer
31 views

How to convert a Turing Machine program to a tiling using Wang Tiles?

To illustrate my question I provide the following example. The website Online Turing Machine provides a Turing Machine simulator. The following program adds 1 to any binary number. q0,1 q0,1,> ...
0
votes
0answers
24 views

Convert nested for loop to mathematical expression

Does anyone know how I can convert this nested for loop into a mathematical expression? ...
0
votes
2answers
40 views

Recurrence Relationship Questions

Consider the recurrence defined by: $$G_0 = 0\\ G_n = G_{n-1} + 2n - 1$$ Determine what Gn is for several values of n to determine a formula for Gn. $2n$ $n$ $2n-1$ $n^2$ *I believe this one is ...
1
vote
1answer
37 views

Simple Recurrence Questions [closed]

$r$ is a real number, define a recurrence relationship for $A_n$ $$A_0 = 1\\ A_n = r\cdot A_{n-1}$$ Question: What is the value of $A_4$ $4(A{n-1})$ $r^4$ $1$ $4r$ I've pretty much eliminated ...
10
votes
3answers
152 views

is there an efficient algorithm for comparing collections of points?

Let's say you have two sets of M points $p_1...p_M$, and $q_1...q_M$, which reside in $\mathbb{R}^N$. Is there an efficient (e.g. polynomial in M and N) algorithm to determine if the point-sets are ...
0
votes
1answer
22 views

create a new formula

I should write a new computer program which includes this computation which I am having trouble with. I may have several cases, ...
0
votes
0answers
10 views

Hierarchy of hardness for the pumping lemma for regular languages.

Whenever I bring up the Pumping lemma for regular languages people often say `better to use the Myhill-Nerode theorem'. I want to make this thought rigorous. Def: A language $L$ is pumpable if there ...
5
votes
3answers
372 views

Finite Automaton that accepts only the words baa,ab, abb and no other strings longer or shorter

I am trying to understand the answer here for FA that accepts only the words baa, ab, abb and ...
0
votes
0answers
39 views

Todd-Coxeter algorithm: coincidences

I'm trying to understand the Todd-Coxeter algorithm with the help of a multiplication and relator table, but there is one thing about coincidences that is not really clear. For some small groups (for ...
1
vote
4answers
691 views

Convert from base 10 to base 5

I am having a problem converting 727(base 10) to base 5. What is the algorithm to do it? I am getting the same number when doing so: $7*10^2 + 2*10^1+7*10^0 = 727$, nothing changes. Help me figure it ...
1
vote
3answers
30 views

Base 16 to base 10 number conversion

I know that if we want to convert from base 16 to base 10 we do as follows (for example): Given : $15C$ in base $16$ Conversion to base 10: $12 \times 16^0 + 5 \times 16^1 + 1 \times 16^2 = 348$ in ...
0
votes
0answers
19 views

Application of Combinatorics, Logic and computability theory in physical science: Tiling of Wang Tile with proportionality

The original problem of Domino Tiling and Wang Tile has great theoretical interest on computability theory... However, the great emerging problem on application of Wang Tile in material science and ...
0
votes
1answer
21 views

using pumping lemma to prove that a set is not regular

A={s11s|s $\epsilon$ {0}^*} so the strings 00011000 and 000001100000 are accepted of A but not 00100 or 001100000. Demon chooses k. ...
0
votes
2answers
25 views

What can be observed by evaluating a polynomial at roots of order greater than the polynomial itself?

I have been reading through an algorithms book on the use of FFT for large number multiplication. An example it used to emphasize a point was: Evaluate the following polynomial at all roots of unity ...
-1
votes
0answers
40 views

Computer Based Mathematics

I made a post several days ago about the use of computers - and computer programming specifically - in learning mathematics. I have subsequently discovered this project/website by Conrad Wolfram, the ...
1
vote
4answers
49 views

Examples of partial functions in which the domain is not known?

I was reading this, it mentions about a kind of function in which the exact domain is not known. The only example given is this one - and I'm not really sure I understood it. I got curious about it: ...
0
votes
0answers
12 views

It would be possible to use the covariance matrix $C'=XX^T$ instead of the standard $C=X^TX$ to get the same result on PCA?

It would be possible to use the covariance matrix $C'=XX^T$ instead of the standard $C=X^TX$ to get the same result on PCA? If so, what are the next steps to retrieve the data with reduced ...
0
votes
0answers
23 views

Create a Truth Table that reflects the following scenario?? HELP [closed]

Create a truth table to the following scenario. Using appropriate labeled inputs and outputs, identify which Boolean operator is being used in the truth table. It's very difficult to make your cat ...
1
vote
1answer
28 views

Are there differences between total functions, epimorphic functions and surjective functions?

I've read three definitions which seems to point to the same idea. I've read about epimorphic functions in Mazzola's Comprehensive Mathematics for Computer Scientists - in this book, he treats it as ...
8
votes
3answers
2k views

fast algorithm for solving system of linear equations

I have a system of linear equations, $Ax=b$, with $N$ equations and $N$ unknowns ($N$ large) If I am interested in the solution for only one of the unknowns, what are the best approaches? for ...
-1
votes
0answers
15 views

copying a file from linux to windows using PSCP [closed]

I have just started using linux so I am very unfamiliar with commands etc. I have created a .tar file in my directory and I would like to get this .tar file copied to windows so I can attach it to an ...
3
votes
1answer
94 views

How to solve this system of 3 equations with 3 variables?

I stumbled upon this system with constants $a_{i,j}>0$ that I want to solve for $x,y,z \in\mathbb{R}$: \begin{align} a_{2,1}y+a_{3,1}z=& x(y+z) \\ a_{1,2}x+a_{3,2}z=& y(x+z) \\ ...
0
votes
0answers
13 views

(L1* ∩ L2*) = (L1 ∩ L2)* for all languages L1 and L2 over the alpabet Σ={A,B} Is it true or false and why?

plz answer me Determine whether each of the following statements is true or false. If a statement is false, give a counterexample..... 1- $(L_{1}^{*} \cap L_{2}^{*}) = (L_{1} \cap L_{2})^{*}$ for ...
1
vote
1answer
16 views

Is this function (Strings and Languages) True or false, and why? plz help me

plz answer this two question if u know an give me the reason Determine whether each of the following statements is true or false. If a statement is false, give a counterexample. 1- uv=vu for all ...
2
votes
2answers
27 views

Moving segments colliding

I need to check if the edges of two triangles will collide. I do an edge-edge check for each pair. One segment is stationary, while the other moves with constant velocity. The segments are not ...
0
votes
1answer
22 views

How to prove not a CFL with pumping lemma?

need to prove using the pumping lemma that $L=\{a^{2N} b^{N} c^M d^N| M,N>=0\}$ is not Context-Free. This is what I have so far: Suppose that L is a CFL. Let p be the pumping length. Choose ...
3
votes
3answers
750 views

How to compute the transition function in non-determinism finite accepter NFA?

I'm currently teaching myself Automaton using Peter Linz book - An Introduction to Formal Languages and Automata 4th edition. While reading chapter 2 about NFA, I was stuck this example (page 51): ...
0
votes
2answers
26 views

How to compute surface normal pointing out of the object

An object has been approximated by a lot of triangles. Given the vertex positions of these triangles, how can I compute the normal of these vertices which pointing outside of the object. I know the ...
20
votes
5answers
3k views

Is a brute force method considered a proof?

Say we have some finite set, and some theory about a set, say "All elements of the finite set $X$ satisfy condition $Y$". If we let a computer check every single member of $X$ and conclude that the ...
1
vote
1answer
21 views

texture mapping from a camera image to a 3D surface acquired by a kinect

I have the following problem: A kinect camera capture a 3D surface and save it as a .obj files containing all the positions of the vertices (in the kinect coordinate system). If I take a picture ...
0
votes
1answer
58 views

efficient algorithm to place people in a specific order

You are preparing a banquet where the guests are government officials from many different countries. In order to avoid unnecessary troubles, you are asked to check the list of international conflicts in ...
1
vote
4answers
138 views

Prove this language is not regular [closed]

How do I prove that this language = {1^k | k is a perfect square} is not regular by showing that no DFA can accept the language?
0
votes
1answer
30 views

How to convert this NFA to DFA?

http://www.cs.odu.edu/~toida/nerzic/390teched/regular/fa/figures/nfa-dfa1.jpg What are the steps for convert this NFA to DFA??
0
votes
1answer
13 views

how to come up with a solution of finite or infinite language using context free grammer?

I am trying to come up with a solution of finite or infinite language using context free grammer. I have these grammers to find if it's a solution of finite or infinite language ...