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
25 views

Non-Negative Integer answer of Inequation

i study some combination note. in setion inequation non-negative answer i have some misunderetsanding. suppose we have $7<=x_1+x_2+x_3<=12$, i want to calculate numbwe of Non-Negative Integer ...
-1
votes
1answer
25 views

Combination Problem on Distinct Object

How many way we can devide 10 distinct object between 5 student? i think the solution is combination(10,5)*5! but i'm not sure. or maybe 5^10? any expert could help me ? add some detail?
0
votes
0answers
6 views

Retrieve the initial cubic bezier curve subdivided in two bezier curves

I have a cubic Bezier curve subdivided to two cubic Bezier: Assuming that "t_cut" is the t value where this initial Bezier is cut: example of function subdivision(BezierCurve initialCurve, ...
2
votes
1answer
16 views

Rounding Percentages

Okay so I have been having a problem and would really appreciate any help. I have posted a table below with the aim of making this as simple/precise as possible. ...
1
vote
0answers
29 views

Why is there information loss here?

I posted this a while ago, but realized that actually this works, but produces information loss. Here is the process: Let's try to reduce a number $x$. We will be using base $\beta$ for this process. ...
0
votes
0answers
13 views

Do automatons and formal grammars belong to formal systems

A formal system consists of a formal language, a formal grammar that generates the language, a set of axioms, and a set of inference rules. Are automatons also formal systems? Is an automaton ...
0
votes
1answer
49 views

fastest algorithm for prime factorization [on hold]

I need the fastest algorithm to factorize the given number $N$ as a product of primes. $$N=p_1^{e_1}p_2{e_2}\ldots p_n^{e_n}$$ where $p_1, p_2,\ldots ,p_n$ are primes and $e_1,e_2,\ldots, e_n$ are ...
7
votes
1answer
67 views

Applications of Geometry to Computer Graphics

How is differential geometry (or any type of theoretical math) related to computer graphics and/or computer programming? A friend of a friend of mine has only a bachelors degree in pure math and got ...
4
votes
3answers
44 views

Show that $\frac{x^4 +7x^3+5}{4x+1}$ is big-theta($x^3$)

I'm having trouble grasping how to set these types of problems. There are a lot of related questions but it's difficult to abstract a general procedure on finding constants that give the given ...
2
votes
1answer
27 views

Simple minimization problem

Suppose we want to execute a program on a processor which can run in three different modes. Each mode can be describe by a pair $(E,\tau)$ where $E$ denotes the energy consumption per cycle (in nJ) ...
-2
votes
0answers
28 views

Maximum number of compressed RLE strings under any given length

Given a random string of length L (for instance, "01100010000101" of length "14"), and knowing that this string is only numerical, how many other strings under the form Y one can achieve by ...
-2
votes
1answer
82 views

The “Four beer caps” puzzle [closed]

Four beer caps are placed on the corners of a square table with arbitrary orientations. There is a robot on the table that acts upon three commands: (a) “flip a corner cap”, (b) “flip two diagonal ...
2
votes
1answer
49 views

need help in number theory problem

Given a number $n$. I need to find the largest $q$ such that $q^2$ divides $n$. I need the fastest method to find $q$. $q$ can be any number prime or composite. At present I am factorizing the number ...
1
vote
1answer
44 views

Merge two or more cubic Bézier curves for optimization

I am looking for an algorithm which can merge several cubic Bezier curves. For instance, I have a lot of cubic Bezier that are joined to form a poly-Bezier curve. The idea is to merge dynamically some ...
-6
votes
0answers
68 views

Computation Challenging Problem [closed]

i ask one question, but someone put it on-hold. I ask it again. I see some strange definition in lecture note, every expert could help me in defining this notation in computation theory course? and ...
-5
votes
0answers
65 views

Computation Challenging Definition Problem [closed]

I see some strange definition in lecture note, every expert could help me in defining this notation in computation theory course? and why this sentence is true?? a) there is infinite number t, such ...
1
vote
1answer
53 views

Is there a more general proof for the halting problem?

Note:If this question is better suited for a different site, please tell me in the comments. Summary:Is there a proof for the impossibility of the halting problem that doesn't involve calling it on ...
0
votes
0answers
17 views

n-1 dimensional hypercube perpendicular to given edge in m dimensional Hamming hypercube

