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

0
votes
1answer
28 views

Homogeneous Arrays

I have this problem for homework and was wondering if anyone could help me out with it:
22
votes
5answers
4k 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 ...
0
votes
1answer
341 views

Bipartite Graphs and Trees Questions

Which of the claims below is not equivalent to the rest? 1) Every cycle in a graph "B" has an even length 2) Graph "B" is bipartite 3) Graph "B" has two components that are connected. 4) Graph "B" ...
0
votes
1answer
80 views

Checking Boolean Algebra work - Simplification

I am currently working on an assignment for a CE class I am taking, and I wanted to know if I have been simplifying these equations correctly. I'm supposed to reduce them to a sum of products. 1) ...
2
votes
3answers
68 views

Help making the distinction between polynomial and exponential time

I'm trying to understand how problems are categorized in these two classes. I have a specific problem I'm looking at, the directed path problem: PATH = $\{\langle G,s,t \rangle | G$ is a directed ...
3
votes
2answers
196 views

Are even numbers the sum of two odd sub-primes? / How to use computers to check?

Suppose $$p_{a} + p_{b} = 2{p_{1}}^{m_{1}}{p_{2}}^{m_{2}}...{p_{n}}^{m_{n}} \qquad \text{where }p_{x} \in \mathbb{P} -\left\{2\right\} $$ Then $$\frac{p_{a} + ...
0
votes
1answer
371 views

If the union of two languages is NP-complete, is one of them NP-complete?

Question 1) If $A\cup B$ is NP-complete, and $A$ is NP, and $B$ is P, then is $A$ NP-complete? I don't think so but I am unsure. When I try to reduce $A\cup B$ to $A$, I fail because strings in $B$ ...
1
vote
1answer
63 views

Showing a Problem Is Undecidable

How can I show that T is undecidable using only this information? $$T = \{\langle M, w, r\rangle \mid M \text{ accepts } w^r \text{ when it accepts } w.\}$$ So, what it's saying is that the machine ...
0
votes
1answer
67 views

Using the Pumping Lemma to prove a language is not regular.

I want to know if my proof is wrong and whether what I am doing works. $$\sigma = \{0, 1\}$$ $$A = \{0^n1^m \mid n < m\}$$ Claim: A is not regular. Proof: Assume A is regular. Let p be the ...
0
votes
1answer
179 views

Reduction from HALT on any string to HALT on empty string

The title says it all (if I have phrased it properly). How can we show that HALT on any string is undecidable using a decider for HALT on empty string? I think this is written: $$ HALT \leq ...
3
votes
1answer
141 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) \\ ...
2
votes
2answers
74 views

Prove the following by using mathematical induction

If we define the alphabet such that $$ \Sigma = {\{a,b}\} $$ and let $w$ be a string over it. I'd like to prove $$ ( \operatorname{comp}(w))^R = \operatorname{comp}(w^R) $$ where $$ w^R$$ and ...
0
votes
2answers
179 views

Discrete Math graph question?

How many edges would I need to add to $K_{n,m}$ to make it complete (instead of bipartite)? (n,m --> n+m) I know that $K_n$ has $\frac{n(n-1)}{2}$ edges and $K_{n,m}$ has $nm$ edges, but I can't ...
0
votes
1answer
54 views

Polytime implementation of Discrete Log using primitive recursive functions

