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

Planar and Euler's Formula Question

If a connected planar graph has four regions and six vertices, how many edges will the graph have? (I believe the answer is 8 but I'm not positive) 1) 9 2) 8 3) 6 4) 7 Graph A = ({a,b,c,d,e,f,g}, ...
0
votes
1answer
19 views

Homogeneous Arrays

I have this problem for homework and was wondering if anyone could help me out with it:
21
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 ...
0
votes
0answers
13 views

What are the current lower bounds for $NTIME$ vs $DTIME$?

Trivially, we have $DTIME(f(n)) \subset NTIME(f(n))$. Is it known whether or not this inclusion is strict? Do we know if $DTIME(f^c(n)) \subset NTIME(f(n))$ for any $c$? Is there any $c$ for which ...
0
votes
1answer
94 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
0answers
27 views

Given a N*M matrix determine the number of pairs that exist in a GLCM

This is an interesting problem for which I can't find a direct solution. Given a n*m matrix (in this case 5*5): 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 There exist a certain number of ...
0
votes
1answer
59 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
44 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
154 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
88 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
33 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
0answers
34 views

An independent set of vertices $\times$ the chromatic number $\ge$ the number of vertices

$A$ is a graph. By definition an independent set $S$ is a group of vertices (could be 0 vertices, or could be all vertices) of $A$ where there are no two vertices from $S$ that are adjacent in graph ...
0
votes
1answer
55 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
66 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
112 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) \\ ...
1
vote
0answers
56 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
45 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
41 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
63 views

Confusing Notations in a Paper

From : "Multicast Routing and Design of Sparse Connectors" by Andreas Baltz and Anand Srivastav, Springer 2009: http:\\link.springer.com/chapter/10.1007%2F978-3-642-02094-0_12 In 2-Copy Method, ...
0
votes
1answer
121 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 ...
1
vote
1answer
47 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
55 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
57 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?
3
votes
1answer
182 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
36 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
0answers
10 views

parallelizing $k$-means

I'm having trouble thinking about the following. If we have two machines 1 and 2 that evenly split a set of data points, does $k$-means separately, then averages the result, does this agree with just ...
0
votes
0answers
41 views

What is the result of the calculation: $8.375 - 0.375-0.875$?

Given the base $\beta=2$ (binary) and $t=4$ digits to represent the number in computer with hidden bit representation and symmetric rounding, what is the result of the calculation in floating point ...
1
vote
1answer
57 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. ...
0
votes
1answer
33 views

Natural Decision Problem not in PTIME

Are there any natural decision problems which are guaranteed not to be in $\mathsf{PTIME}$? Preferably natural graph problems like $\mathsf{CLIQUE}, \mathsf{VERTEXCOVER}$ etc. (However, they would be ...
1
vote
0answers
14 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
28 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
588 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
88 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
46 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
63 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
57 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
48 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
35 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 ...
0
votes
0answers
17 views

Reduction of halting problem

I can show that this reduction !H ≤ H where H is the general halting problem an !H is the complement of it. But what with H ≤ !H ...
2
votes
3answers
112 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: ...
2
votes
0answers
52 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
34 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
61 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
60 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
87 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
0answers
41 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 ...
0
votes
1answer
81 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
71 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
154 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. ...
0
votes
0answers
18 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 ...