Suppose to have a $m$-dimensional direct binary hypercube of $n=2^m$ nodes with appropriate labeling of nodes given the corrisponding m-bit string. Picking a directed edge $e=(u,v)$, is there a ...
2
votes
1answer
50 views

Computing a solution of the Laplace-Eigenvalueproblem with Neumann-b.c.

Good day! I was considering the Laplace-Eigenvalueproblem with Neumann b.c., i.e. find $u \in H^1(\Omega) \setminus \{0\}$ and $\lambda \in \mathbb{R}$, such that: \begin{eqnarray} -\Delta u \ ...
-1
votes
1answer
45 views

prenex equivalence problem

Suppose: $$\forall x\exists y \phi(x,y) \to \neg \exists x\psi(x) $$ which of the following formula are prenex normal equivalence with the above formula? i didn't any idea to explain it. it's a ...
0
votes
0answers
16 views
0
votes
3answers
80 views

Combination Problem Understanding

How many ways can a Doctor go to the Hospital on $5$ days of January (which has $31$ days) such that no two visits are on consecutive days? I think the solution is: $\displaystyle\binom{27}{5}$ But ...
1
vote
1answer
40 views

Partition Graph Challenging Question

I want to find in which of the following Graph, the edges cannot partitioned to triangles? Km,n,r means 3-Partite Complete Graph with m, n, and r sections. a) K7 b) K12 c) K3,3,3 d) K5,5,5 i ...
0
votes
1answer
15 views

Planner Combination Problem on Graph

I ran into a Graph Problem. Suppose G is A Planner Graph with 100 Vertices such that if connect each two Non-adjacent vertices, the resulting graph would be non-planner. what is the number of edges ...
1
vote
1answer
39 views

Perfect Matching Combination Problem

We know: A perfect matching (a.k.a. 1-factor) is a matching which matches all vertices of the graph. if we remove edges of perfect matching of a 12-Complete Graph. how many triangle remain in this ...
2
votes
2answers
53 views

The value of loop variable at the end of a loop in the insertion sort

I am looking at the algorithm of the insertion sort: Input: $A[1 \dots n]$ ...
0
votes
0answers
20 views

Space-dependent diffusivity and finite-differences

I want to implement a finite difference code of this simple diffusion equation with space-dependent diffusivity: $$\partial_{t}u =D\partial_{x}^{2}u+\partial_{x}D\cdot\partial_{x}u$$ I go for a ...
0
votes
1answer
22 views

Finding final value of sum from double summation code fragment.

sum = 0; inc = 0 for i from 1 to n for j from 1 to i sum = sum + inc inc = inc + 1 What does it mean when it is asking the "final value of sum" from above code ...
0
votes
1answer
126 views

Proof completion: if $Y$ is a closed term in strong nf, then $Yx$ weakly reduces to a strong nf $Z$

I am self-studying Hindley & Seldin's Lambda-Calculus and Combinators. I would appreciate some help with filling in a final detail for a proof for the following statement regarding combinatory ...
0
votes
1answer
47 views

Computable Set & Function

we know that i read this sentence are true? can anyone say an example for following sentence? there are a non computable set A such that
0
votes
1answer
22 views

Convex hulls for a finite amount of points

I'm trying to understand what a convex hull intuitively is, and say given for a set of points $(x,y)\in\mathbb{R}^2$ how is it generated from these points? I tried reading the wikipedia article and ...
-1
votes
1answer
60 views

Turing & Computability & Computation

We know if we have: we can show (T=t= Turin Redu.) but i have no idea why this relation be correct? any idea?
0
votes
0answers
12 views

Must the weight function be nonnegative for the greedy algorithm to be optimal for both a matroid and a greedoid?

Must the weight function be nonnegative for the greedy algorithm to be optimal for both a matroid and a greedoid? For a matroid, the codomain of the weight function is $[0,\infty)$, from Wikipedia ...
1
vote
0answers
47 views

Big Challenge in TM & R.E Set [closed]

we know that Halting problem {(M.w) | M halts on input w} is r.e but not recursive. i see the following sentence in one book. "the set of {(M.w) | M halts on input w and M is a TM}} is not r.e" ...
-2
votes
1answer
240 views

How to obtain $\operatorname{lcm}(a_1,a_2,a_3,\ldots,a_n)\%1000000007$