The primitive recursive functions are defined by Godel as: $z() = 0$ $s(x) = x+1$ $\pi_i(x_1, \dots, x_k) = x_i$ Plus closure under Composition: $h(x_1, \dots, x_m) = f(g_1(x_1, \dots, x_m), ...
0
votes
1answer
307 views

I want to pursue Computer Science as a major but I don't know if i should…HELP!? [closed]

I'm currently a second semester sophomore who's currently pursuing a Global Affairs major and minoring in Japanese Studies. I plan on going to law school after college and I'm interested in ...
2
votes
1answer
137 views

Question on Proof that the Fibonacci Word is Sturmian

I am currently reading a text where it is proved that the infinite Fibonacci Word $u$ defined as the limit of the sequence $$ u_n = \varphi^n(0) $$ where the morphism is given by $\varphi(0) = 01, ...
0
votes
1answer
86 views

Recommendations of programming language / software for computer-assisted mathematics

I have always used R and Python for statistical analyses and object-oriented programming. Now, I have to perform relatively demanding (long to perform) mathematical analyses such as derivations and ...
0
votes
3answers
154 views

3D triangle computer graphics

We are given a 3D triangle with vertices $(0,0,0), (5,0,10), (0,20,0)$. What is the $z$ value of the point in the triangle with $x=3, y=1$? How do we find the $z$ value?
5
votes
2answers
870 views

“Opposite” of idempotent operation?

What is the adjective given to a mathematical operation/expression on a variable whose new value can only be described in terms of that variable's existing value? Sequential operation? Example: i = ...
2
votes
2answers
57 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 ...
1
vote
1answer
76 views

Subscript before a function symbol?

Does anyone know what the subscript before the function means? $$ _pf_p $$ It's part of a definition for selfish routing in networks: Let $N = (V,E)$ be the network, which is a directed graph. ...
1
vote
0answers
18 views

Encoder based on large similar data

Let us say you (Alice) and another agent (Bob) share a large piece of data (say, the Gutenberg project collection of books, or the Linux kernel. You want to send a smaller but still large piece of ...
0
votes
1answer
37 views

Range of number systems [closed]

I don't understand how to get the fraction part. This is what I came up with for the integer part. A) For 12 bit unsigned = 0 to 4095 B) For 12 bit signed = -2048 to 2047 C) For 12 bit in 2's ...
5
votes
3answers
2k 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
1answer
167 views

Graph Coloring Question

Given T(n) as a star graph with n edges. (Basically T(n) is a graph that has one vertex u in the center, and from u there is one edge to each vertex v1,...,vn.) It is easily know that star-graphs are ...
1
vote
0answers
72 views

Computationnal geometry: vector, basis, point and coordinate system?

I am trying to build a small geometrical library in C++, that is mathematically consistent (not so false). The goal here is to construct two concepts: vectors and points. I am not sure that the ...
1
vote
1answer
243 views

Engineering notation algorithm, i.e. 1000 -> 1k, 0.001 -> 1m

I had to come up with a simple algorithm on a low powered embedded system, because dividing numbers by 1000s to get the wanted digits (first three basically) caused a loss in precision in the floating ...
1
vote
1answer
110 views

Show that the Turing machine will solve the self-halting problem

Suppose we have Turing machine $M^*$ that: i. halts printing 1 if $M_n$ halts on input 1 ii. halts printing 0 if $M_n$ doesn't halt on input 1 Show that you cannot construct $M^*$. ...
2
votes
0answers
169 views

A* vs D* vs Dijkstra [closed]

I understand the basis of A* as being a derivative of Dijkstra, however, I recently found out about D*. From wikipedia, I can understand the algorithm. What I do not understand is why I would use D* ...
1
vote
1answer
56 views

Proof that such a Turing machine cannot be constructed…

Prove there can be no Turing machine $M^*$ that takes input $n$ and: i. halts printing 1 if $M_n$ halts on input 1 ii. halts printing 0 if $M_n$ doesn't halt on input 1 Intuitively I can see why ...
2
votes
3answers
223 views

Exponential Regression: how to get a formula from a given pattern

I'm trying to code a computer script (in Java) that returns an array of numbers that follows a certain pattern. The numbers should be: ...
5
votes
0answers
103 views

This proof in my textbook involving the pumping lemma appears incorrect - is it?

It states Let $B$ be the language $\{0^n1^n2^n | n \geq 0\}$. We use the pumping lemma to prove that $B$ is not regular. The proof is by contradiction. Assume to the contrary that $B$ is regular. ...
0
votes
1answer
72 views

Proving Upper Bound for Two Variable Function?

The question is: Prove (logn)^k = O(n) for every k>=1. I have never encounter a problem for proving an upper bound for two variables, so I am perplexed as to ...
0
votes
1answer
76 views

How to get 2 percentages to a 100%

First of im new to this site and I've never been the sharpest at math, im a web developer by trade. My question is math related but ill just give you a quick background about my website so that you ...
0
votes
2answers
478 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 ...
0
votes
2answers
168 views

Existing Algorithm / Code to calculate exact values of the Riemann Zeta function at even natural numbers?

I wanted to know if there's any existing algorithm to compute exact values of the Riemann Zeta function at even natural numbers? For example, it should compute $\zeta(4)$ as exactly $\frac{\pi^4}{90}$ ...
2
votes
1answer
104 views

Iteratively Replacing Substrings

This problem came up while I was helping someone. Informally, we have a string of characters and a "rule" which replaces a specific string with another one, and we repeat this rule until we can no ...
-1
votes
1answer
108 views

Graph Theory - Introduction Questions [closed]

I have a couple of questions that are probably SUPER easy for anybody that has studied graph theory but are confusing the hell out of me. I know it may be inconvenient to help me but I have a test ...
3
votes
3answers
95 views

Is $L = \{(x,y,z) | x+y=z\}$ a regular language?

Suppose $x,y,z$ are coded as decimal or their binary representations in an appropriate DFA. Is $L$ regular? My intuition tells me that the answer is no, because there are infinitely many combinations ...
0
votes
2answers
571 views

Tough Turing machine multiple choice questions

I'm having a tough time deciding whether my answers for these questions are correct. Can anyone help me agree on something? They seem pretty easy, but I've found that they're actually difficult. ...
1
vote
1answer
67 views

Echo State Network learning Mackey-Glass function, but how?

I got this example of a minimal Echo State Network (ESN) which I analyse while trying to understand Echo State Networks. Unfortunately I have some problems understanding why this really works. It all ...
4
votes
1answer
34 views

Is anything nontrivial known about quotients of complexity classes?

This question is just for fun and this is completely outside my area, so it's likely dumb; apologies in advance. By a "quotient" I mean the following: suppose you have two complexity classes, $A ...
0
votes
1answer
95 views

Easy Proofs with Functions and Big-O

I have these two questions. I tried answering them, but got them wrong and I don't know how to answer them correctly. This is not homework --- I'd appreciate a solution (at least to one), and an ...
-1
votes
1answer
211 views

Is there a general formula to represent the cardinality of a Cartesian product of n sets?

For two sets, basically, $|A \times B|=|A| \times |B|$.. Suppose I'm given a random number of sets. Which formula should I use? Or is there a specific method? Using a program It's easy to ...
1
vote
2answers
109 views

Which pure mathematical problems could be tackled with an algorithm solving NP-complete problems?

In the past, practical applications have motivated the development of mathematical theories, which then became the subject of study in pure mathematics, where mathematics is developed primarily for ...
1
vote
1answer
252 views

Knuth-Bendix completion algorithm: word problem

Can someone explain me how to set up an algorithm to find the 12 normal forms of the group $A_4$ by making use of the Knuth-Bendix completion algorithm? So we have that $RRR=1, SSS=1$ and $RSRS=1$. ...
0
votes
1answer
320 views

Data Representation Question

A computer stores a number of $16$ bits word using floating-point arrangement. Given that the first bit is reserved for the sign and followed by $6$ bits for the exponent using biased form. The ...
3
votes
1answer
338 views

No of pairs of elements whose XOR satisfies a condition

We are given a set of $n$ non-negative integers. We need to find the number of pairs of integers from this set whose $XOR$ is $ = K$. My approach is to sort the integers which takes $O(NlogN)$. Then ...
4
votes
1answer
126 views

Recursively deleting every second element in a list

This question got me thinking. If you have a list of length n and recursively delete every other element from the list until only one element remains, is there any ...
2
votes
1answer
231 views

Texture mapping from a camera image (knowing the camera pose)

I'm not sure if I should ask this question here or on stackoverflow, so forgive me if I'm wrong. I want to apply a texture (taken from a camera) on a 3D surface, let me explain my problem: I have ...