The problem is that you have $n$ numbers whose value can be in range $[1,100000]$. The task is to find the LCM of all these numbers. Now the answer can be very large so it should be printed MODULO ...
1
vote
1answer
43 views

Meaning of the characteristic polynomial of a matroid

From wikipedia The characteristic polynomial of a matroid $M$ (which is sometimes called the chromatic polynomial,[29] although it does not count colorings), is defined to be $$ p_M(\lambda) ...
0
votes
1answer
21 views

Linear equation so that the solutions has to be integers.

I have this equation $$-X_5-32X_4-32^2X_3-32^3X_2-32^4X_1=[PARAMETER]$$ I want to get all the solutions to this equation with a given parameter(integer) and all of the solutions has to be integers ...
0
votes
0answers
61 views

TAUTOLOGIES NP-Complete Condition

The decision problem TAUTOLOGIES is, Given $\forall x_1 \forall x_2 ... \forall x_n$ $\phi(x_1, x_2, ... x_n)$ a set of universally quantified Boolean variables and a Boolean formula ...
0
votes
1answer
34 views

How do you find the probability of a certain state in Markov Chain?

This question appears without answer in an old exam I found (not a homework question) Suppose messages that enter a system need to be processed by two servers. They arrive at the system at a ...
2
votes
2answers
56 views

Equivalent definitions for a coloop?

From wikipedia, in a matroid, An element that belongs to no circuit is called a coloop. Equivalently, an element is a coloop if it belongs to every basis. I wonder why the equivalence? From ...
0
votes
1answer
17 views

How do the dependent sets of a matroid characterize the matroid?

Wikipedia says: The dependent sets of a matroid characterize the matroid completely. The collection of dependent sets has simple properties that may be taken as axioms for a matroid. So I ...
0
votes
0answers
7 views

Maximum amount of positional offset caused by noisy distance measurements in Quadrilateration

Quadrilateration is a range-based localization technique applied to wireless sensor networks. It is the equivalent method of trilateration in 2D. Assume that, there are four beacons (the sensors ...
0
votes
0answers
10 views

The mathematical road to learning procedural graphic generation

I am trying to get started with procedural generation of computer graphics and animation, but my basic math skills are not enough. Can anyone recommend the courses/topics in mathematics that will get ...
0
votes
0answers
17 views

to maximize the summation

let F=$∑i=1$ to $N$ $((abs(A[i]-X))^P mod $K$)mod K$ $A[1..N]$ is an array with $N$ elements, the problem is to find $X$ such that the above summation F maximized where $X$ can take any value from ...
5
votes
1answer
46 views

Mathematical definition of Blender's F-Curves

I'm designing software for generating animation curves. I'd like the curves to be based on those found in Blender 3D, which they call "F-Curves." According to the page on the Blender Wiki, they are ...
0
votes
2answers
46 views

How to prove that for all 25 ppl and 4 groups, there is a group of at least 6 ppl from the same group?

As of Jun.17, I predict that Brazil, Germany, Italy, and Argentina will make it to the semi-finals of the FIFA World Cup. Suppose you have a group of 25 footballers from those four countries. Prove ...
3
votes
1answer
36 views

Image Reconstruction:Phase vs. Magnitude

Figure 1.(c) shows the Test image reconstructed from MAGNITUDE spectrum only. We can say that the intensity values of LOW frequency pixels are comparatively more than HIGH frequency pixels. $$ ...
1
vote
1answer
25 views

What kind of set system is defined to have this property?

Let $E$ be a set, and $F \in \mathcal P(E)$ has the following property: For every $x\in E$ and $Y,Z\in F$ with $x\notin Y\cup Z$, there exists $X\in F$ with $(Y\cap Z)\cup\{x\}\subseteq X$. I wonder ...
2
votes
0answers
27 views

Generating interesting random TMs

To get a more intuitive understanding of the halting problem I want to generate some random TMs and see how they behave, what some heuristics can tell about them, etc. The problem is that, if I ...
0
votes
0answers
35 views

another series problem [duplicate]

I need help in simplification below are the two formulas for AGP series: if $n$ is even $a\cdot r^{(n-1)/2} + d\cdot( 1 + r + r^2 + r^{(n-1)/2})$ if $n$ is odd $a\cdot r^{(n-1)/2} + d\cdot( 1 + ...